Maze solving: Difference between revisions
Content added Content deleted
(Added solution for Action!) |
m (→{{header|Phix}}: added syntax colouring, marked p2js compatible) |
||
Line 3,889: | Line 3,889: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Combined generator and solver. |
Combined generator and solver. |
||
<lang Phix>-- |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #000080;font-style:italic;">-- |
|||
constant w = 11, h = 8 |
|||
-- demo\rosetta\Maze_solving.exw |
|||
-- ============================= |
|||
sequence wall = join(repeat("+",w+1),"---")&"\n", |
|||
--</span> |
|||
cell = join(repeat("|",w+1)," ? ")&"\n", |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
grid = split(join(repeat(wall,h+1),cell),'\n') |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">11</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">h</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">8</span> |
|||
procedure amaze(integer x, integer y) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">wall</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"+"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</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;">"\n"</span><span style="color: #0000FF;">,</span> |
|||
grid[y][x] = ' ' -- mark cell visited |
|||
<span style="color: #000000;">cell</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"|"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">w</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;">"\n"</span><span style="color: #0000FF;">,</span> |
|||
sequence p = shuffle({{x-4,y},{x,y+2},{x+4,y},{x,y-2}}) |
|||
<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: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">wall</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">cell</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span> |
|||
for i=1 to length(p) do |
|||
integer {nx,ny} = p[i] |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">amaze</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">)</span> |
|||
if nx>1 and nx<w*4 and ny>1 and ny<=2*h and grid[ny][nx]='?' then |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> <span style="color: #000080;font-style:italic;">-- mark cell visited</span> |
|||
integer mx = (x+nx)/2 |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shuffle</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</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: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</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: #000000;">2</span><span style="color: #0000FF;">}})</span> |
|||
grid[(y+ny)/2][mx-1..mx+1] = ' ' -- knock down wall |
|||
<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;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
amaze(nx,ny) |
|||
<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;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> |
|||
end if |
|||
<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;">w</span><span style="color: #0000FF;">*</span><span style="color: #000000;">4</span> <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;">2</span><span style="color: #0000FF;">*</span><span style="color: #000000;">h</span> <span style="color: #008080;">and</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">'?'</span> <span style="color: #008080;">then</span> |
|||
end for |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">mx</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span> |
|||
end procedure |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">mx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">mx</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: #008000;">' '</span> <span style="color: #000080;font-style:italic;">-- knock down wall</span> |
|||
<span style="color: #000000;">amaze</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> |
|||
integer dx,dy -- door location (in a wall!) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
function solve_maze(integer x, y) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
sequence p = {{x-4,y},{x,y+2},{x+4,y},{x,y-2}} |
|||
for d=1 to length(p) do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dy</span> <span style="color: #000080;font-style:italic;">-- door location (in a wall!)</span> |
|||
integer {nx,ny} = p[d] |
|||
integer {wx,wy} = {(x+nx)/2,(y+ny)/2} |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">solve_maze</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">)</span> |
|||
if grid[wy][wx]=' ' then |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</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: #000000;">2</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</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: #000000;">2</span><span style="color: #0000FF;">}}</span> |
|||
grid[wy][wx] = "-:-:"[d] -- mark path |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">d</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;">p</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
if {wx,wy}={dx,dy} then return true end if |
|||
<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;">p</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> |
|||
if grid[ny][nx]=' ' then |
|||
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">wx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">wy</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span> |
|||
grid[ny][nx] = 'o' -- mark cell |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">wy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">wx</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span> |
|||
if solve_maze(nx,ny) then return true end if |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">wy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">wx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"-:-:"</span><span style="color: #0000FF;">[</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]</span> <span style="color: #000080;font-style:italic;">-- mark path</span> |
|||
grid[ny][nx] = ' ' -- unmark cell |
|||
<span style="color: #008080;">if</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">wx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">wy</span><span style="color: #0000FF;">}={</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">}</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">' '</span> <span style="color: #008080;">then</span> |
|||
grid[wy][wx] = ' ' -- unmark path |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'o'</span> <span style="color: #000080;font-style:italic;">-- mark cell</span> |
|||
end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">solve_maze</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: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">true</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end for |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ny</span><span style="color: #0000FF;">][</span><span style="color: #000000;">nx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> <span style="color: #000080;font-style:italic;">-- unmark cell</span> |
|||
return false |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end function |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">wy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">wx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> <span style="color: #000080;font-style:italic;">-- unmark path</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
function heads() |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
return rand(2)=1 -- toin coss 50:50 true(1)/false(0) |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">false</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
integer {x,y} = {(rand(w)*4)-1,rand(h)*2} |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">heads</span><span style="color: #0000FF;">()</span> |
|||
amaze(x,y) |
|||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">rand</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: #000080;font-style:italic;">-- toin coss 50:50 true(1)/false(0)</span> |
|||
-- mark start pos |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
grid[y][x] = '*' |
|||
-- add a random door (heads=rhs/lhs, tails=top/btm) |
|||
<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: #0000FF;">{(</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</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: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">}</span> |
|||
if heads() then |
|||
<span style="color: #000000;">amaze</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> |
|||
{dy,dx} = {rand(h)*2,heads()*w*4+1} |
|||
<span style="color: #000080;font-style:italic;">-- mark start pos</span> |
|||
grid[dy][dx] = ' ' |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">y</span><span style="color: #0000FF;">][</span><span style="color: #000000;">x</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">'*'</span> |
|||
else |
|||
<span style="color: #000080;font-style:italic;">-- add a random door (heads=rhs/lhs, tails=top/btm)</span> |
|||
{dy,dx} = {heads()*h*2+1,rand(w)*4-1} |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">heads</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">then</span> |
|||
grid[dy][dx-1..dx+1] = ' ' |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">heads</span><span style="color: #0000FF;">()*</span><span style="color: #000000;">w</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> |
|||
end if |
|||
<span style="color: #000000;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span> |
|||
{} = solve_maze(x,y) |
|||
<span style="color: #008080;">else</span> |
|||
puts(1,join(grid,'\n'))</lang> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">,</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">heads</span><span style="color: #0000FF;">()*</span><span style="color: #000000;">h</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: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">w</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;">grid</span><span style="color: #0000FF;">[</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">][</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">dx</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: #008000;">' '</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #0000FF;">{}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">solve_maze</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: #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> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |