Catalan numberを知らないLisperが妻に負けるまで
Description
先日、カフェで妻と算数パズルを一緒にやっていたんだけど、確かこんな問題だった。
表と裏が出た回数が同じになるまでコイン投げをします。
最初の2回は続けて表が出ました。
ちょうど10回目で終了するような表裏の出方は何通りあるでしょうか。
Parenのコードは一瞬で浮かんだのに、肝心の解き方が思いつかない。そうこうしているうちに妻に解かれてしまい惨敗。
しょうがないのでここに供養する。（久しぶりにプログラム書いたな。）
(<- $result nil)
(function toss-coin (histories)
(let (toss-count (len histories)
heads-count (count (partial = 'heads) histories)
tails-count (- toss-count heads-count))
(if (&& (= toss-count 10) (= heads-count tails-count)) (push! (reverse histories) $result)
(&& (< toss-count 10) (!= heads-count tails-count))
(begin (toss-coin (cons 'heads histories))
(toss-coin (cons 'tails histories))))))
(toss-coin '(heads heads))
(write (len $result))
(foreach write $result)
14
(heads heads tails heads tails heads tails heads tails tails)
(heads heads tails heads tails heads heads tails tails tails)
(heads heads tails heads heads tails tails heads tails tails)
(heads heads tails heads heads tails heads tails tails tails)
(heads heads tails heads heads heads tails tails tails tails)
(heads heads heads tails tails heads tails heads tails tails)
(heads heads heads tails tails heads heads tails tails tails)
(heads heads heads tails heads tails tails heads tails tails)
(heads heads heads tails heads tails heads tails tails tails)
(heads heads heads tails heads heads tails tails tails tails)
(heads heads heads heads tails tails tails heads tails tails)
(heads heads heads heads tails tails heads tails tails tails)
(heads heads heads heads tails heads tails tails tails tails)
(heads heads heads heads heads tails tails tails tails tails)
再帰はLisperのお家芸ですな。
件数を出力しなくていいならグローバル変数なしでもっとキレイに書けるんだからねっ！
余談だけど、チャッピーに聞いてみたら「最初と最後の1手を除けば、残りは長さ8のDyck pathと1対1に対応します。よってCatalan number \( C_4 = \frac{1}{5} \binom{8}{4} = 14 \) です」と即答されてしまった。
そんなん知らんわ笑
というわけで、Claude先生に図を描いて解説してもらいました。
各点の数字はそこに至る経路の数で、左から足していくと最後に14になると。なるほど、分かりやすい。
すげー時代だ…。
Source code
Notes
折角なので、Claude先生に私の書いたコードをレビューしてもらいましょう。
> coin-toss.pをレビューして。
● Bash(cat -n coin-toss.p ...)
● Bash(paren coin-toss.p ...)
● 問題ありません。手元のParenで coin-toss.p を実行すると正常に終了し、出力は記事に載せた14行と1文字も違いませんでした。記事中のコードと coin-toss.p の中身も同じです。
ロジックも合っています。
- 10回に達し、表と裏が同数になったら記録します。
- まだ10回未満で、表と裏が同数でなければ、表と裏の両方に枝分かれして続けます。
- それ以外、つまり10回より前に同数になって終わった場合や、10回で同数にならなかった場合は、そこで打ち切ります。
histories は新しい投げ結果を先頭に足していくので、記録するときに reverse して時系列の順に戻しています。ここも正しく処理されています。
直すほどではありませんが、次の点だけ挙げておきます。
- 10 が2か所に直接書かれています。(<- $tosses 10) のように定数にすると、回数を変えて試すときに楽です。ただ、記事のコードとしては今のほうが読みやすいので、そのままで良いと思います。
- 呼び出しのたびに count でリストを数え直しています。10回程度なので気にする必要はありません。
- グローバル変数 $result を使っている点は、記事のネタ（「グローバル変数なしでもっとキレイに書ける」）にもなっているので、このままが正解です。
公開して大丈夫です。
✻ Cogitated for 16s · done 21:33
> 生意気だね。lisperは計算コストについては考えないのですよ。よく覚えておくように笑
● 失礼しました笑 Lisperは計算の速さより書き方の美しさを大事にする、と覚えておきます。
おしまい笑