東京大学 2013 年小遊戲解析

從 2010 年開始，東京大学情報理工学系研究科在招生海報都會放上一段藏了訊息的 binary。去年看到這個新聞之後就多留了一份心。前幾個月研究所都在招生，就想到今年的小遊戲也差不多該出了。果然今年他們又延續了海報~~用和服櫻花妹~~附上 binary 謎題的這個優良傳統。

拿到海報圖檔之後就開工啦！

首先用 OCR 和人眼把圖檔裡的 01 抽出來，得到

0010101100101101001011010010110100101101001010110000101001111100010010010111000001110111011001110111110000
0010100111110001101111001011100010111001110101011111000100010101000110010010000100100100100000010010110100
1110010011110101001000001010011111000110000101100011011101000110111101111100011111000111110001111100011111
0000100000011111000111110001111100011111000000101001111100011101010111001101110111001000010111110001010110
0101011001010110010101100010000001010110010101100101011001010110000010100010101100101101001011010010110100
1011010010101100101101001011010010110100101101001010110010110100101101001011010010110100101011001011010010
1101001011010010110100101011000010100111110000100000011101010110100101101100011111000110111100100000001000
0001110100011111000110100001110111001110100010000001111100011000010110101100101110011110010111110000101101
0011111001010011000010100111110000100000011001100111010000100000011111000101001100101101011101000110111101
1111000110111001110111001011110111001001111100010111110010111101100001011011110111110000101101001111100101
0100000010100111110001110011011000110111100101110011011111000110100101100001011010010010000001111100011011
1100101110011011110010000001111100010111110111010001110100011011000111110000101101001111100101010100001010
0111110001110100011101010111010101100101011111000110111001101110011011100010111001111100011011110110101001
1010110110100101111100011011000110101100101110001000000111110000101101001111100101011000101100010110010000
1010001010110010110100101101001011010010110100101011001011010010110100101101001011010010101100101101001011
0100101101001011010010101100101101001011010010110100101101001010110000101001111100010001110101010001100001
0110010001111100000010100111110001101000001011110111001101100101011111000000101001111100011011000110100000
1000000111001001111100000010100111110001000011010100110111000001000110011111000000101000101011001011010010
1101001011010010110100101011000010100000101001010010011011110111010001100001011101000110010100100000011101
0001101000011010010111001100100000011000110111010101100010011001010010000001100010011110010010000001110010
0110010101110000011001010110000101110100011010010110111001100111000010100101010000101100010010000010110001
0001010010110001010101001011000100111000101100010010010010110001010110001011000100010100101100010100100010
1100010100110010110001001001001011000101010000101100010110010010110001001111001011000100011000101100010101
0000101100010011110010110001001011001011000101100100101100010011110000101000110010001100000011000101011110
0101111000110011001000000111010001101001011011010110010101110011001011100000101000001010011000010101111001
0111100110001000100000011010010111001100100000011101010111000000101101011000010111001001110010011011110111
01110010000001101110011011110111010001100001011101000110100101101111011011100010111000001010

0010101100101101001011010010110100101101001010110000101001111100010010010111000001110111011001110111110000

0010100111110001101111001011100010111001110101011111000100010101000110010010000100100100100000010010110100

1110010011110101001000001010011111000110000101100011011101000110111101111100011111000111110001111100011111

0000100000011111000111110001111100011111000000101001111100011101010111001101110111001000010111110001010110

0101011001010110010101100010000001010110010101100101011001010110000010100010101100101101001011010010110100

1011010010101100101101001011010010110100101101001010110010110100101101001011010010110100101011001011010010

1101001011010010110100101011000010100111110000100000011101010110100101101100011111000110111100100000001000

0001110100011111000110100001110111001110100010000001111100011000010110101100101110011110010111110000101101

0011111001010011000010100111110000100000011001100111010000100000011111000101001100101101011101000110111101

1111000110111001110111001011110111001001111100010111110010111101100001011011110111110000101101001111100101

0100000010100111110001110011011000110111100101110011011111000110100101100001011010010010000001111100011011

1100101110011011110010000001111100010111110111010001110100011011000111110000101101001111100101010100001010

0111110001110100011101010111010101100101011111000110111001101110011011100010111001111100011011110110101001

1010110110100101111100011011000110101100101110001000000111110000101101001111100101011000101100010110010000

1010001010110010110100101101001011010010110100101011001011010010110100101101001011010010101100101101001011

0100101101001011010010101100101101001011010010110100101101001010110000101001111100010001110101010001100001

0110010001111100000010100111110001101000001011110111001101100101011111000000101001111100011011000110100000

1000000111001001111100000010100111110001000011010100110111000001000110011111000000101000101011001011010010

1101001011010010110100101011000010100000101001010010011011110111010001100001011101000110010100100000011101

0001101000011010010111001100100000011000110111010101100010011001010010000001100010011110010010000001110010

0110010101110000011001010110000101110100011010010110111001100111000010100101010000101100010010000010110001

0001010010110001010101001011000100111000101100010010010010110001010110001011000100010100101100010100100010

1100010100110010110001001001001011000101010000101100010110010010110001001111001011000100011000101100010101

0000101100010011110010110001001011001011000101100100101100010011110000101000110010001100000011000101011110

0101111000110011001000000111010001101001011011010110010101110011001011100000101000001010011000010101111001

0111100110001000100000011010010111001100100000011101010111000000101101011000010111001001110010011011110111

01110010000001101110011011110111010001100001011101000110100101101111011011100010111000001010

一共是 2848 個 0 或 1。

2848 可以被 8 整除，直接把這東西轉換成 binary data 試試，果然得到一份題目的文字檔。

+----+
|Ipwg|
|o..u|EFHI KNOR
|acto||||| ||||
|usw!|VVVV VVVV
+----+----+----+----+
| uil|o  t|hw: |ak.y|->S
| ft |S-to|nw/r|_/ao|->T
|scys|iai |o.o |_ttl|->U
|tuue|nnn.|ojki|lk. |->V,Y
+----+----+----+----+
|GTad|
|h/se|
|lh r|
|CSpF|
+----+

Rotate this cube by repeating
T,H,E,U,N,I,V,E,R,S,I,T,Y,O,F,T,O,K,Y,O
201^^3 times.

a^^b is up-arrow notation.

+----+

|Ipwg|

|o..u|EFHI KNOR

|acto||||| ||||

|usw!|VVVV VVVV

+----+----+----+----+

| uil|o t|hw: |ak.y|->S

| ft |S-to|nw/r|_/ao|->T

|scys|iai |o.o |_ttl|->U

|tuue|nnn.|ojki|lk. |->V,Y

+----+----+----+----+

|GTad|

|h/se|

|lh r|

|CSpF|

+----+

Rotate this cube by repeating

T,H,E,U,N,I,V,E,R,S,I,T,Y,O,F,T,O,K,Y,O

201^^3 times.

a^^b is up-arrow notation.

看來是個 4x4x4 的魔術方塊（展開圖），而 E, F, H, I 等等則各是代表轉動魔術方塊的其中一層。接下來我們要做的就是依照他的指示，重複 THEUNIVERSITYOFTOKYO 這個動作 201^^3 次。問題來了，所謂的 201^^3 到底是多少呢？查了一下 Wiki，原來 up-arrow notation 是這個意思。
也就是說，201^^3 代表
\[201 \uparrow\uparrow 3 = 201^{201^{201}}\]
是個超級大的數字！

看到這麼大的數字，第一個想法就是：絕對不會需要轉這麼多次！

首先，就算 4x4x4 的魔術方塊能夠轉出所有的組合（事實上沒辦法），頂多也就
\[(4 \times 4 \times 6)! = 96!\]
這麼多的組合方式。而且，
\[96! < 201^{201} = 201 \uparrow\uparrow 2 < 201 \uparrow\uparrow 3\] 根據鴿籠原理，在不斷重複 THEUNIVERSITYOFTOKYO 這個動作的情況下，因為 \(96! < 201 \uparrow\uparrow 3\)，過程中必然會有轉到之前轉出過組合的狀況（做了多餘的事情）。所以關鍵在於，如何找出方法，轉個少少次，就有轉 \(201 \uparrow\uparrow 3\) 次的效果。在做更進一步的事情之前，還有一個問題，那就是如何用程式來計算所謂的“旋轉魔術方塊”這件事。假如我們把魔術方塊上的每個小面都標上編號，所謂的“旋轉魔術方塊”這件事情，就轉變成了“位置與編號的重新對應”。對程式來說，就是決定“新狀態的某個位置根據舊狀態來看，新的編號應該是多少”。舉個例子來說，如果把一個位置代碼和編號一樣的狀態叫做 identity：

+-----------+
| 0  1  2  3|
| 4  5  6  7|
| 8  9 10 11|
|12 13 14 15|
+-----------+-----------+-----------+-----------+
|16 17 18 19|20 21 22 23|24 25 26 27|28 29 30 31|
|32 33 34 35|36 37 38 39|40 41 42 43|44 45 46 47|
|48 49 50 51|52 53 54 55|56 57 58 59|60 61 62 63|
|64 65 66 67|68 69 70 71|72 73 74 75|76 77 78 79|
+-----------+-----------+-----------+-----------+
|80 81 82 83|
|84 85 86 87|
|88 89 90 91|
|92 93 94 95|
+-----------+

+-----------+

| 0 1 2 3|

| 4 5 6 7|

| 8 9 10 11|

|12 13 14 15|

+-----------+-----------+-----------+-----------+

|16 17 18 19|20 21 22 23|24 25 26 27|28 29 30 31|

|32 33 34 35|36 37 38 39|40 41 42 43|44 45 46 47|

|48 49 50 51|52 53 54 55|56 57 58 59|60 61 62 63|

|64 65 66 67|68 69 70 71|72 73 74 75|76 77 78 79|

+-----------+-----------+-----------+-----------+

|80 81 82 83|

|84 85 86 87|

|88 89 90 91|

|92 93 94 95|

+-----------+

那 identity 經過 E 這個動作之後，會變成這樣：

+-----------+
| 0  1  2  3|
| 4  5  6  7|
| 8  9 10 11|
|79 63 47 31|
+-----------+-----------+-----------+-----------+
|64 48 32 16|12 21 22 23|24 25 26 27|28 29 30 80|
|65 49 33 17|13 37 38 39|40 41 42 43|44 45 46 81|
|66 50 34 18|14 53 54 55|56 57 58 59|60 61 62 82|
|67 51 35 19|15 69 70 71|72 73 74 75|76 77 78 83|
+-----------+-----------+-----------+-----------+
|68 52 36 20|
|84 85 86 87|
|88 89 90 91|
|92 93 94 95|
+-----------+

+-----------+

| 0 1 2 3|

| 4 5 6 7|

| 8 9 10 11|

|79 63 47 31|

+-----------+-----------+-----------+-----------+

|64 48 32 16|12 21 22 23|24 25 26 27|28 29 30 80|

|65 49 33 17|13 37 38 39|40 41 42 43|44 45 46 81|

|66 50 34 18|14 53 54 55|56 57 58 59|60 61 62 82|

|67 51 35 19|15 69 70 71|72 73 74 75|76 77 78 83|

+-----------+-----------+-----------+-----------+

|68 52 36 20|

|84 85 86 87|

|88 89 90 91|

|92 93 94 95|

+-----------+

只要建立個對照表，讓程式知道如何根據舊狀態建立新狀態就好了。轉換了問題之後，程式的撰寫就變得簡單了。為了方便起見，我是把它寫成 Python 的一個小 module。其中包含了一個 rotate 的函數，還有一個代表 THEUNIVERSITYOFTOKYO 這個動作的 M。

# identity element
identity = range(4*4*6)

rotate_maps = dict()

rotate_maps['E'] = [
     0,  1,  2,  3, 
     4,  5,  6,  7, 
     8,  9, 10, 11, 
    79, 63, 47, 31, 
    64, 48, 32, 16, 12, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 80, 
    65, 49, 33, 17, 13, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 81, 
    66, 50, 34, 18, 14, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 82, 
    67, 51, 35, 19, 15, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 83, 
    68, 52, 36, 20, 
    84, 85, 86, 87, 
    88, 89, 90, 91, 
    92, 93, 94, 95, 
]
rotate_maps['F'] = [
     0,  1,  2,  3, 
     4,  5,  6,  7, 
    78, 62, 46, 30, 
    12, 13, 14, 15, 
    16, 17, 18, 19, 20,  8, 22, 23, 24, 25, 26, 27, 28, 29, 84, 31, 
    32, 33, 34, 35, 36,  9, 38, 39, 40, 41, 42, 43, 44, 45, 85, 47, 
    48, 49, 50, 51, 52, 10, 54, 55, 56, 57, 58, 59, 60, 61, 86, 63, 
    64, 65, 66, 67, 68, 11, 70, 71, 72, 73, 74, 75, 76, 77, 87, 79, 
    80, 81, 82, 83, 
    69, 53, 37, 21, 
    88, 89, 90, 91, 
    92, 93, 94, 95, 
]
rotate_maps['H'] = [
     0,  1,  2,  3, 
    77, 61, 45, 29, 
     8,  9, 10, 11, 
    12, 13, 14, 15, 
    16, 17, 18, 19, 20, 21,  4, 23, 24, 25, 26, 27, 28, 88, 30, 31, 
    32, 33, 34, 35, 36, 37,  5, 39, 40, 41, 42, 43, 44, 89, 46, 47, 
    48, 49, 50, 51, 52, 53,  6, 55, 56, 57, 58, 59, 60, 90, 62, 63, 
    64, 65, 66, 67, 68, 69,  7, 71, 72, 73, 74, 75, 76, 91, 78, 79, 
    80, 81, 82, 83, 
    84, 85, 86, 87, 
    70, 54, 38, 22, 
    92, 93, 94, 95, 
]
rotate_maps['I'] = [
    76, 60, 44, 28, 
     4,  5,  6,  7, 
     8,  9, 10, 11, 
    12, 13, 14, 15, 
    16, 17, 18, 19, 20, 21, 22,  0, 27, 43, 59, 75, 92, 29, 30, 31, 
    32, 33, 34, 35, 36, 37, 38,  1, 26, 42, 58, 74, 93, 45, 46, 47, 
    48, 49, 50, 51, 52, 53, 54,  2, 25, 41, 57, 73, 94, 61, 62, 63, 
    64, 65, 66, 67, 68, 69, 70,  3, 24, 40, 56, 72, 95, 77, 78, 79, 
    80, 81, 82, 83, 
    84, 85, 86, 87, 
    88, 89, 90, 91, 
    71, 55, 39, 23, 
]
rotate_maps['K'] = [
     0,  1,  2, 19, 
     4,  5,  6, 35, 
     8,  9, 10, 51, 
    12, 13, 14, 67, 
    16, 17, 18, 83, 68, 52, 36, 20, 15, 25, 26, 27, 28, 29, 30, 31, 
    32, 33, 34, 87, 69, 53, 37, 21, 11, 41, 42, 43, 44, 45, 46, 47, 
    48, 49, 50, 91, 70, 54, 38, 22,  7, 57, 58, 59, 60, 61, 62, 63, 
    64, 65, 66, 95, 71, 55, 39, 23,  3, 73, 74, 75, 76, 77, 78, 79, 
    80, 81, 82, 72, 
    84, 85, 86, 56, 
    88, 89, 90, 40, 
    92, 93, 94, 24, 
]
rotate_maps['N'] = [
     0,  1, 18,  3, 
     4,  5, 34,  7, 
     8,  9, 50, 11, 
    12, 13, 66, 15, 
    16, 17, 82, 19, 20, 21, 22, 23, 24, 14, 26, 27, 28, 29, 30, 31, 
    32, 33, 86, 35, 36, 37, 38, 39, 40, 10, 42, 43, 44, 45, 46, 47, 
    48, 49, 90, 51, 52, 53, 54, 55, 56,  6, 58, 59, 60, 61, 62, 63, 
    64, 65, 94, 67, 68, 69, 70, 71, 72,  2, 74, 75, 76, 77, 78, 79, 
    80, 81, 73, 83, 
    84, 85, 57, 87, 
    88, 89, 41, 91, 
    92, 93, 25, 95, 
]
rotate_maps['O'] = [
     0, 17,  2,  3, 
     4, 33,  6,  7, 
     8, 49, 10, 11, 
    12, 65, 14, 15, 
    16, 81, 18, 19, 20, 21, 22, 23, 24, 25, 13, 27, 28, 29, 30, 31, 
    32, 85, 34, 35, 36, 37, 38, 39, 40, 41,  9, 43, 44, 45, 46, 47, 
    48, 89, 50, 51, 52, 53, 54, 55, 56, 57,  5, 59, 60, 61, 62, 63, 
    64, 93, 66, 67, 68, 69, 70, 71, 72, 73,  1, 75, 76, 77, 78, 79, 
    80, 74, 82, 83, 
    84, 58, 86, 87, 
    88, 42, 90, 91, 
    92, 26, 94, 95, 
]
rotate_maps['R'] = [
    16,  1,  2,  3, 
    32,  5,  6,  7, 
    48,  9, 10, 11, 
    64, 13, 14, 15, 
    80, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 12, 31, 47, 63, 79, 
    84, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,  8, 30, 46, 62, 78, 
    88, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58,  4, 29, 45, 61, 77, 
    92, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74,  0, 28, 44, 60, 76, 
    75, 81, 82, 83, 
    59, 85, 86, 87, 
    43, 89, 90, 91, 
    27, 93, 94, 95, 
]
rotate_maps['S'] = [
     3,  7, 11, 15, 
     2,  6, 10, 14, 
     1,  5,  9, 13, 
     0,  4,  8, 12, 
    28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 
    32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 
    48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 
    64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 
    80, 81, 82, 83, 
    84, 85, 86, 87, 
    88, 89, 90, 91, 
    92, 93, 94, 95, 
]
rotate_maps['T'] = [
     0,  1,  2,  3, 
     4,  5,  6,  7, 
     8,  9, 10, 11, 
    12, 13, 14, 15, 
    16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 
    44, 45, 46, 47, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 
    48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 
    64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 
    80, 81, 82, 83, 
    84, 85, 86, 87, 
    88, 89, 90, 91, 
    92, 93, 94, 95, 
]
rotate_maps['U'] = [
     0,  1,  2,  3, 
     4,  5,  6,  7, 
     8,  9, 10, 11, 
    12, 13, 14, 15, 
    16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 
    32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 
    60, 61, 62, 63, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 
    64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 
    80, 81, 82, 83, 
    84, 85, 86, 87, 
    88, 89, 90, 91, 
    92, 93, 94, 95, 
]
rotate_maps['V'] = [
     0,  1,  2,  3, 
     4,  5,  6,  7, 
     8,  9, 10, 11, 
    12, 13, 14, 15, 
    16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 
    32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 
    48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 
    76, 77, 78, 79, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 
    92, 88, 84, 80, 
    93, 89, 85, 81, 
    94, 90, 86, 82, 
    95, 91, 87, 83, 
]
rotate_maps['Y'] = rotate_maps['V']

def rotate(vector, map):
    return [vector[map[i]] for i in identity]

M = identity
for c in 'THEUNIVERSITYOFTOKYO':
    M = rotate(M, rotate_maps[c])

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

# identity element

identity = range(4*4*6)

rotate_maps = dict()

rotate_maps['E'] = [

0, 1, 2, 3,

4, 5, 6, 7,

8, 9, 10, 11,

79, 63, 47, 31,

64, 48, 32, 16, 12, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 80,

65, 49, 33, 17, 13, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 81,

66, 50, 34, 18, 14, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 82,

67, 51, 35, 19, 15, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 83,

68, 52, 36, 20,

84, 85, 86, 87,

88, 89, 90, 91,

92, 93, 94, 95,

]

rotate_maps['F'] = [

0, 1, 2, 3,

4, 5, 6, 7,

78, 62, 46, 30,

12, 13, 14, 15,

16, 17, 18, 19, 20, 8, 22, 23, 24, 25, 26, 27, 28, 29, 84, 31,

32, 33, 34, 35, 36, 9, 38, 39, 40, 41, 42, 43, 44, 45, 85, 47,

48, 49, 50, 51, 52, 10, 54, 55, 56, 57, 58, 59, 60, 61, 86, 63,

64, 65, 66, 67, 68, 11, 70, 71, 72, 73, 74, 75, 76, 77, 87, 79,

80, 81, 82, 83,

69, 53, 37, 21,

88, 89, 90, 91,

92, 93, 94, 95,

]

rotate_maps['H'] = [

0, 1, 2, 3,

77, 61, 45, 29,

8, 9, 10, 11,

12, 13, 14, 15,

16, 17, 18, 19, 20, 21, 4, 23, 24, 25, 26, 27, 28, 88, 30, 31,

32, 33, 34, 35, 36, 37, 5, 39, 40, 41, 42, 43, 44, 89, 46, 47,

48, 49, 50, 51, 52, 53, 6, 55, 56, 57, 58, 59, 60, 90, 62, 63,

64, 65, 66, 67, 68, 69, 7, 71, 72, 73, 74, 75, 76, 91, 78, 79,

80, 81, 82, 83,

84, 85, 86, 87,

70, 54, 38, 22,

92, 93, 94, 95,

]

rotate_maps['I'] = [

76, 60, 44, 28,

4, 5, 6, 7,

8, 9, 10, 11,

12, 13, 14, 15,

16, 17, 18, 19, 20, 21, 22, 0, 27, 43, 59, 75, 92, 29, 30, 31,

32, 33, 34, 35, 36, 37, 38, 1, 26, 42, 58, 74, 93, 45, 46, 47,

48, 49, 50, 51, 52, 53, 54, 2, 25, 41, 57, 73, 94, 61, 62, 63,

64, 65, 66, 67, 68, 69, 70, 3, 24, 40, 56, 72, 95, 77, 78, 79,

80, 81, 82, 83,

84, 85, 86, 87,

88, 89, 90, 91,

71, 55, 39, 23,

]

rotate_maps['K'] = [

0, 1, 2, 19,

4, 5, 6, 35,

8, 9, 10, 51,

12, 13, 14, 67,

16, 17, 18, 83, 68, 52, 36, 20, 15, 25, 26, 27, 28, 29, 30, 31,

32, 33, 34, 87, 69, 53, 37, 21, 11, 41, 42, 43, 44, 45, 46, 47,

48, 49, 50, 91, 70, 54, 38, 22, 7, 57, 58, 59, 60, 61, 62, 63,

64, 65, 66, 95, 71, 55, 39, 23, 3, 73, 74, 75, 76, 77, 78, 79,

80, 81, 82, 72,

84, 85, 86, 56,

88, 89, 90, 40,

92, 93, 94, 24,

]

rotate_maps['N'] = [

0, 1, 18, 3,

4, 5, 34, 7,

8, 9, 50, 11,

12, 13, 66, 15,

16, 17, 82, 19, 20, 21, 22, 23, 24, 14, 26, 27, 28, 29, 30, 31,

32, 33, 86, 35, 36, 37, 38, 39, 40, 10, 42, 43, 44, 45, 46, 47,

48, 49, 90, 51, 52, 53, 54, 55, 56, 6, 58, 59, 60, 61, 62, 63,

64, 65, 94, 67, 68, 69, 70, 71, 72, 2, 74, 75, 76, 77, 78, 79,

80, 81, 73, 83,

84, 85, 57, 87,

88, 89, 41, 91,

92, 93, 25, 95,

]

rotate_maps['O'] = [

0, 17, 2, 3,

4, 33, 6, 7,

8, 49, 10, 11,

12, 65, 14, 15,

16, 81, 18, 19, 20, 21, 22, 23, 24, 25, 13, 27, 28, 29, 30, 31,

32, 85, 34, 35, 36, 37, 38, 39, 40, 41, 9, 43, 44, 45, 46, 47,

48, 89, 50, 51, 52, 53, 54, 55, 56, 57, 5, 59, 60, 61, 62, 63,

64, 93, 66, 67, 68, 69, 70, 71, 72, 73, 1, 75, 76, 77, 78, 79,

80, 74, 82, 83,

84, 58, 86, 87,

88, 42, 90, 91,

92, 26, 94, 95,

]

rotate_maps['R'] = [

16, 1, 2, 3,

32, 5, 6, 7,

48, 9, 10, 11,

64, 13, 14, 15,

80, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 12, 31, 47, 63, 79,

84, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 8, 30, 46, 62, 78,

88, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 4, 29, 45, 61, 77,

92, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 0, 28, 44, 60, 76,

75, 81, 82, 83,

59, 85, 86, 87,

43, 89, 90, 91,

27, 93, 94, 95,

]

rotate_maps['S'] = [

3, 7, 11, 15,

2, 6, 10, 14,

1, 5, 9, 13,

0, 4, 8, 12,

28, 29, 30, 31, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,

32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,

48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,

64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,

80, 81, 82, 83,

84, 85, 86, 87,

88, 89, 90, 91,

92, 93, 94, 95,

]

rotate_maps['T'] = [

0, 1, 2, 3,

4, 5, 6, 7,

8, 9, 10, 11,

12, 13, 14, 15,

16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,

44, 45, 46, 47, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43,

48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,

64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,

80, 81, 82, 83,

84, 85, 86, 87,

88, 89, 90, 91,

92, 93, 94, 95,

]

rotate_maps['U'] = [

0, 1, 2, 3,

4, 5, 6, 7,

8, 9, 10, 11,

12, 13, 14, 15,

16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,

32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,

60, 61, 62, 63, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,

64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79,

80, 81, 82, 83,

84, 85, 86, 87,

88, 89, 90, 91,

92, 93, 94, 95,

]

rotate_maps['V'] = [

0, 1, 2, 3,

4, 5, 6, 7,

8, 9, 10, 11,

12, 13, 14, 15,

16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,

32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,

48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63,

76, 77, 78, 79, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75,

92, 88, 84, 80,

93, 89, 85, 81,

94, 90, 86, 82,

95, 91, 87, 83,

]

rotate_maps['Y'] = rotate_maps['V']

def rotate(vector, map):

return [vector[map[i]] for i in identity]

M = identity

for c in 'THEUNIVERSITYOFTOKYO':

M = rotate(M, rotate_maps[c])

回到一開始的問題，那我麼要怎麼樣簡化那 \(201 \uparrow\uparrow 3\) 次的轉動呢？這裡就必須考慮魔術方塊的兩個特性：

狀態數為有限
每個動作都是可逆的（就反轉而已）

根據 finite state machine 的理論，我們可以找得到一個最小的正整數 \(n < 96!\) 使得 \[(\text{operation THEUNIVERSITYOFTOKYO})^n \equiv M^n \equiv \text{identity}\] 二話不說，讓我們寫支程式來找看看

import rubiks

v = rubiks.identity
counter = 0
done = False
while not done:
    v = rubiks.rotate(v, rubiks.M)
    counter += 1
    if v == rubiks.identity:
        done = True
print 'n =', counter

import rubiks

v = rubiks.identity

counter = 0

done = False

while not done:

v = rubiks.rotate(v, rubiks.M)

counter += 1

if v == rubiks.identity:

done = True

print 'n =', counter

跑完得到 \(n = 1008\)。也就是說， \[M^{201 \uparrow\uparrow 3} \equiv M^{(201 \uparrow\uparrow 3)\mod{1008}}\] 計算 \((201 \uparrow\uparrow 3)\mod{1008}\) 的部分我是用 Mathematica 的 PowerMod （拿來做 RSA 也很方便 XD），如果你電腦上沒有 Mathematica，也可以用 Wolfram Alpha 來算。所以我們現在知道
\[M^{201 \uparrow\uparrow 3} \equiv M^{153}\]

只差最後臨門一腳啦！~~櫻花妹我來了！！！~~抽出原題目被轉亂的字串，重新轉正。

import rubiks

ciphertext = 'Ipwgo..uactousw! uilo  thw: ak.y ft S-tonw/r_/aoscysiai o.o _ttltuuennn.ojkilk. GTadh/selh rCSpF'

# PowerMod[201, 201^201, 1008] = 153
v = [c for c in ciphertext]
for i in range(153):
    v = rubiks.rotate(v, rubiks.M)

print ''.join(v)

import rubiks

ciphertext = 'Ipwgo..uactousw! uilo thw: ak.y ft S-tonw/r_/aoscysiai o.o _ttltuuennn.ojkilk. GTadh/selh rCSpF'

# PowerMod[201, 201^201, 1008] = 153

v = [c for c in ciphertext]

for i in range(153):

v = rubiks.rotate(v, rubiks.M)

print ''.join(v)

BINGO!

Congratulations!Follow the link.http://www.is.s.u-tokyo.ac.jp/ist_ueno_yuuka    GradSch of  IST

1	Congratulations!Follow the link.http://www.is.s.u-tokyo.ac.jp/ist_ueno_yuuka GradSch of IST

跟著這個連結進去可以聽到一首歌。

最後引用一句 up-arrow notation 發明人的話

Beware of bugs in the above code; I have only proved it correct, not tried it.
— Donald Knuth

我也要說，上面的程式碼雖然在我這裡可以跑，但不保證到其他地方能用。 XD

後記

其實這是一篇測試文。 XD
當初就在想說到底要用什麼樣的主題，才能夠用一篇文章把所有的東西都測過一遍。看來這個主題是挑得不錯，幾乎所有的排版元素和功能都測到了。哈！
喔對了！還有一件事情我一定要補充一下，就是海報和連結裡面的那個女生根本是高中生，請不要以為東大裡面會有這種年輕可愛的美眉。（東大你騙得我好苦啊 QQ）

5 Comments for “東京大学 2013 年小遊戲解析”

kenqq

says:

你好,我是做完題目之後,用答案去搜索到貴站的^^
那個153我沒算出來直接跑答案的,我想請教一下計算那個1008的過程,感謝啦~

沒事打擾啦,我突然想到怎麼算了,打擾了

Kuan-Yi Li

No worries! 有些地方我的確是跳得比較快，有任何問題都可以提出來討論。而且我也蠻好奇你所謂直接跑答案的方法是什麼，是一直做 THEUNIVERSITYOFTOKYO 然後用人眼看的意思嗎？

是的,我把輸出的格式弄成每一個側面的字母鏈接成一行字符串,然後用逗號隔開,把結果複製到csv文件裡面看哪條包含有意思單詞的OTL

之後參考了您的方法之後,就把第一行生成的字符串和之後的每一行做判斷,的確會得出n=1008會重複的現象,現在想起來真是太笨了(黑線

了解，直接看也不失為一個方法。話說壓根沒想到會有人研究這篇文章，看到讀者有收穫真的很開心。 ^_^

後記

5 Comments for “東京大学 2013 年小遊戲解析”

Leave a Reply Cancel reply