從 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
一共是 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.
看來是個 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|
+-----------+
那 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|
+-----------+
只要建立個對照表，讓程式知道如何根據舊狀態建立新狀態就好了。
寫程式囉#
轉換了問題之後，程式的撰寫就變得簡單了。為了方便起見，我是把它寫成 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])
回到一開始的問題，那我麼要怎麼樣簡化那 $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
跑完得到 $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)
BINGO!
Congratulations!Follow the link.http://www.is.s.u-tokyo.ac.jp/ist_ueno_yuuka GradSch of IST
跟著這個連結進去可以聽到海報娘上野優華的新歌──Summer Prism。
最後引用一句 up-arrow notation 發明人的話
Beware of bugs in the above code; I have only proved it correct, not tried it.
—Donald Knuth
我也要說，上面的程式碼雖然在我這裡可以跑，但不保證到其他地方能用。 😁
後記#
其實這是一篇測試文。 😝
當初就在想說到底要用什麼樣的主題，才能夠用一篇文章把所有的東西都測過一遍。看來這個主題是挑得不錯，幾乎所有的排版元素和功能都測到了。哈！
喔對了！還有一件事情我一定要補充一下，就是海報和連結裡面的那個女生根本是高中生，請不要以為東大裡面會有這種年輕可愛的美眉。（東大你騙得我好苦啊 😭）