make10

make10はテンパズルとも呼ばれるゲームです．

4桁の数字を一桁の数字4つとみなし，これに四則演算などを用いて10を作る遊び．

制約

入力は0〜9の4つの数を想定
計算は+ - ÷ × ( )のみを使用した四則演算のみ有効
累乗や負の数(-1など)は禁止
4つの数の順番を入れ替えることは可能
出力は通常の計算式で，すべての解を出力する

考え方

大前提として4つの数の順番を入れ替えることを可能としているので，数字を○，演算子を△とすると，以下の2通りに分類されると考える（証明してません）．この2式に対して数字と演算子の全ての組み合わせを検証することで，10を作ることが可能かを判定する．

((○ △ ○) △ ○) △ ○
(○ △ ○) △ (○ △ ○)

追記

実装後に上の2式では3つの演算子のいずれかが割り算だった場合，全通りを検証できていないことに気づいたため，3つの演算子のいずれかが割り算だった場合に限り，以下の3式を検証して10を作ることが可能か判定する．

(○ △ (○ △ ○)) △ ○
○ △ ((○ △ ○) △ ○)
○ △ (○ △ (○ △ ○))

実装

ここでは，4つの数をそれぞれn1, n2, n3, n4とし，3つの演算子をop1, op2, op3とする．

next_permutation()を使用して，順列の数え上げを行い，全探索を行う．
- 与えられた4つの数が入った配列をソートする
- next_permutation()を用いて返り値がfalseになるまで探索を行う．（重複するものについては自動的に飛ばしてくれるので考慮する必要はない）
ある順番の4つの数の間に入る3つの演算子を+ - ÷ ×の中から決定する．
- 3重ループを用いて探索．
4つの数と間に入る3つの演算子が決定したら，式を評価して10と等しければ((○ △ ○) △ ○) △ ○か(○ △ ○) △ (○ △ ○)の形で出力を行う．
- 前述の2式に4つの数と3つの演算子を代入して，10を作ることができれば出力する.
すべての組み合わせを探索し終わったらプログラムを終了する
- この時，10を作るパターンが1つも出力されていない場合はNot Foundを出力する．

計算量

10 ^ 4 * 4 ^ 4 = 2560000でおよそ10 ^ 6の定数倍となる．

ファイル構成

make10.cpp

メインのプログラムです．実装の説明などはこれの説明をしています．

make10-test.cpp

すべての入力パターンを評価して，10になるものが見つかり次第出力し，なければNot Foundを出力するプログラム．各入力パターンに対してすべての解を出力すると膨大な数になるため，各入力パターンにつき1つの解のみを出力するようにしている．

test.txt

すべての入力パターンが入っています．

ans.txt

make10-test.cppに入力としてtest.txtを入れた時の出力結果が入っている．

入出力

入力例1

1 2 3 4

出力例1

((1+2)+3)+4
(1+2)+(3+4)
((1×2)×3)+4
((1+2)+4)+3
(1+2)+(4+3)
((1+3)+2)+4
(1+3)+(2+4)
((1×3)×2)+4
((1+3)+4)+2
(1+3)+(4+2)
((1×3)×4)-2
((1+4)+2)+3
(1+4)+(2+3)
(1×4)+(2×3)
((1+4)+3)+2
(1+4)+(3+2)
(1×4)+(3×2)
((1×4)×3)-2
((2+1)+3)+4
(2+1)+(3+4)
((2×1)×3)+4
((2÷1)×3)+4
((2+1)+4)+3
(2+1)+(4+3)
((2+3)+1)+4
(2+3)+(1+4)
(2×3)+(1×4)
((2×3)×1)+4
((2×3)÷1)+4
((2+3)+4)+1
(2+3)+(4+1)
((2×3)+4)×1
(2×3)+(4×1)
((2×3)+4)÷1
(2×3)+(4÷1)
((2+4)+1)+3
(2+4)+(1+3)
((2×4)-1)+3
(2×4)-(1-3)
((2+4)+3)+1
(2+4)+(3+1)
((2×4)+3)-1
(2×4)+(3-1)
((3+1)+2)+4
(3+1)+(2+4)
(3-1)+(2×4)
((3×1)×2)+4
((3÷1)×2)+4
((3+1)+4)+2
(3+1)+(4+2)
(3-1)+(4×2)
((3-1)×4)+2
((3×1)×4)-2
((3÷1)×4)-2
((3+2)+1)+4
(3+2)+(1+4)
(3×2)+(1×4)
((3×2)×1)+4
((3×2)÷1)+4
((3÷2)+1)×4
((3+2)+4)+1
(3+2)+(4+1)
((3×2)+4)×1
(3×2)+(4×1)
((3×2)+4)÷1
(3×2)+(4÷1)
((3+4)+1)+2
(3+4)+(1+2)
(3×4)-(1×2)
((3×4)×1)-2
((3×4)÷1)-2
((3+4)+2)+1
(3+4)+(2+1)
((3×4)-2)×1
(3×4)-(2×1)
((3×4)-2)÷1
(3×4)-(2÷1)
((4+1)+2)+3
(4+1)+(2+3)
(4×1)+(2×3)
(4÷1)+(2×3)
((4+1)+3)+2
(4+1)+(3+2)
(4×1)+(3×2)
((4×1)×3)-2
(4÷1)+(3×2)
((4÷1)×3)-2
((4+2)+1)+3
(4+2)+(1+3)
((4×2)-1)+3
(4×2)-(1-3)
((4+2)+3)+1
(4+2)+(3+1)
((4×2)+3)-1
(4×2)+(3-1)
((4+3)+1)+2
(4+3)+(1+2)
(4×3)-(1×2)
((4×3)×1)-2
((4×3)÷1)-2
((4+3)+2)+1
(4+3)+(2+1)
((4×3)-2)×1
(4×3)-(2×1)
((4×3)-2)÷1
(4×3)-(2÷1)

入力例2

1 1 9 9

出力例2

((1÷9)+1)×9

入力例3

1 1 1 1

出力例3

Not Found

実行

c++の実行環境がある場合(mac, clang)

git clone <this repo>
cd <this repo>
g++ make10.cpp
./a.out

Cork0158/make10