10パズル（４つの数字から四則演算で10を作る！）

## 10パズルの解を調べる！

peigのサイトに「10パズルについてコードで求められるんですか？」って質問があったので，``Julia``  の練習を兼ねて作ってみることにしました！

`Jupyter notebook`を使って行います。

まずは，wikiをチェック。

https://ja.wikipedia.org/wiki/テンパズル

まあ，当然調べ尽くされているわけです。

552通りと書いてあるので，そこに向かってコードを作成開始です！

wikiの中で，『逆ポーランド記法で表現する』とあったので，その方針でやってみることにしました。

## 逆ポーランド記法で数式を表現

まずは
http://rosettacode.org/wiki/Parsing/RPN_calculator_algorithm#Julia

のサイトで，逆ポーランド記法（RPN:Reverse Polish Notation）のコードをチェック

``parse``は通らなかったので，``Meta.parse``に直しました。（下記参照）

https://discourse.julialang.org/t/parse-in-julia-1-0/13273

```julia:rpn(s)
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$





```julia:ex1
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``を最後の結果だけ出るようにしました。

```julia:rpn2(s)
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))


```Julia:ex2
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になるケースはこんな感じです。

```Julia:ex2
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数のリストを得られそうです！


```Julia:test3
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通りです！

だいたい５分くらいの時間ですが，もっと，もっと短縮できると思うのですが，とりあえずです。

全体的に参考にしたサイトです。

https://hshindo.github.io/julia-doc-ja-v0.6/

https://qiita.com/ssh0/items/85da01474cafb855cfab

https://qiita.com/cometscome_phys/items/31d0b811345a3e12fcef#基本的な計算