24 game/Solve: Difference between revisions
m
→{{header|Phix}}: added syntax colouring the hard way
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
Line 5,931:
=={{header|Phix}}==
<!--<lang Phix>-->
<span style="color: #000080;font-style:italic;">-- demo\rosetta\24_game_solve.exw
--
-- The following 5 parse expressions are possible.
-- Obviously numbers 1234 represent 24 permutations from
-- {1,2,3,4} to {4,3,2,1} of indexes to the real numbers.
-- Likewise "+-*" is like "123" representing 64 combinations
-- from {1,1,1} to {4,4,4} of indexes to "+-*/".
-- Both will be replaced if/when the strings get printed.
-- Last hint is because of no precedence, just parenthesis.
--</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">OPS</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"+-*/"</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">expressions</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"1+(2-(3*4))"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"1+((2-3)*4)"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"(1+2)-(3*4)"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"(1+(2-3))*4"</span><span style="color: #0000FF;">,</span>
<span style="color: #008000;">"((1+2)-3)*4"</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- (equivalent to "1+2-3*4")
-- The above represented as three sequential operations (the result gets
-- left in <(map)1>, ie vars[perms[operations[i][3][1]]] aka vars[lhs]):</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">operations</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'*'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'-'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},</span> <span style="color: #000080;font-style:italic;">--3*=4; 2-=3; 1+=2</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'-'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'*'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}},</span> <span style="color: #000080;font-style:italic;">--2-=3; 2*=4; 1+=2</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'*'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'-'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">}},</span> <span style="color: #000080;font-style:italic;">--1+=2; 3*=4; 1-=3</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'-'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'*'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">}},</span> <span style="color: #000080;font-style:italic;">--2-=3; 1+=2; 1*=4</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'+'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'-'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'*'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">}}}</span> <span style="color: #000080;font-style:italic;">--1+=2; 1-=3; 1*=4</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">evalopset</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">opset</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ops</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- invoked 5*24*64 = 7680 times, to try all possible expressions/vars/operators
-- (btw, vars is copy-on-write, like all parameters not explicitly returned, so
-- we can safely re-use it without clobbering the callee version.)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rhs</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">opset</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">opset</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">lhs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ops</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">OPS</span><span style="color: #0000FF;">)]</span>
<span style="color: #000000;">rhs</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'+'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'-'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'*'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">op</span><span style="color: #0000FF;">=</span><span style="color: #008000;">'/'</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">1e300</span><span style="color: #0000FF;">*</span><span style="color: #000000;">1e300</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">/=</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">rhs</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">lhs</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nSolutions</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">xSolutions</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">success</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">expr</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ops</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expr</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">expr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">>=</span><span style="color: #008000;">'1'</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;"><=</span><span style="color: #008000;">'9'</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">expr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">[</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">-</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">]]+</span><span style="color: #008000;">'0'</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">OPS</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ch</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">expr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ops</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">xSolutions</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- avoid duplicates for eg {1,1,2,7} because this has found
-- the "same"
-- and likewise whenever an operator is used more than once.</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"success: %s = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">expr</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)})</span>
<span style="color: #000000;">nSolutions</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">xSolutions</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xSolutions</span><span style="color: #0000FF;">,</span><span style="color: #000000;">expr</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">tryperms</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ops</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">operations</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- 5 parse expressions</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">evalopset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">operations</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ops</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">round</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1e9</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- fudge tricky 8/(3-(8/3)) case</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">24</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">success</span><span style="color: #0000FF;">(</span><span style="color: #000000;">expressions</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ops</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">tryops</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">ops</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">p</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- 24 var permutations</span>
<span style="color: #000000;">tryperms</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">}),</span><span style="color: #000000;">ops</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">global</span> <span style="color: #008080;">procedure</span> <span style="color: #000000;">solve24</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">vars</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">nSolutions</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #000000;">xSolutions</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">op1</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">op2</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">op3</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">4</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- 64 operator combinations</span>
<span style="color: #000000;">tryops</span><span style="color: #0000FF;">({</span><span style="color: #000000;">OPS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">op1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">OPS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">op2</span><span style="color: #0000FF;">],</span><span style="color: #000000;">OPS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">op3</span><span style="color: #0000FF;">]},</span><span style="color: #000000;">vars</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n%d solutions\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">nSolutions</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">solve24</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">})</span>
<span style="color: #000080;font-style:italic;">--solve24({6,4,6,1})
--solve24({3,3,8,8})
--solve24({6,9,7,4})</span>
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">wait_key</span><span style="color: #0000FF;">()</span>
<!--</lang>-->
{{out}}
<pre>
|