I'm a software engineer, get me out of here: Difference between revisions

Content added Content deleted
m (→‎{{header|Raku}}: pointing out the obvious)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 946: Line 946:
=={{header|Phix}}==
=={{header|Phix}}==
Using a simple breadth-first search. Parts 1 and 2 and extra credit.
Using a simple breadth-first search. Parts 1 and 2 and extra credit.
<lang Phix>constant gmooh = split("""
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">constant</span> <span style="color: #000000;">gmooh</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"""
.........00000.........
......00003130000......
.........00000.........
....000321322221000....
......00003130000......
...00231222432132200...
....000321322221000....
...00231222432132200...
..0041433223233211100..
..0041433223233211100..
..0232231612142618530..
..0232231612142618530..
.003152122326114121200.
.003152122326114121200.
.031252235216111132210.
.031252235216111132210.
.022211246332311115210.
.022211246332311115210.
00113232262121317213200
00113232262121317213200
03152118212313211411110
03152118212313211411110
03231234121132221411410
03231234121132221411410
03513213411311414112320
03513213411311414112320
00427534125412213211400
00427534125412213211400
.013322444412122123210.
.013322444412122123210.
.015132331312411123120.
.015132331312411123120.
.003333612214233913300.
.003333612214233913300.
..0219126511415312570..
..0219126511415312570..
..0021321524341325100..
..0021321524341325100..
...00211415413523200...
....000122111322000....
...00211415413523200...
......00001120000......
....000122111322000....
.........00000.........""",'\n')
......00001120000......
.........00000........."""</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'\n'</span><span style="color: #0000FF;">)</span>
constant width = length(gmooh[1]),
<span style="color: #008080;">constant</span> <span style="color: #7060A8;">width</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gmooh</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]),</span>
height = length(gmooh),
<span style="color: #7060A8;">height</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">gmooh</span><span style="color: #0000FF;">),</span>
d = {{-1,-1},{0,-1},{+1,-1},
<span style="color: #000000;">d</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, 0}, {+1, 0},
<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>
{-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;">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 routes -- {cost,fromy,fromx} for each gmooh[][].
<span style="color: #004080;">sequence</span> <span style="color: #000000;">routes</span> <span style="color: #000080;font-style:italic;">-- {cost,fromy,fromx} for each gmooh[][].</span>
procedure search(integer y, x)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">search</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
-- simple breadth-first search, populates routes
<span style="color: #000080;font-style:italic;">-- simple breadth-first search, populates routes
-- (this isn't strictly dijkstra, because graph edges are not weighted)
-- (this isn't strictly dijkstra, because graph edges are not weighted)</span>
integer cost = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">cost</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
sequence route = {{y,x}},
<span style="color: #004080;">sequence</span> <span style="color: #000000;">route</span> <span style="color: #0000FF;">=</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>
next = {}
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
routes = repeat(repeat(0,width),height)
<span style="color: #000000;">routes</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">width</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">height</span><span style="color: #0000FF;">)</span>
routes[y,x] = {0,y,x} -- zero-cost the starting point
<span style="color: #000000;">routes</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: #0000FF;">{</span><span style="color: #000000;">0</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: #000080;font-style:italic;">-- zero-cost the starting point</span>
while 1 do
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
integer n = gmooh[y,x]-'0'
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gmooh</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: #008000;">'0'</span>
for di=1 to length(d) do
<span style="color: #008080;">for</span> <span style="color: #000000;">di</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;">d</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer {dx,dy} = d[di]
<span style="color: #004080;">integer</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: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">di</span><span style="color: #0000FF;">]</span>
integer {rx,ry} = {x+n*dx,y+n*dy}
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ry</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;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">}</span>
if rx>=1 and rx<=width
<span style="color: #008080;">if</span> <span style="color: #000000;">rx</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">rx</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">width</span>
and ry>=1 and ry<=height
<span style="color: #008080;">and</span> <span style="color: #000000;">ry</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ry</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">height</span>
and gmooh[ry,rx]>='0' then
<span style="color: #008080;">and</span> <span style="color: #000000;">gmooh</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">]>=</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">then</span>
object ryx = routes[ry,rx]
<span style="color: #004080;">object</span> <span style="color: #000000;">ryx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">routes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">]</span>
if ryx=0
<span style="color: #008080;">if</span> <span style="color: #000000;">ryx</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span>
or ryx[1]>cost+1 then
<span style="color: #008080;">or</span> <span style="color: #000000;">ryx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]></span><span style="color: #000000;">cost</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
routes[ry,rx] = {cost+1,y,x}
<span style="color: #000000;">routes</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">cost</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</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>
if gmooh[ry,rx]>'0' then
<span style="color: #008080;">if</span> <span style="color: #000000;">gmooh</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">]></span><span style="color: #008000;">'0'</span> <span style="color: #008080;">then</span>
next = append(next,{cost+1,ry,rx})
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">cost</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">})</span>
-- (if the graph was weighted, at this point
-- that would get shuffled up into place.)
<span style="color: #000080;font-style:italic;">-- (if the graph was weighted, at this point
end if
-- that would get shuffled up into place.)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
if length(next)=0 then exit end if
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</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>
{cost,y,x} = next[1]
<span style="color: #0000FF;">{</span><span style="color: #000000;">cost</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: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
next = next[2..$]
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>

function get_route(sequence yx)
<span style="color: #008080;">function</span> <span style="color: #000000;">get_route</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">yx</span><span style="color: #0000FF;">)</span>
integer {y,x} = yx, cost
<span style="color: #004080;">integer</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: #000000;">yx</span>
sequence res = {{y,x}}
<span style="color: #004080;">integer</span> <span style="color: #000000;">cost</span>
while 1 do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</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>
{cost,y,x} = routes[y,x]
<span style="color: #008080;">while</span> <span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
if cost=0 then exit end if
<span style="color: #0000FF;">{</span><span style="color: #000000;">cost</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: #000000;">routes</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>
res = prepend(res,{y,x})
<span style="color: #008080;">if</span> <span style="color: #000000;">cost</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</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>
end while
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prepend</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</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>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure show_shortest_routes_to_safety()
integer shortest = 9999
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show_shortest_routes_to_safety</span><span style="color: #0000FF;">()</span>
sequence res = {}
<span style="color: #004080;">integer</span> <span style="color: #000000;">shortest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">9999</span>
for x=1 to width do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for y=1 to height do
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">width</span> <span style="color: #008080;">do</span>
if gmooh[y,x]='0' then
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">height</span> <span style="color: #008080;">do</span>
object ryx = routes[y,x]
<span style="color: #008080;">if</span> <span style="color: #000000;">gmooh</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: #008000;">'0'</span> <span style="color: #008080;">then</span>
if ryx!=0 then
<span style="color: #004080;">object</span> <span style="color: #000000;">ryx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">routes</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>
integer cost = ryx[1]
<span style="color: #008080;">if</span> <span style="color: #000000;">ryx</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
if cost<=shortest then
<span style="color: #004080;">integer</span> <span style="color: #000000;">cost</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ryx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
if cost<shortest then
<span style="color: #008080;">if</span> <span style="color: #000000;">cost</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">shortest</span> <span style="color: #008080;">then</span>
res = {}
<span style="color: #008080;">if</span> <span style="color: #000000;">cost</span><span style="color: #0000FF;"><</span><span style="color: #000000;">shortest</span> <span style="color: #008080;">then</span>
shortest = cost
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
end if
<span style="color: #000000;">shortest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cost</span>
res = append(res,{y,x})
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</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>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
string {areis,s} = iff(length(res)>1?{"are","s"}:{"is",""})
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
printf(1,"There %s %d shortest route%s of %d days to safety:\n",{areis,length(res),s,shortest})
<span style="color: #004080;">string</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">areis</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">}</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;">res</span><span style="color: #0000FF;">)></span><span style="color: #000000;">1</span><span style="color: #0000FF;">?{</span><span style="color: #008000;">"are"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"s"</span><span style="color: #0000FF;">}:{</span><span style="color: #008000;">"is"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">""</span><span style="color: #0000FF;">})</span>
for i=1 to length(res) 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;">"There %s %d shortest route%s of %d days to safety:\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">areis</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">shortest</span><span style="color: #0000FF;">})</span>
?get_route(res[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;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for
<span style="color: #0000FF;">?</span><span style="color: #000000;">get_route</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure show_unreachable()
sequence res = {}
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show_unreachable</span><span style="color: #0000FF;">()</span>
for x=1 to width do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for y=1 to height do
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">width</span> <span style="color: #008080;">do</span>
if gmooh[y,x]>='0'
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">height</span> <span style="color: #008080;">do</span>
and routes[y,x]=0 then
<span style="color: #008080;">if</span> <span style="color: #000000;">gmooh</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: #008000;">'0'</span>
res = append(res,{y,x})
<span style="color: #008080;">and</span> <span style="color: #000000;">routes</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;">0</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</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>
end for
<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>
puts(1,"The following cells are unreachable:\n")
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
?res
<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: #008000;">"The following cells are unreachable:\n"</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #0000FF;">?</span><span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure show_longest()
integer longest = 0
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show_longest</span><span style="color: #0000FF;">()</span>
sequence res = {}
<span style="color: #004080;">integer</span> <span style="color: #000000;">longest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
for x=1 to width do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for y=1 to height do
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">width</span> <span style="color: #008080;">do</span>
if gmooh[y,x]>='0' then
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">height</span> <span style="color: #008080;">do</span>
object ryx = routes[y,x]
<span style="color: #008080;">if</span> <span style="color: #000000;">gmooh</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: #008000;">'0'</span> <span style="color: #008080;">then</span>
if ryx!=0 then
<span style="color: #004080;">object</span> <span style="color: #000000;">ryx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">routes</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>
integer rl = ryx[1]
<span style="color: #008080;">if</span> <span style="color: #000000;">ryx</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
if rl>=longest then
<span style="color: #004080;">integer</span> <span style="color: #000000;">rl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ryx</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
if rl>longest then
<span style="color: #008080;">if</span> <span style="color: #000000;">rl</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">longest</span> <span style="color: #008080;">then</span>
res = {}
<span style="color: #008080;">if</span> <span style="color: #000000;">rl</span><span style="color: #0000FF;">></span><span style="color: #000000;">longest</span> <span style="color: #008080;">then</span>
longest = rl
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
end if
<span style="color: #000000;">longest</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rl</span>
res = append(res,{y,x})
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</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>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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;">if</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
printf(1,"There are %d cells that take %d days to send reinforcements to\n",{length(res),longest})
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
for i=1 to length(res) 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;">"There are %d cells that take %d days to send reinforcements to\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span><span style="color: #000000;">longest</span><span style="color: #0000FF;">})</span>
?get_route(res[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;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
end for
<span style="color: #0000FF;">?</span><span style="color: #000000;">get_route</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure main()
search(12,12)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
show_shortest_routes_to_safety()
<span style="color: #000000;">search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">show_shortest_routes_to_safety</span><span style="color: #0000FF;">()</span>
-- see also below
search(22,12)
<span style="color: #000080;font-style:italic;">-- see also below</span>
puts(1,"The shortest route from 22,12 to 2,12:\n")
<span style="color: #000000;">search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">22</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">)</span>
?get_route({2,12})
<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: #008000;">"The shortest route from 22,12 to 2,12:\n"</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">get_route</span><span style="color: #0000FF;">({</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">})</span>
search(2,12)
puts(1,"The shortest route from 2,12 to 22,12:\n")
<span style="color: #000000;">search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">)</span>
?get_route({22,12})
<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: #008000;">"The shortest route from 2,12 to 22,12:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">get_route</span><span style="color: #0000FF;">({</span><span style="color: #000000;">22</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">})</span>
search(12,12)
-- </see also below>
<span style="color: #000000;">search</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">)</span>

<span style="color: #000080;font-style:italic;">-- &lt;/see also below&gt;</span>
show_unreachable()
show_longest()
<span style="color: #000000;">show_unreachable</span><span style="color: #0000FF;">()</span>

<span style="color: #000000;">show_longest</span><span style="color: #0000FF;">()</span>
end procedure
main()</lang>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">main</span><span style="color: #0000FF;">()</span>
<!--</lang>-->
{{out}}
{{out}}
Note: Phix indexes are 1-based and therefore so too are these results.
Note: Phix indexes are 1-based and therefore so too are these results.
Line 1,170: Line 1,173:
</pre>
</pre>
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
<!--<lang Phix>(phixonline)-->
<lang Phix>--(same constants as above: gmooh, width, height, d)
<span style="color: #000080;font-style:italic;">--(same constants as above: gmooh, width, height, d)</span>
constant inf = 1e300*1e300
<span style="color: #008080;">constant</span> <span style="color: #000000;">inf</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1e300</span><span style="color: #0000FF;">*</span><span style="color: #000000;">1e300</span>

sequence dist, next, pmap = {}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">dist</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pmap</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
function fw_path(integer u, v)
<span style="color: #008080;">function</span> <span style="color: #000000;">fw_path</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">)</span>
sequence res = {}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
if next[u,v]!=null then
<span style="color: #008080;">if</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">]!=</span><span style="color: #004600;">null</span> <span style="color: #008080;">then</span>
sequence path = {sprintf("{%d,%d}",pmap[u])}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">path</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"{%d,%d}"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pmap</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">])}</span>
while u!=v do
<span style="color: #008080;">while</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">v</span> <span style="color: #008080;">do</span>
u = next[u,v]
<span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">]</span>
path = append(path,sprintf("{%d,%d}",pmap[u]))
<span style="color: #000000;">path</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"{%d,%d}"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pmap</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">]))</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
res = join(path,"->")
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">path</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"-&gt;"</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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>

procedure show_fw_path(integer u, v)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">show_fw_path</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">v</span><span style="color: #0000FF;">)</span>
printf(1,"{%d,%d}->{%d,%d} %2d %s\n",pmap[u]&pmap[v]&{dist[u,v],fw_path(u,v)})
<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;">"{%d,%d}-&gt;{%d,%d} %2d %s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pmap</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">]&</span><span style="color: #000000;">pmap</span><span style="color: #0000FF;">[</span><span style="color: #000000;">v</span><span style="color: #0000FF;">]&{</span><span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">],</span><span style="color: #000000;">fw_path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">)})</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
procedure FloydWarshall()
<span style="color: #008080;">procedure</span> <span style="color: #000000;">FloydWarshall</span><span style="color: #0000FF;">()</span>
integer point = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">point</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
sequence weights = {},
<span style="color: #004080;">sequence</span> <span style="color: #000000;">weights</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
points = repeat(repeat(0,width),height)
<span style="color: #000000;">points</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">width</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">height</span><span style="color: #0000FF;">)</span>
-- First number the points...
<span style="color: #000080;font-style:italic;">-- First number the points...</span>
for x=1 to width do
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">width</span> <span style="color: #008080;">do</span>
for y=1 to height do
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">height</span> <span style="color: #008080;">do</span>
if gmooh[y,x]>='0' then
<span style="color: #008080;">if</span> <span style="color: #000000;">gmooh</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: #008000;">'0'</span> <span style="color: #008080;">then</span>
point += 1
<span style="color: #000000;">point</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
points[y,x] = point
<span style="color: #000000;">points</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: #000000;">point</span>
pmap = append(pmap,{y,x})
<span style="color: #000000;">pmap</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pmap</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>
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 for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
-- ...and then a set of edges (all of which have a "weight" of 1 day)
<span style="color: #000080;font-style:italic;">-- ...and then a set of edges (all of which have a "weight" of 1 day)</span>
for x=1 to width do
<span style="color: #008080;">for</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">width</span> <span style="color: #008080;">do</span>
for y=1 to height do
<span style="color: #008080;">for</span> <span style="color: #000000;">y</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">height</span> <span style="color: #008080;">do</span>
if gmooh[y,x]>'0' then
<span style="color: #008080;">if</span> <span style="color: #000000;">gmooh</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: #008000;">'0'</span> <span style="color: #008080;">then</span>
integer n = gmooh[y,x]-'0'
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">gmooh</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: #008000;">'0'</span>
for di=1 to length(d) do
<span style="color: #008080;">for</span> <span style="color: #000000;">di</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;">d</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer {dx,dy} = d[di]
<span style="color: #004080;">integer</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: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">di</span><span style="color: #0000FF;">]</span>
integer {rx,ry} = {x+n*dx,y+n*dy}
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ry</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;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y</span><span style="color: #0000FF;">+</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">}</span>
if rx>=1 and rx<=width
<span style="color: #008080;">if</span> <span style="color: #000000;">rx</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">rx</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">width</span>
and ry>=1 and ry<=height
<span style="color: #008080;">and</span> <span style="color: #000000;">ry</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">ry</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">height</span>
and gmooh[ry,rx]>='0' then
<span style="color: #008080;">and</span> <span style="color: #000000;">gmooh</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</span><span style="color: #0000FF;">]>=</span><span style="color: #008000;">'0'</span> <span style="color: #008080;">then</span>
-- weights = append(weights,{points[y,x],points[ry,rx],1})
weights = append(weights,{points[y,x],points[ry,rx]})
<span style="color: #000080;font-style:italic;">-- weights = append(weights,{points[y,x],points[ry,rx],1})</span>
<span style="color: #000000;">weights</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">weights</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">points</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;">points</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ry</span><span style="color: #0000FF;">,</span><span style="color: #000000;">rx</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 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 for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
-- Before applying Floyd-Warshall
<span style="color: #000080;font-style:italic;">-- Before applying Floyd-Warshall</span>
integer V = length(pmap)
<span style="color: #004080;">integer</span> <span style="color: #000000;">V</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pmap</span><span style="color: #0000FF;">)</span>
dist = repeat(repeat(inf,V),V)
<span style="color: #000000;">dist</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inf</span><span style="color: #0000FF;">,</span><span style="color: #000000;">V</span><span style="color: #0000FF;">),</span><span style="color: #000000;">V</span><span style="color: #0000FF;">)</span>
next = repeat(repeat(null,V),V)
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">null</span><span style="color: #0000FF;">,</span><span style="color: #000000;">V</span><span style="color: #0000FF;">),</span><span style="color: #000000;">V</span><span style="color: #0000FF;">)</span>
for k=1 to length(weights) do
<span style="color: #008080;">for</span> <span style="color: #000000;">k</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;">weights</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
-- integer {u,v,w} = weights[k]
integer {u,v} = weights[k]
<span style="color: #000080;font-style:italic;">-- integer {u,v,w} = weights[k]</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">weights</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
-- dist[u,v] := w -- the weight of the edge (u,v)
dist[u,v] := 1 -- the weight of the edge (u,v)
<span style="color: #000080;font-style:italic;">-- dist[u,v] := w -- the weight of the edge (u,v)</span>
<span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">1</span> <span style="color: #000080;font-style:italic;">-- the weight of the edge (u,v)</span>
next[u,v] := v
<span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span><span style="color: #000000;">v</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">v</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
-- standard Floyd-Warshall implementation,
<span style="color: #000080;font-style:italic;">-- standard Floyd-Warshall implementation,
-- with the optimisation of avoiding processing of self/infs,
-- with the optimisation of avoiding processing of self/infs,
-- which surprisingly makes quite a noticeable difference.
-- which surprisingly makes quite a noticeable difference.</span>
for k=1 to V do
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">V</span> <span style="color: #008080;">do</span>
for i=1 to V 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;">V</span> <span style="color: #008080;">do</span>
if i!=k and dist[i,k]!=inf then
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">k</span> <span style="color: #008080;">and</span> <span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">inf</span> <span style="color: #008080;">then</span>
for j=1 to V do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">V</span> <span style="color: #008080;">do</span>
if j!=i and j!=k and dist[k,j]!=inf then
<span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">i</span> <span style="color: #008080;">and</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">k</span> <span style="color: #008080;">and</span> <span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">inf</span> <span style="color: #008080;">then</span>
atom d = dist[i,k] + dist[k,j]
<span style="color: #004080;">atom</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
if d<dist[i,j] then
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><</span><span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
dist[i,j] := d
<span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">d</span>
next[i,j] := next[i,k]
<span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">next</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span>
end if
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<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 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 for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
show_fw_path(points[22,12],points[2,12])
<span style="color: #000000;">show_fw_path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">points</span><span style="color: #0000FF;">[</span><span style="color: #000000;">22</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">],</span><span style="color: #000000;">points</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">])</span>
show_fw_path(points[2,12],points[22,12])
<span style="color: #000000;">show_fw_path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">points</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">],</span><span style="color: #000000;">points</span><span style="color: #0000FF;">[</span><span style="color: #000000;">22</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">])</span>

integer maxd = 0, mi, mj
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mi</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">mj</span>
for i=1 to V 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;">V</span> <span style="color: #008080;">do</span>
for j=1 to V do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">V</span> <span style="color: #008080;">do</span>
if j!=i then
<span style="color: #008080;">if</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">i</span> <span style="color: #008080;">then</span>
atom d = dist[i,j]
<span style="color: #004080;">atom</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dist</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
if d!=inf and d>maxd then
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">inf</span> <span style="color: #008080;">and</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxd</span> <span style="color: #008080;">then</span>
{maxd,mi,mj} = {d,i,j}
<span style="color: #0000FF;">{</span><span style="color: #000000;">maxd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mj</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">j</span><span style="color: #0000FF;">}</span>
end if
<span style="color: #008080;">end</span> <span style="color: #008080;">if</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 for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
printf(1,"Maximum shortest distance:\n")
<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;">"Maximum shortest distance:\n"</span><span style="color: #0000FF;">)</span>
show_fw_path(mi,mj)
<span style="color: #000000;">show_fw_path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mi</span><span style="color: #0000FF;">,</span><span style="color: #000000;">mj</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>

FloydWarshall()</lang>
<span style="color: #000000;">FloydWarshall</span><span style="color: #0000FF;">()</span>
<!--</lang>-->
{{out}}
{{out}}
<pre>
<pre>
Retrieved from "https://rosettacode.org/wiki/I%27m_a_software_engineer,_get_me_out_of_here"