python等のプログラミング力と問題解決力が問われた問題。
一度は心を折られたが，あきらめずにチャレンジして解いた記憶に残る問題。
最近はやりの，English only の問題ですね。
Big welcome です。
問題
Automaton Lab.
262pt Normal
Automaton Lab.で将来予測のお手伝いをしましょう <--日本語混じってる
nc automaton.mis.wanictf.org 50020
reference: https://en.wikipedia.org/wiki/Rule_30
Solution
ncしてみる
$ nc automaton.mis.wanictf.org 50020
Welcome to Automaton Lab.!
We study about automaton in there, here is the space of "Rule 30"[1] automaton.
We breed 15 cells automaton now, they are ring-connected -- they are connected the first cell and the last cell.
Our interest is what this cute automaton grow up in future, we want your help to expect their growth.
[1]: https://en.wikipedia.org/wiki/Rule_30
For example, now automaton state is "100000100000001" ('1' is alive and '0' is dead) and in next generation they are "010001110000011".
generation state
0 100000100000001
1 010001110000011
2 011011001000110
We give you initial state(init) and generation(gen). You write down the state of this automaton of the nth generation in binary.
Are you ready?
(press enter key to continue)
ここで aaa と入力
aaa
OK! Here we go! The first question is warming up.
init = 010111100010000
gen = 7
>
ルール
に基づいて何世代か後のビットパターンを答える問題とわかった。
ソルバー書いてみる
solver.py
init = ”010111100010000”
gen = 7
i = 0
while i < gen:
ans = ""
j = 0
while j < 15:
chk = ""
if j == 0:
chk = init[14]+init[0]+init[1]
if j == 14:
chk = init[13]+init[14]+init[0]
if j >= 1 and j <= 13:
chk = init[j-1]+init[j]+init[j+1]
#print(chk)
if chk == '111':
ans = ans + "0"
if chk == '110':
ans = ans + "0"
if chk == '101':
ans = ans + "0"
if chk == '100':
ans = ans + "1"
if chk == '011':
ans = ans + "1"
if chk == '010':
ans = ans + "1"
if chk == '001':
ans = ans + "1"
if chk == '000':
ans = ans + "0"
j = j + 1
#print(ans)
init = ans
i = i + 1
print(ans)
実行した結果を入力してみると
> 111011101100001
Great! The second question is below.
init = 000011000000000
gen = 997
>
今度は 997 世代目だと
計算した結果を入れる。
> 110101111010111
Even if human become extinct, we wanna see the view of prosperity of cell automaton. This is last question.
init = 000000000000001
gen = 145180878248087930822675870521224824318594123419581197764296767187269329560188872269760488314219678660744026209365352834395821787688590524538339794462323979413816885896955061908051716263494446436907527717746123918714900672662822274220789622765357101233975574606429515821751260196625638309200227868630073832431
>
まだあるのか？
もはや計算できない世代数だ。
どうする？
15ビットしかないので同じビットパターンが出現しないか確認することに。
init = 000010000010000
gen = 997
のデータの答えが途中で重複していないか確認
ダメだ重複していない。
ここで一度，心が折れる。
翌日
計算可能な大きい世代でもう一度重複しないか確認する。
init = "000000000000101"
gen = 132767
10547 - 9092 = 1455
9092 - 7637 = 1455
7637 - 6182 = 1455
6182 - 4727 = 1455
4727 - 3272 = 1455
3271 - 1817 = 1455
1817 - 362 = 1455
1455周期だ。
剰余でいけるはず。
ソルバーを改良する
solver_kai.py
init = "000000000000001"
gen = 145180878248087930822675870521224824318594123419581197764296767187269329560188872269760488314219678660744026209365352834395821787688590524538339794462323979413816885896955061908051716263494446436907527717746123918714900672662822274220789622765357101233975574606429515821751260196625638309200227868630073832431
gen = gen % 1455 # この一行が全て！
i = 0
while i < gen:
ans = ""
j = 0
while j < 15:
chk = ""
if j == 0:
chk = init[14]+init[0]+init[1]
if j == 14:
chk = init[13]+init[14]+init[0]
if j >= 1 and j <= 13:
chk = init[j-1]+init[j]+init[j+1]
#print(chk)
if chk == '111':
ans = ans + "0"
if chk == '110':
ans = ans + "0"
if chk == '101':
ans = ans + "0"
if chk == '100':
ans = ans + "1"
if chk == '011':
ans = ans + "1"
if chk == '010':
ans = ans + "1"
if chk == '001':
ans = ans + "1"
if chk == '000':
ans = ans + "0"
j = j + 1
#print(ans)
init = ans
i = i + 1
print(ans)
nc に答えを投げてみる
> 001011010110011
Jesus!!! Are you the genius of future sight? We award you the special prize.
FLAG{W3_4w4rd_y0u_d0c70r473_1n_Fu7ur3_S1gh7}
ビンゴ！
作問者writeup