Rosetta Code

Solve triangle solitaire puzzle: Difference between revisions

Page Discussion

Solve triangle solitaire puzzle (view source)

Revision as of 14:25, 25 March 2021

15,694 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way, phix/basics
(Added Wren)
m (→‎{{header|Phix}}: added syntax colouring the hard way, phix/basics)
Line 1,391:
 
=={{header|Phix}}==
{{libheader|Phix/basics}}
Twee brute-force string-based solution. Backtracks a mere 366 times, whereas starting with the 5th peg missing backtracks 19388 times (all in 0s, obvs).
 
<lang Phix>--
<!--<lang Phix>-->
-- demo\rosetta\IQpuzzle.exw
<span style="color: #000080;font-style:italic;">-- demo\rosetta\IQpuzzle.exw</span>
--
<span style="color: #008080;">constant</span> <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{-</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">11</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span>
constant moves = {-11,-9,2,11,9,-2}
<span style="color: #008080;">function</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">)</span>
function solve(string board, integer left)
<span style="color: #008080;">if</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008000;">""</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if left=1 then return "" end if
<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;">board</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
for i=1 to length(board) do
<span style="color: #008080;">if</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'1'</span> <span style="color: #008080;">then</span>
if board[i]='1' then
<span style="color: #008080;">for</span> <span style="color: #000000;">j</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;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
for j=1 to length(moves) do
<span style="color: #004080;">integer</span> <span style="color: #000000;">mj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">over</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">mj</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tgt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">mj</span>
integer mj = moves[j], over = i+mj, tgt = i+2*mj
<span style="color: #008080;">if</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
if tgt>=1 and tgt<=length(board)
<span style="color: #008080;">and</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tgt</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">and</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">over</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'1'</span> <span style="color: #008080;">then</span>
and board[tgt]='0' and board[over]='1' then
<span style="color: #0000FF;">{</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">over</span><span style="color: #0000FF;">],</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tgt</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"001"</span>
{board[i],board[over],board[tgt]} = "001"
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #000000;">left</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
string res = solve(board,left-1)
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">4</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">&</span><span style="color: #000000;">res</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if length(res)!=4 then return board&res end if
<span style="color: #0000FF;">{</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">over</span><span style="color: #0000FF;">],</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tgt</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"110"</span>
{board[i],board[over],board[tgt]} = "110"
<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;">if</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">return</span> <span style="color: #008000;">"oops"</span>
return "oops"
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
end function
<span style="color: #004080;">sequence</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
sequence start = """
----0----
---1-1---
--1-1-1--
-1-1-1-1-
1-1-1-1-1
"""</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">substitute</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">start</span><span style="color: #0000FF;">&</span><span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">start</span><span style="color: #0000FF;">,</span><span style="color: #000000;">14</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">),</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">))</span>
puts(1,substitute(join_by(split(start&solve(start,14),'\n'),5,7),"-"," "))</lang>
<!--</lang>-->
 
{{out}}
<pre>
Line 1,437 ⟶ 1,440:
1 0 0 1 1 1 0 0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0
</pre>
Adapted to the English game (also in demo\rosetta\IQpuzzle.exw):
 
<lang Phix>constant moves = {-2,15,2,-15}
<!--<lang Phix>-->
function solve(string board, integer left)
<span style="color: #008080;">constant</span> <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">15</span><span style="color: #0000FF;">}</span>
if left=1 then
<span style="color: #008080;">function</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">)</span>
-- return "" -- (leaves it on the edge)
<span style="color: #008080;">if</span> <span style="color: #000000;">left</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
if board[3*15+8]='.' then return "" end if
<span style="color: #000080;font-style:italic;">-- return "" -- (leaves it on the edge)</span>
return "oops"
<span style="color: #008080;">if</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">*</span><span style="color: #000000;">15</span><span style="color: #0000FF;">+</span><span style="color: #000000;">8</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'.'</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #008000;">""</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">return</span> <span style="color: #008000;">"oops"</span>
for i=1 to length(board) do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if board[i]='.' then
<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;">board</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
for j=1 to length(moves) do
<span style="color: #008080;">if</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'.'</span> <span style="color: #008080;">then</span>
integer mj = moves[j], over = i+mj, tgt = i+2*mj
<span style="color: #008080;">for</span> <span style="color: #000000;">j</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;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
if tgt>=1 and tgt<=length(board)
<span style="color: #004080;">integer</span> <span style="color: #000000;">mj</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">over</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">mj</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tgt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">mj</span>
and board[tgt]='o' and board[over]='.' then
<span style="color: #008080;">if</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">tgt</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">)</span>
{board[i],board[over],board[tgt]} = "oo."
<span style="color: #008080;">and</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tgt</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'o'</span> <span style="color: #008080;">and</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">over</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'.'</span> <span style="color: #008080;">then</span>
string res = solve(board,left-1)
<span style="color: #0000FF;">{</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">over</span><span style="color: #0000FF;">],</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tgt</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"oo."</span>
if length(res)!=4 then return board&res end if
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">board</span><span style="color: #0000FF;">,</span><span style="color: #000000;">left</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
{board[i],board[over],board[tgt]} = "..o"
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">4</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">board</span><span style="color: #0000FF;">&</span><span style="color: #000000;">res</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #0000FF;">{</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">over</span><span style="color: #0000FF;">],</span><span style="color: #000000;">board</span><span style="color: #0000FF;">[</span><span style="color: #000000;">tgt</span><span style="color: #0000FF;">]}</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"..o"</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
return "oops"
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #008000;">"oops"</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
sequence start = """
-----.-.-.----
<span style="color: #004080;">sequence</span> <span style="color: #000000;">start</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
-----.-.-.----
-.-.-.-.-.-.-.----
-.-.-.-o-.-.-.----
-.-.-.-.-.-.-.
-.-.-.-o-.-.-.----
-.-.--.-.-.-.----.
-----.-.-.----
"""
-----.-.-.----
puts(1,substitute(join_by(split(start&solve(start,32),'\n'),7,8),"-"," "))</lang>
"""</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">substitute</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">start</span><span style="color: #0000FF;">&</span><span style="color: #000000;">solve</span><span style="color: #0000FF;">(</span><span style="color: #000000;">start</span><span style="color: #0000FF;">,</span><span style="color: #000000;">32</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">),</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">),</span><span style="color: #008000;">"-"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">))</span>
<!--</lang>-->
 
{{out}}
<pre>
Petelomax
7,806

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/250935"