PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 349 / ラングトンの蟻

黒白いずれかで色づけされた正方形の規則的な格子上をアリが動く。
アリは上下左右のいずれかを向いており,次のルールにしたがって隣接する正方形へ移動する。

  • 黒い正方形上にいる場合,その正方形の色を白に変えて反時計回りに向きを変え,1マス前進する
  • 白い正方形上にいる場合,その正方形の色を黒に変えて時計回りに向きを変え,1マス前進する

格子全体が白の状態から始めるとき,アリが 10^18 回動いた後の黒い正方形の数は何個あるか。

本家:Problem 349 - Project Euler
日本語訳:Problem 349 - PukiWiki

wikipediaで調べる

「ラングトンの蟻」は wikipedia に載っています。英語版のページに周期についての記述がありました。約一万ステップ後,周期104の動きを見せるようになるそうです。

  • After a few hundred moves, a big, irregular pattern of black and white squares appears. The ant traces a pseudo-random path until around 10,000 steps.
  • Finally the ant starts building a recurrent "highway" pattern of 104 steps that repeats indefinitely.

Langton's ant - Wikipedia

シミュレーション

mathematica による実装が Rosetta Code にありました。

Langton's ant - Rosetta Code

これをちょっといじって,104*100 ステップ後と104*105 ステップ後を見てみました。

これが104*100 ステップ後。
f:id:variee:20180614163952p:plain

次は104*105 ステップ後。
f:id:variee:20180614163947p:plain

左上に向かって伸びていく様子が見てとれます。次のようにして黒の数を調べてみたら,104ステップ毎に12ずつ増えていました。


計算

10^18 を104で割ると,商は 9615384615384615 で余りは 40 です。

40+104*100 ステップ後の黒の数は 772 なので,初項772,公差12の等差数列として計算して終了です。