東京大学 2013 年小遊戲解析

Posted on by

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

Poster_2013

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

首先用 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)

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

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

根據 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 = 
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

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

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

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

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

後記

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

Posted in Technical.

5 Comments

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

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

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

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

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

Leave a Reply

Your email address will not be published. Required fields are marked *

Captcha loading...