Rosetta Code

A* search algorithm: Difference between revisions

Page Discussion

A* search algorithm (view source)

Revision as of 11:57, 26 March 2021

51,089 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
No edit summary
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 2,738:
barriers are simply avoided, rather than costed at 100.
Note that the 23 visited nodes does not count walls, but with them this algorithm exactly matches the 35 of Racket.
 
<lang Phix>sequence grid = split("""
<!--<lang Phix>-->
x:::::::
<span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"""
::::::::
x::::::###:
::::#:::#:
::#:::###:
::####:::#:
::#:::::#:
:::::::#####:
::::::::
""",'\n')
::::::::
"""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
constant permitted = {{-1,-1},{0,-1},{1,-1},
{-1, 0}, {1, 0},
<span style="color: #008080;">constant</span> <span style="color: #000000;">permitted</span> <span style="color: #0000FF;">=</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;">0</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;">1</span><span style="color: #0000FF;">},</span>
{-1, 1},{0,+1},{1,+1}}
<span style="color: #0000FF;">{-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">},</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;">0</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;">1</span><span style="color: #0000FF;">}}</span>
sequence key = {7,0}, -- chebyshev, cost
moves = {{1,1}},
<span style="color: #004080;">sequence</span> <span style="color: #000000;">key</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- chebyshev, cost</span>
data = {moves},
<span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</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>
acta = {} -- actually analysed set
<span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">},</span>
setd(key,data)
<span style="color: #000000;">acta</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> <span style="color: #000080;font-style:italic;">-- actually analysed set</span>
bool found = false
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span>
integer count = 0
<span style="color: #004080;">bool</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
while not found do
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
if dict_size()=0 then ?"impossible" exit end if
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found</span> <span style="color: #008080;">do</span>
key = getd_partial_key(0)
<span style="color: #008080;">if</span> <span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #008000;">"impossible"</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
data = getd(key)
<span style="color: #000000;">key</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_partial_key</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
moves = data[$]
<span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">)</span>
if length(data)=1 then
<span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">data</span><span style="color: #0000FF;">[$]</span>
deld(key)
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
else
<span style="color: #7060A8;">deld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">)</span>
data = data[1..$-1]
<span style="color: #008080;">else</span>
putd(key,data)
<span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">data</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>
end if
<span style="color: #7060A8;">putd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span>
count += 1
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
acta = append(acta,moves[$])
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
for i=1 to length(permitted) do
<span style="color: #000000;">acta</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">acta</span><span style="color: #0000FF;">,</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[$])</span>
sequence newpos = sq_add(moves[$],permitted[i])
<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;">permitted</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer {nx,ny} = newpos
<span style="color: #004080;">sequence</span> <span style="color: #000000;">newpos</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">[$],</span><span style="color: #000000;">permitted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
if nx>=1 and nx<=8
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newpos</span>
and ny>=1 and ny<=8
<span style="color: #008080;">if</span> <span style="color: #000000;">nx</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">nx</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">8</span>
and grid[nx,ny] = ':' then -- (unvisited)
<span style="color: #008080;">and</span> <span style="color: #000000;">ny</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ny</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">8</span>
grid[nx,ny] = '.'
<span style="color: #008080;">and</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">':'</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (unvisited)</span>
sequence newkey = {max(8-nx,8-ny),key[2]+1},
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'.'</span>
newmoves = append(moves,newpos)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">newkey</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">8</span><span style="color: #0000FF;">-</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">-</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">),</span><span style="color: #000000;">key</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>
if newpos = {8,8} then
<span style="color: #000000;">newmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">,</span><span style="color: #000000;">newpos</span><span style="color: #0000FF;">)</span>
moves = newmoves
<span style="color: #008080;">if</span> <span style="color: #000000;">newpos</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">,</span><span style="color: #000000;">8</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span>
found = true
<span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newmoves</span>
exit
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
end if
integer k <span style="color: getd_index(newkey)#008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if k=0 then
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newkey</span><span style="color: #0000FF;">)</span>
data = {newmoves}
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
else
<span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">newmoves</span><span style="color: #0000FF;">}</span>
data = append(getd_by_index(k),newmoves)
end if<span style="color: #008080;">else</span>
<span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">getd_by_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">k</span><span style="color: #0000FF;">),</span><span style="color: #000000;">newmoves</span><span style="color: #0000FF;">)</span>
putd(newkey,data)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #7060A8;">putd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">newkey</span><span style="color: #0000FF;">,</span><span style="color: #000000;">data</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if found then
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
printf(1,"visited %d nodes\ncost:%d\npath:%v\n",{count,length(moves)-1,moves})
<span style="color: #008080;">if</span> <span style="color: #000000;">found</span> <span style="color: #008080;">then</span>
for i=1 to length(acta) do
<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;">"visited %d nodes\ncost:%d\npath:%v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</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: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">})</span>
integer {x,y} = acta[i]
<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;">acta</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
grid[x,y] = '_'
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">acta</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'_'</span>
for i=1 to length(moves) do
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
integer {x,y} = moves[i]
<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;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
grid[x,y] = 'x'
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'x'</span>
puts(1,join(grid,'\n'))
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end if</lang>
<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;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</lang>-->
 
{{out}}
<pre>
Line 2,829 ⟶ 2,833:
task author assumed it would, instead the main loop uses a priority queue to obtain the next
lowest cost and a simple dictionary to avoid re-examination/inifinte recursion.
<!--<lang Phix>--set_rand(3) -- (for consistent output)>
<span style="color: #000080;font-style:italic;">--set_rand(3) -- (for consistent output)</span>
constant optimal = false,
<span style="color: #008080;">constant</span> <span style="color: #000000;">optimal</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span><span style="color: #0000FF;">,</span>
mtm = true, -- mutli-tile metrics
<span style="color: #000000;">mtm</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span><span style="color: #0000FF;">,</span> <span style="color: #000080;font-style:italic;">-- mutli-tile metrics</span>
target = {1,2,3,4,5,6,7,8,0},
<span style="color: #000000;">target</span> <span style="color: #0000FF;">=</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;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</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: #000000;">0</span><span style="color: #0000FF;">},</span>
-- <-tile found 0..8->
<span style="color: #000080;font-style:italic;">-- &lt;-tile found 0..8-&gt;</span>
mcost = {{0,0,1,2,1,2,3,2,3}, -- position 1
<span style="color: #000000;">mcost</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</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;">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;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- position 1</span>
{0,1,0,1,2,1,2,3,2},
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</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;">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;">2</span><span style="color: #0000FF;">},</span>
{0,2,1,0,3,2,1,4,3},
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</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: #000000;">0</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: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">},</span>
{0,1,2,3,0,1,2,1,2},
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</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;">0</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;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">},</span>
{0,2,1,2,1,0,1,2,1}, -- ...
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</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: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</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;">1</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- ...</span>
{0,3,2,1,2,1,0,3,2},
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</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: #000000;">1</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: #000000;">0</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>
{0,2,3,4,1,2,3,0,1},
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</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;">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;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span>
{0,3,2,3,2,1,2,1,0},
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</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: #000000;">3</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: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span>
{0,4,3,2,3,2,1,2,1}}, -- position 9
<span style="color: #0000FF;">{</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</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: #000000;">3</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: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span> <span style="color: #000080;font-style:italic;">-- position 9</span>
udlr = "udlr",
<span style="color: #000000;">udlr</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"udlr"</span><span style="color: #0000FF;">,</span>
dirs = {+3,-3,+1,-1}, -- udlr
<span style="color: #000000;">dirs</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: #000000;">3</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: #000080;font-style:italic;">-- udlr</span>
lims = {{9,9,9,9,9,9,9,9,9}, -- up
<span style="color: #000000;">lims</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- up</span>
{1,1,1,1,1,1,1,1,1}, -- down
<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;">1</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;">1</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;">1</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- down</span>
{3,3,3,6,6,6,9,9,9}, -- left
<span style="color: #0000FF;">{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">,</span><span style="color: #000000;">9</span><span style="color: #0000FF;">},</span> <span style="color: #000080;font-style:italic;">-- left</span>
{1,1,1,4,4,4,7,7,7}} -- right
<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;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">}}</span> <span style="color: #000080;font-style:italic;">-- right</span>
function get_moves(sequence grid, bool mtm)
<span style="color: #008080;">function</span> <span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">bool</span> <span style="color: #000000;">mtm</span><span style="color: #0000FF;">)</span>
sequence valid = {}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
integer p0 = find(0,grid)
<span style="color: #004080;">integer</span> <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">)</span>
for dx=1 to length(dirs) do
<span style="color: #008080;">for</span> <span style="color: #000000;">dx</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;">dirs</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer step = dirs[dx],
<span style="color: #004080;">integer</span> <span style="color: #000000;">step</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dirs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">],</span>
lim = lims[dx][p0],
<span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lims</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">][</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">],</span>
count = 1
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
for i=p0+step to lim by step do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">+</span><span style="color: #000000;">step</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim</span> <span style="color: #008080;">by</span> <span style="color: #000000;">step</span> <span style="color: #008080;">do</span>
valid = append(valid,{step,i,udlr[dx],count})
<span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">valid</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">step</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">udlr</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">],</span><span style="color: #000000;">count</span><span style="color: #0000FF;">})</span>
if not mtm then exit end if
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">mtm</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
count += 1
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return valid
<span style="color: #008080;">return</span> <span style="color: #000000;">valid</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
function make_move(sequence grid, move)
<span style="color: #008080;">function</span> <span style="color: #000000;">make_move</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">move</span><span style="color: #0000FF;">)</span>
integer p0 = find(0,grid),
<span style="color: #004080;">integer</span> <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">),</span>
{step,lim} = move
<span style="color: #0000FF;">{</span><span style="color: #000000;">step</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lim</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">move</span>
for i=p0+step to lim by step do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">+</span><span style="color: #000000;">step</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim</span> <span style="color: #008080;">by</span> <span style="color: #000000;">step</span> <span style="color: #008080;">do</span>
grid[p0] = grid[i]
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p0</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
grid[i] = 0
<span style="color: #000000;">grid</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;">0</span>
p0 = i
<span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return grid
<span style="color: #008080;">return</span> <span style="color: #000000;">grid</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function manhattan(sequence grid)
<span style="color: #008080;">function</span> <span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">)</span>
integer res = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
for i=1 to 9 do
<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: #000000;">9</span> <span style="color: #008080;">do</span>
res += mcost[i][grid[i]+1]
<span style="color: #000000;">res</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">mcost</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
return res
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
sequence problem, grid, new_grid,
<span style="color: #004080;">sequence</span> <span style="color: #000000;">problem</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span>
moves, next_moves, move
<span style="color: #000000;">moves</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next_moves</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">move</span>
procedure show_grid()
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show_grid</span><span style="color: #0000FF;">()</span>
printf(1,"%s\n",join_by(sq_add(grid,'0'),1,3,""))
<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;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">),</span><span style="color: #000000;">1</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>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
 
grid = target
<span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">target</span>
for i=1 to 1000 do
<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: #000000;">1000</span> <span style="color: #008080;">do</span>
-- (initially shuffle as if mtm==true, otherwise
<span style="color: #000080;font-style:italic;">-- (initially shuffle as if mtm==true, otherwise
-- output compares answers to different puzzles)
-- output compares answers to different puzzles)</span>
moves = get_moves(grid,true)
<span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
move = moves[rand(length(moves))]
<span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">))]</span>
grid = make_move(grid,move)
<span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_move</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
problem = grid
<span style="color: #000000;">problem</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">grid</span>
printf(1,"problem (manhattan cost is %d):\n",manhattan(grid))
<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;">"problem (manhattan cost is %d):\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">))</span>
show_grid()
<span style="color: #000000;">show_grid</span><span style="color: #0000FF;">()</span>
 
integer todo = pq_new(),
<span style="color: #004080;">integer</span> <span style="color: #000000;">todo</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pq_new</span><span style="color: #0000FF;">(),</span>
seen = new_dict()
<span style="color: #000000;">seen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
pq_add({{grid,{}},iff(optimal?0:manhattan(grid))},todo)
<span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,{}},</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">optimal</span><span style="color: #0000FF;">?</span><span style="color: #000000;">0</span><span style="color: #0000FF;">:</span><span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">))},</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)</span>
setd(grid,true,seen)
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">)</span>
atom t1 = time()+1
<span style="color: #004080;">atom</span> <span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
bool found = false
<span style="color: #004080;">bool</span> <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
integer count = 0, mc
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mc</span>
while not found do
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #000000;">found</span> <span style="color: #008080;">do</span>
if pq_size(todo)=0 then ?"impossible" exit end if
<span style="color: #008080;">if</span> <span style="color: #7060A8;">pq_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #008000;">"impossible"</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
{{grid,moves},mc} = pq_pop(todo)
<span style="color: #0000FF;">{{</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">},</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">pq_pop</span><span style="color: #0000FF;">(</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)</span>
if time()>t1 then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()></span><span style="color: #000000;">t1</span> <span style="color: #008080;">then</span>
string m = iff(optimal?"moves":"manhattan")
<span style="color: #004080;">string</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">optimal</span><span style="color: #0000FF;">?</span><span style="color: #008000;">"moves"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"manhattan"</span><span style="color: #0000FF;">)</span>
printf(1,"searching (count=%d, %s=%d)\r",{count,m,mc})
<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;">"searching (count=%d, %s=%d)\r"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">})</span>
t1 = time()+1
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()+</span><span style="color: #000000;">1</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
next_moves = get_moves(grid,mtm)
<span style="color: #000000;">next_moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">get_moves</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mtm</span><span style="color: #0000FF;">)</span>
count += length(next_moves)
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next_moves</span><span style="color: #0000FF;">)</span>
integer l = length(moves)
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span>
for i=1 to length(next_moves) do
<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;">next_moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
move = next_moves[i]
<span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next_moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
new_grid = make_move(grid,move)
<span style="color: #000000;">new_grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_move</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span>
mc = manhattan(new_grid)
<span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">manhattan</span><span style="color: #0000FF;">(</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">)</span>
if mc=0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">mc</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
if new_grid!=target then ?9/0 end if
<span style="color: #008080;">if</span> <span style="color: #000000;">new_grid</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">target</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
moves = append(moves,move)
<span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span>
found = true
<span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
exit
<span style="color: #008080;">exit</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if getd_index(new_grid,seen)=NULL then
<span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">)=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
if optimal then mc = l+1 end if
<span style="color: #008080;">if</span> <span style="color: #000000;">optimal</span> <span style="color: #008080;">then</span> <span style="color: #000000;">mc</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
pq_add({{new_grid,append(moves,move)},mc},todo)
<span style="color: #7060A8;">pq_add</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)},</span><span style="color: #000000;">mc</span><span style="color: #0000FF;">},</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)</span>
setd(new_grid,true,seen)
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">new_grid</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
if found then
<span style="color: #008080;">if</span> <span style="color: #000000;">found</span> <span style="color: #008080;">then</span>
string s = iff(length(moves)=1?"":"s")
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</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: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">""</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"s"</span><span style="color: #0000FF;">)</span>
if optimal then
<span style="color: #008080;">if</span> <span style="color: #000000;">optimal</span> <span style="color: #008080;">then</span>
s &= sprintf(" (max shd be %d)",iff(mtm?24:31))
<span style="color: #000000;">s</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">" (max shd be %d)"</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mtm</span><span style="color: #0000FF;">?</span><span style="color: #000000;">24</span><span style="color: #0000FF;">:</span><span style="color: #000000;">31</span><span style="color: #0000FF;">))</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
grid = problem
<span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">problem</span>
string soln = ""
<span style="color: #004080;">string</span> <span style="color: #000000;">soln</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
for i=1 to length(moves) do
<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;">moves</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
move = moves[i]
<span style="color: #000000;">move</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">moves</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
grid = make_move(grid,move)
<span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">make_move</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">move</span><span style="color: #0000FF;">)</span>
integer {{},{},ch,c} = move
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{{},{},</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">move</span>
soln &= ch
<span style="color: #000000;">soln</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">ch</span>
if c>1 then soln&='0'+c end if
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000000;">soln</span><span style="color: #0000FF;">&=</span><span style="color: #008000;">'0'</span><span style="color: #0000FF;">+</span><span style="color: #000000;">c</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
-- show_grid() -- (set the initial shuffle to eg 5 first!)
<span style="color: #000080;font-style:italic;">-- show_grid() -- (set the initial shuffle to eg 5 first!)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
-- show_grid() -- (not very educational!)
<span style="color: #000080;font-style:italic;">-- show_grid() -- (not very educational!)</span>
if grid!=target then ?9/0 end if
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">target</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
printf(1,"solved in %d move%s:%s\n",{length(moves),s,soln})
<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;">"solved in %d move%s:%s\n"</span><span style="color: #0000FF;">,{</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: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">soln</span><span style="color: #0000FF;">})</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
printf(1,"count:%d, seen:%d, queue:%d\n",{count,dict_size(seen),pq_size(todo)})</lang>
<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;">"count:%d, seen:%d, queue:%d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">count</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">dict_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">seen</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">pq_size</span><span style="color: #0000FF;">(</span><span style="color: #000000;">todo</span><span style="color: #0000FF;">)})</span>
<!--</lang>-->
{{out}}
Note: The solutions are non-optimal (far from it, in fact), since it searches lowest manhattan() first.<br>
Petelomax
7,796

edits

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