A* search algorithm: Difference between revisions

Line 2,948:

Note that the 23 visited nodes does not count walls, but with them this algorithm exactly matches the 35 of Racket.

sequence grid = split("""

x:::::::

Line 2,959:

::::::::

""",'\n')

constant permitted = {{-1,-1},{0,-1},{1,-1},

{-1, 0}, {1, 0},

{-1, 1},{0,+1},{1,+1}}

sequence key = {7,0}, -- chebyshev, cost

moves = {{1,1}},

Line 2,992:

Line 2,990:

grid[nx,ny] = '.'

sequence newkey = {max(8-nx,8-ny),key[2]+1},

newmoves = ~~append~~(moves~~,newpos~~)

newmoves = deep_copy(moves)

newmoves = append(newmoves,newpos)

if newpos = {8,8} then

moves = newmoves

Line 3,000:

Line 2,999:

integer k = getd_index(newkey)

if k=0 then

data = {~~newmoves~~}

data = {}

else

data = ~~append~~(getd_by_index(k)~~,newmoves~~)

data = deep_copy(getd_by_index(k))

end if

data = append(data,newmoves)

putd(newkey,data)

end if

Line 3,042:

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.

--set_rand(3) -- (for consistent output)

constant optimal = false,

mtm = true, -- mutli-tile metrics

target = {1,2,3,4,5,6,7,8,0},

target = {1,2,3,4,5,6,7,8,0},

-- <-tile found 0..8->

mcost = {{0,0,1,2,1,2,3,2,3}, -- position 1

Line 3,063:

Line 3,064:

{3,3,3,6,6,6,9,9,9}, -- left

{1,1,1,4,4,4,7,7,7}} -- right

function get_moves(sequence grid, bool mtm)

sequence valid = {}

Line 3,071:

Line 3,072:

lim = lims[dx][p0],

count = 1

~~for~~ i=p0+step to lim by step do

integer i = p0+step

while true do

if step<0 then

if i<lim then exit end if

else

if i>lim then exit end if

end if

valid = append(valid,{step,i,udlr[dx],count})

if not mtm then exit end if

count += 1

~~end~~ ~~for~~

i += step

end while

end for

return valid

end function

function make_move(sequence grid, move)

integer p0 = find(0,grid),

{step,lim} = move

~~for~~ i~~<span~~ ~~style="color: #0000FF;">=p0~~~~+step~~ to ~~lim~~ ~~by~~ ~~step~~ do

grid = deep_copy(grid)

integer i = p0+step

while true do

if step<0 then

if i<lim then exit end if

else

if i>lim then exit end if

end if

grid[p0] = grid[i]

grid[i] = 0

p0 = i

~~end~~ ~~for~~

i += step

end while

return grid

end function

function manhattan(sequence grid)

integer res = 0

Line 3,098:

Line 3,114:

return res

end function

sequence problem, grid, new_grid,

moves, next_moves, move

procedure show_grid()

printf(1,"%s\n",join_by(sq_add(grid,'0'),1,3,""))

end procedure

grid = target

grid = target

for i=1 to 1000 do

-- (initially shuffle as if mtm==true, otherwise

Line 3,117:

Line 3,133:

printf(1,"problem (manhattan cost is %d):\n",manhattan(grid))

show_grid()

integer todo = pq_new(),

seen = new_dict()

Line 3,141:

Line 3,156:

mc = manhattan(new_grid)

if mc=0 then

if new_grid!=target then ?9/0 end if

if new_grid!=target then ?9/0 end if

moves = append(moves,move)

found = true

Line 3,148:

Line 3,163:

if getd_index(new_grid,seen)=NULL then

if optimal then mc = l+1 end if

pq_add({{new_grid,append(moves,move)},mc},todo)

pq_add({{new_grid,append(deep_copy(moves),move)},mc},todo)

setd(new_grid,true,seen)

end if

Line 3,169:

Line 3,184:

end for

-- show_grid() -- (not very educational!)

if grid!=target then ?9/0 end if

if grid!=target then ?9/0 end if

printf(1,"solved in %d move%s:%s\n",{length(moves),s,soln})

end if

printf(1,"count:%d, seen:%d, queue:%d\n",{count,dict_size(seen),pq_size(todo)})

Note: The solutions are non-optimal (far from it, in fact), since it searches lowest manhattan() first.

@@ Line 2,948: / Line 2,948: @@
 Note that the 23 visited nodes does not count walls, but with them this algorithm exactly matches the 35 of Racket.
-<!--<lang Phix>-->
+<!--<lang Phix>(phixonline)-->
  <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:::::::
@@ Line 2,959: / Line 2,959: @@
  ::::::::
  """</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
  <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>
                        <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>
  <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>
           <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>
@@ Line 2,992: / Line 2,990: @@
              <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: #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>
-                      <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>
+                      <span style="color: #000000;">newmoves</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">moves</span><span style="color: #0000FF;">)</span>
+             <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;">newmoves</span><span style="color: #0000FF;">,</span><span style="color: #000000;">newpos</span><span style="color: #0000FF;">)</span>
              <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>
                  <span style="color: #000000;">moves</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">newmoves</span>
@@ Line 3,000: / Line 2,999: @@
              <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>
              <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>
-                 <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>
+                 <span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
              <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>
+                 <span style="color: #000000;">data</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</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: #008080;">end</span> <span style="color: #008080;">if</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: #000000;">data</span><span style="color: #0000FF;">,</span><span style="color: #000000;">newmoves</span><span style="color: #0000FF;">)</span>
              <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>
          <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
@@ Line 3,042: / Line 3,042: @@
 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>-->
+<!--<lang Phix>(phixonline)-->
  <span style="color: #000080;font-style:italic;">--set_rand(3)    -- (for consistent output)</span>
  <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>
           <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>
-          <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>
+          <span style="color: #7060A8;">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>
               <span style="color: #000080;font-style:italic;">--   &lt;-tile found 0..8-&gt;</span>
           <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>
@@ Line 3,063: / Line 3,064: @@
                   <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>
                   <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>
  <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>
      <span style="color: #004080;">sequence</span> <span style="color: #000000;">valid</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
@@ Line 3,071: / Line 3,072: @@
                  <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>
                  <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
-         <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>
+         <span style="color: #004080;">integer</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;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
+             <span style="color: #008080;">if</span> <span style="color: #000000;">step</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
+                 <span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">lim</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>
+             <span style="color: #008080;">else</span>
+                 <span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">lim</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>
+             <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
              <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>
              <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>
              <span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
-         <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
+             <span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">step</span>
+         <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
      <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
      <span style="color: #008080;">return</span> <span style="color: #000000;">valid</span>
  <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  <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>
      <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>
              <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>
-     <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>
+     <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">grid</span><span style="color: #0000FF;">)</span>
+     <span style="color: #004080;">integer</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;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
+         <span style="color: #008080;">if</span> <span style="color: #000000;">step</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
+             <span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><</span><span style="color: #000000;">lim</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>
+         <span style="color: #008080;">else</span>
+             <span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">lim</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>
+         <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
          <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>
          <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>
          <span style="color: #000000;">p0</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
-     <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
+         <span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">step</span>
+     <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
      <span style="color: #008080;">return</span> <span style="color: #000000;">grid</span>
  <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  <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>
      <span style="color: #004080;">integer</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
@@ Line 3,098: / Line 3,114: @@
      <span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
  <span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
  <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>
           <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>
  <span style="color: #008080;">procedure</span> <span style="color: #000000;">show_grid</span><span style="color: #0000FF;">()</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;">"%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>
  <span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
- <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">target</span>
+ <span style="color: #000000;">grid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">target</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: #000000;">1000</span> <span style="color: #008080;">do</span>
      <span style="color: #000080;font-style:italic;">-- (initially shuffle as if mtm==true, otherwise
@@ Line 3,117: / Line 3,133: @@
  <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>
  <span style="color: #000000;">show_grid</span><span style="color: #0000FF;">()</span>
  <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>
          <span style="color: #000000;">seen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
@@ Line 3,141: / Line 3,156: @@
          <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>
          <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>
-             <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>
+             <span style="color: #008080;">if</span> <span style="color: #000000;">new_grid</span><span style="color: #0000FF;">!=</span><span style="color: #7060A8;">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>
              <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>
              <span style="color: #000000;">found</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
@@ Line 3,148: / Line 3,163: @@
          <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>
              <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>
-             <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>
+             <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: #7060A8;">deep_copy</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>
              <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>
          <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
@@ Line 3,169: / Line 3,184: @@
      <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
  <span style="color: #000080;font-style:italic;">--  show_grid() -- (not very educational!)</span>
-     <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>
+     <span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">!=</span><span style="color: #7060A8;">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>
      <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>
  <span style="color: #008080;">end</span> <span style="color: #008080;">if</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;">"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>