WaniCTF'21-spring Automaton Lab. Writeup

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
>
```

ルール

https://en.wikipedia.org/wiki/Rule_30

に基づいて何世代か後のビットパターンを答える問題とわかった。

ソルバー書いてみる

```python: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
のデータの答えが途中で重複していないか確認
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1163572/8d244b75-de20-c762-f6db-cd5979298f8c.png)
ダメだ重複していない。

ここで一度，心が折れる。

翌日

計算可能な大きい世代でもう一度重複しないか確認する。
init = "000000000000101"
gen = 132767
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1163572/8b2278f7-a997-7e1a-a724-88c9034acac3.png)

10547 - 9092 = 1455
9092 - 7637 = 1455
7637 - 6182 = 1455
6182 - 4727 = 1455
4727 - 3272 = 1455
3271 - 1817 = 1455
1817 - 362 = 1455

1455周期だ。
剰余でいけるはず。
ソルバーを改良する

```python: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

https://github.com/wani-hackase/wanictf21spring-writeup/tree/main/mis/automaton-lab