10パズルの解を調べる！
peigのサイトに「10パズルについてコードで求められるんですか？」って質問があったので，Julia の練習を兼ねて作ってみることにしました！
Jupyter notebookを使って行います。
まずは，wikiをチェック。
まあ，当然調べ尽くされているわけです。
552通りと書いてあるので，そこに向かってコードを作成開始です！
wikiの中で，『逆ポーランド記法で表現する』とあったので，その方針でやってみることにしました。
逆ポーランド記法で数式を表現
まずは
http://rosettacode.org/wiki/Parsing/RPN_calculator_algorithm#Julia
のサイトで，逆ポーランド記法（RPN:Reverse Polish Notation）のコードをチェック
parseは通らなかったので，Meta.parseに直しました。（下記参照）
function rpn(s)
stack = Any[]
for op in map(eval, map(Meta.parse, split(s)))
if isa(op, Function)
arg2 = pop!(stack)
arg1 = pop!(stack)
push!(stack, op(arg1, arg2))
else
push!(stack, op)
end
println("$op: ", join(stack, ", "))
end
length(stack) != 1 && error("invalid RPN expression $s")
return stack[1]
end
例1
$(3+4)\times(1+2)$
$(3+4+5)\div 2$
In [22]:rpn("3 4 + 1 2 + *")
3: 3
4: 3, 4
+: 7
1: 7, 1
2: 7, 1, 2
+: 7, 3
*: 21
Out[22]:21
In[35]:rpn("3 4 + 5 + 2 /")
3: 3
4: 3, 4
+: 7
5: 7, 5
+: 12
2: 12, 2
/: 6.0
Out[35]:6.0
#println("$op: ", join(stack, ", "))をコメントアウトし，rpn2を最後の結果だけ出るようにしました。
function rpn2(s)
stack = Any[]
for op in map(eval, map(Meta.parse, split(s)))
if isa(op, Function)
arg2 = pop!(stack)
arg1 = pop!(stack)
push!(stack, op(arg1, arg2))
else
push!(stack, op)
end
#println("$op: ", join(stack, ", "))
end
length(stack) != 1 && error("invalid RPN expression $s")
return stack[1]
end
In[172]:rpn2("3 4 + 5 + 2 +")
Out[172]:14
In [173]:rpn2("3 4 + 5 + 2 /")
Out[173]:6.0
１０パズルの演算について
１０パズルでの演算は３通りとなります。
演算パターンは数を①②③④，演算子を ∗（ + ， − ， × ， ÷）とすると
((①∗1②)∗2③)∗3④
(①∗1②)∗2(③∗3④)
①∗1(②∗2(③∗3④))
となります。逆ポーランド記法で書くと，順に，
①②∗1③∗2④∗3
①②∗1③④∗3∗2
①②③④∗3∗2∗1
です。
例2
(1) ((1+2)*3)-4
(2) (1+2)*(3-4)
(3) 1-(2*(3+4))
In [45]:rpn2("1 2 + 3 * 4 -")
Out[45]:5
In [46]:rpn2("1 2 + 3 4 - *")
Out[46]:-3
In [47]:rpn2("1 2 3 4 + * -")
Out[47]:-13
割り算で，分母が0になるケースはこんな感じです。
In [50]:rpn2("1 1 - 3 3 - /")
Out[50]:NaN
In [52]:rpn2("1 2 - 3 3 - /")
Out[52]:-Inf
In [53]:rpn2("5 2 - 3 3 - /")
Out[53]:Inf
-
①②③④の並びは$10^4=1000$通りです。
-
*1 *2 *3の並びは$4^3=64$通りです。
-
演算のパターンは前述の３通りです。
よって，$10000\times 64\times 3=1920000$通りを四則演算で10になるかをチェックすればOKです。
あとは，10になったケースで4つの数を小さい順に並べ，重複を取り除けば，四則演算で10になる4数のリストを得られそうです！
function test3()
stack=Any[]
mklist=["+","-","*","/"]
for i=0:9,j=0:9,k=0:9,l=0:9,mk1∈ mklist,mk2∈ mklist,mk3∈ mklist
if rpn2("$i $j $mk1 $k $mk2 $l $mk3")==10
push!(stack, sort([i,j,k,l]))
elseif rpn2("$i $j $mk1 $k $l $mk2 $mk3")==10
push!(stack, sort([i,j,k,l]))
elseif rpn2("$i $j $k $l $mk1 $mk2 $mk3")==10
push!(stack, sort([i,j,k,l]))
else
end
end
# println(m)
m=unique(stack)
n=length(m)
println(n)
for i=1:n
println(m[i][1],m[i][2],m[i][3],m[i][4])
end
end
test3()
552
0019
0025
0028
0037
.
.
.
4499
7899
8999
9999
バッチリ，552通りです！
だいたい５分くらいの時間ですが，もっと，もっと短縮できると思うのですが，とりあえずです。
全体的に参考にしたサイトです。