Kawazoe(@riverplus)さんのCodeIQの問題です。
元のページはリンク切れしていますが、こちらに問題と解答、解説が載っています。
ー>https://oraclesqlpuzzle.ninja-web.net/kyoupro-old/kyoupro-04-002.html
問題
n 個のリールを持ち、各リールには、0 から 9 のいずれかの数字がランダムに出る
スロットマシンを回します。
このとき最も多く出現した数字の出現回数に等しいドルが賞金として得られます。
例えばn=6のスロットマシンで、左から順に775107という数字が出たとします。
このとき、7の数字が最も多く3回出現していますので、賞金は3ドルです。
このスロットマシンを 1 回まわしたときの賞金の期待値を F(n) とします
■ 第1問 (Normal)
F(6) の値を求めて下さい(四捨五入は不要です)。
■ 第2問 (Hard)
F(12) の値を求めて下さい(四捨五入は不要です)。
こちらにも情報があります。 (2026年5月2日9時32分追加)
->https://posfie.com/@riverplus/p/msGCRTy
異なる (n) 個から (r) 個を選ぶ方法の数(nCr)を使います。
m列のマシンのi列の組み合わせはm列からi列を選ぶmCiです。
これはJuliaではbinomial(m,i)で求めます。
i列の数がj個あると、その組合せの数はmCi*(m-i)Ci*..(m-i*j)Ci(k+j-1)Cj
(k+j-1)Cjは最多がi列のとき残っていた数字からj個を選ぶ組みあわせの数です。
(列の場所のほうが順序付きになっています)
g(m,i,j,k)はm列のマシンで最多がi列、i列の組ががj個目、
まだ出てきていない数がk個という意味です。
i列の次は①i列g(m-i,i,j+1,k-1)と②1からi-1列g(m-i,h,1,k-1)に分けて足します。
① (m,i,j,k)での組み合わせの数mCiとg(m-i,i,j+1,k-1)の積
②mCiに、i列の組がj個で終わったときの(k+j-1)Cjを掛けさらに
最多の列hが0~i-1列までのg(m,h,1,k)の和を掛けます。
m==iの時にbinomial(m,i)*binomial(k+j-1,j)をかえします。
期待値ですので最多の列がiの場合の組み合わせの数g(n,i,1,10)に
iを掛けてi = 1~nの和を取り全体の組み合わせの数で割ります。
#julia ver 1.41,1.53,1.85,1.12.1
function solve(n,a)
function g(m,i,j,k)
if m == i return binomial(m,i)*binomial(k+j-1,j) #binomial(m,i)=1
elseif m < i || k <= 0 || i <= 0 return 0
end
sm = sum(h -> g(m-i, h, 1, k-1), 1:(i-1), init=0)
return binomial(m,i)*(g(m-i,i,j+1,k-1)+binomial(k+j-1,j)*sm)
end
tsum = sum(i -> g(n,i,1,10)*i,1:n)
ans = tsum/10^n
s = ans == a ? "ok " : "no "
println(s,ans)
end
solve(6,2.01966)
solve(12,3.10849098132)
私はlisp系は苦手なのですが、最近Janetというのを知り興味を持っています。
今はAIがありますのでその助けを借りて、Juliaで書いたのをJanetに移植しました。
私はvscodeを使っていますがplaygroundもあります。
->https://janetdocs.org/playground/example/600
今回もAIにJanetの簡単な紹介をしてもらいます。
Janetは、軽量で組み込みやスクリプト用途に強いLisp系プログラミング言語です
-
「ほぼLisp」だが、馴染みやすいデータ構造
伝統的なLispのリスト(Consセル)ではなく、現代的な配列(Array)と
バッファ(Buffer)、テーブル(Hash Map)、構造体(Struct)を
ネイティブでサポートしています。 -
強力な抽象化:マクロとPEG
マクロ:
Lisp最大の武器であるコード生成能力をフルに活用できます。
PEG (Parsing Expression Grammar):
標準ライブラリに非常に強力なPEGパーサーが組み込まれています。
正規表現よりも読みやすく、複雑な構文解析を驚くほど簡潔に
記述できるため、スクレイピングやDSL 作成に最適です。 -
高度な制御フロー:Fiber(ファイバー)
JanetはFiberによるコルーチンをネイティブサポートしています。
例外処理や動的スコープ、そして非同期プログラミングを、
軽量かつ一貫したメカニズムで制御可能です。
AIはほしい関数が見つからないときに教えてくれますし、どうしてもバグが
見つからないとき、点の間違いまで教えてくれるのでべんりです。
しかし存在しない関数も教えてくれますし、解決しない問題の解決法を
延々と提示してくるので要注意です。
さて、このコードでは(k+j-1)Cjを各列に分散してk/jをかけています。
誤差が出るかと思いましたが、この問題では大丈夫でした。
#v1.41.2
(defn ncr [n k]
(cond
(or (< k 0) (> k n)) 0
(= k 0) 1
(= k 1) n
true (div (* n (ncr (- n 1) (- k 1))) k)))
(defn gn [m i j k]
(cond
(= m i) (/ k j)
(or (<= m 0) (<= i 0) (<= k 0)) 0
:else
(do
(def total (sum (generate [h :range [1 i]]
(gn (- m i) h 1 (- k 1)))))
#janetの範囲は [ ),1>iの時sum=0になる
(* (/ (* (ncr m i) k) j) (+ (gn (- m i) i (+ j 1) (- k 1)) total))
)))
(defn slot [n a]
(def tsum (sum (generate [i :range [1 (+ n 1)]]
(* (gn n i 1 10) i))))
(def ans (/ tsum (math/pow 10 n)))
(def s (if (= ans a) "ok " "no "))
(printf " %s -> %.12f" s ans))
(slot 6 2.01966)
(slot 12 3.10849098132)
ところでswi-prologには 有理数があります。
N rdiv Kとすると結果が整数にならないとそのまま保持されますので
誤差が出ません。
%SWI-Prolog ver 7.42,7.64,9.29
%:-initialization(start). %ideone,Online Prolog Compiler
%start.
ncr(K,_,I,R,R):-I>K,!.
ncr(K,N,I,R1,R):-
R2 is (R1*N) div I,N1 is N-1,I1 is I+1,ncr(K,N1,I1,R2,R).
g(M,M,J,K,R):-!,R is K rdiv J.
g(M,I,_,K,0):-(M<I;K=<0;I=<0),!.
g(M,I,J,K,R):-
I1 is I-1,M1 is M-I,J1 is J+1,K1 is K-1,
(I1>0->(findall(X,(between(1,I1,H),g(M1,H,1,K1,X)),L1),
sum_list(L1,R1));R1 = 0),
g(M1,I,J1,K1,R2),ncr(I,M,1,1,R3),R is R3*(K rdiv J)*(R2 +R1).
solve(N,R):-
findall(X,(between(1,N,I),g(N,I,1,10,Y),
X is Y*I),L1),sum_list(L1,R1),R is R1/10^N.
start:-
f(N,A),(solve(N,R)->(R==A->Str=" ok ";Str=" no ");write(fail)),
write(" "),write(Str),writeln(N->R),fail.
start.
f(6,2.01966).
f(12,3.10849098132).