Lambdaカクテル

京都在住Webエンジニアの日記です

@xtetsuji さんからの出題をやってみる (Common Lispと数学編)

Twitterをやっていたら, id:anatofuz くんがおもしろ問題をやっていた.Perl入学式で出題されたらしい.

anatofuz.hatenablog.com

問題はこういうの.

大人気なくもやってみたくなりました.

Perlはみんなやっているでしょうから,ループをごりごり回すのはCommon Lispの得意技(要出典)なので書いてみましょう.

gist.github.com

だいたいこういう感じになりました.loopマクロだとちょっと不足なのでiterateライブラリを使っています.

感想

完走した感想ですが・・・

iterマクロ

まずiterマクロの強力さがすばらしいですね.

common-lisp.net

繰り返し処理だけに特化した,非常によくできたライブラリです.ほぼこれで完結しています.

隅っこ判定

ボールが隅っこにある判定がちょっとバンカラな感じになっています.

(until (or (and (eq x 1) (eq y 1))
                  (and (eq x 1) (eq y wy))
                  (and (eq x wx) (eq y 1))
                  (and (eq x wx) (eq y wy))))

これは

(member (list x y) `((1 1) (1 ,wy) (,wx 1) (,wx ,wy)))

ってふうにも書けてオシャレなのですが,ループするたびにメモリ確保されるのはう〜んいかんでしょというわけでボツです.こっちでもいい気がします.

数学

数学初心者なのですが,これ巡回群になりませんか?なんか賢い手法が使えそうな気がします.

いったん図にしてみます.

f:id:Windymelt:20200726190220p:plain
実行結果.数字はステップ数

緑のマスはビリヤードのポケット,すなわち「ゴールマス」です.壁にぶつかる度に方向が跳ね返っています.ゴールマスに到達したら終わりです.

マス目が無限に広がる場合について考える

ここでボールの座標に着目します.話を簡単にするために,ステップは0から始まるものとし,行・列の添字も0から始まるようにします. 壁にぶつかる度に増減の方向が反転するので,x軸(縦のマス)は\(0,1,2,1,0,1,2...\) といった数列になり,y軸(横のマス)は\(0,1,2,3,4,5,4,3,2,1,0,...\)といった数列になることがわかります.

そこで,「x軸は0〜2まで」「y軸は0〜5まで」という制限を取り払って,「x軸は0〜2で振動しながら永遠に伸びている」「y軸は0〜5で振動しながら永遠に伸びている」と考えてみます.これを図にすると以下の通りです.

f:id:Windymelt:20200726191856p:plain
マス目の壁が消えた代わりに,それぞれの軸は振動する

最小公倍数

なんか九九の表みたいなものが見えませんか?ここがポイントです.実は,「0から数えた場合のステップ数が」「幅-1と高さ-1の最小公倍数になっている場合」に,なんとボールがポケットインしてしまうのだ!!!!!!! 幅と高さを\(w,h\)としたとき,今回の\(w,h=(6,3)\)のビリヤードは, \(LCM(w-1,h-1) = 10\) ステップ(0から数えた場合)でゴールします.プログラムによれば11回(1から数えた場合)でゴールすると表示されているので,今回の結果と合致しますね.

試しに\(80,50\)のビリヤードをしてみます.

...
3868: (76,46)
3869: (77,47)
3870: (78,48)
3871: (79,49)
3872: (80,50)
GOAL!

1から数えて3872ステップかかりました. \(LCM(79,49)=3871\)なので,これも今回の結果と合致しますね.

そもそも「隅っこに入ったらゴール,それ以外の場合は跳ね返る」という構図自体が,最小公倍数を求める仕組みになっている,と考えることもできそうです. もう少し推し進めると,任意のステップ\(n\)を渡して座標を求める,といったこともできそうですが,今回は割愛します.

おわり

めでたし

貴様!この記事の筆者をフォローしてください!(しなさい)