I'm a software engineer, get me out of here: Difference between revisions
I'm a software engineer, get me out of here (view source)
Revision as of 20:57, 17 August 2018
, 5 years ago→{{header|Phix}}
(→{{header|F_Sharp|F#}}: Complete Part 2) |
|||
Line 119:
(20, 10)->(19, 9)->(18, 9)->(13, 4)->(6, 11)->(4, 11)->(1, 11)
(2, 10)->(5, 13)->(9, 9)->(15, 3)->(20, 8)->(20, 10)->(21, 11)
</pre>
=={{header|Phix}}==
Using a simple breadth-first search. Parts 1 and 2 and extra credit.
<lang Phix>constant gmooh = split("""
.........00000.........
......00003130000......
....000321322221000....
...00231222432132200...
..0041433223233211100..
..0232231612142618530..
.003152122326114121200.
.031252235216111132210.
.022211246332311115210.
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
.013322444412122123210.
.015132331312411123120.
.003333612214233913300.
..0219126511415312570..
..0021321524341325100..
...00211415413523200...
....000122111322000....
......00001120000......
.........00000.........""",'\n')
constant width = length(gmooh[1]),
height = length(gmooh),
d = {{-1,-1},{0,-1},{+1,-1},
{-1, 0}, {+1, 0},
{-1,+1},{0,+1},{+1,+1}}
sequence routes
procedure search(integer y, x)
-- simple breasth-first search, populates routes
integer cost = 0
sequence route = {{y,x}},
this = {}, -- (at cost)
next = {} -- (at cost+1)
routes = repeat(repeat(0,width),height)
routes[y,x] = {0,{}} -- zero-cost the starting point
while 1 do
integer n = gmooh[y,x]-'0'
for di=1 to length(d) do
integer {dx,dy} = d[di]
integer {rx,ry} = {x+n*dx,y+n*dy}
if rx>=1 and rx<=width
and ry>=1 and ry<=height then
object ryx = routes[ry,rx]
if ryx=0
or ryx[1]>cost+1 then
sequence newroute = append(route,{ry,rx})
routes[ry,rx] = {cost+1,newroute}
if gmooh[ry,rx]>'0' then
next = append(next,{ry,rx,newroute})
end if
end if
end if
end for
if length(this)=0 then
if length(next)=0 then exit end if
cost += 1
this = next
next = {}
end if
{y,x,route} = this[1]
this = this[2..$]
end while
end procedure
procedure show_shortest_route_to_safety()
integer shortest = 9999
sequence route = {}
for x=1 to width do
for y=1 to height do
if gmooh[y,x]='0' then
object ryx = routes[y,x]
if ryx!=0
and ryx[1]<shortest then
{shortest,route} = ryx
end if
end if
end for
end for
?{"show_shortest_route_to_safety",shortest,route}
end procedure
procedure show_unreachable()
sequence res = {}
for x=1 to width do
for y=1 to height do
if gmooh[y,x]>='0'
and routes[y,x]=0 then
res = append(res,{y,x})
end if
end for
end for
?{"unreachable",res}
end procedure
procedure show_longest()
integer longest = 0
sequence res = {}
for x=1 to width do
for y=1 to height do
if gmooh[y,x]>='0' then
object ryx = routes[y,x]
if ryx!=0 then
integer rl = ryx[1]
if rl>longest then
res = {{y,x}}
longest = rl
elsif rl=longest then
res = append(res,{y,x})
end if
end if
end if
end for
end for
?{"show_longest",res}
end procedure
procedure main()
search(12,12)
show_shortest_route_to_safety()
search(22,12)
?{"shortest route from 22,12 to 2,12",routes[2,12]}
search(2,12)
?{"shortest route from 2,12 to 22,12",routes[22,12]}
search(12,12)
show_unreachable()
show_longest()
end procedure
main()</lang>
Note: Phix indexes are 1-based and therefore so too are these results.
{{out}}
<pre>
{"show_shortest_route_to_safety",4,{{12,12},{12,13},{9,10},{15,4},{12,1}}}
{"shortest route from 22,12 to 2,12",{7,{{22,12},{21,11},{20,10},{19,10},{14,5},{7,12},{5,12},{2,12}}}}
{"shortest route from 2,12 to 22,12",{7,{{2,12},{3,11},{6,14},{10,10},{16,4},{21,9},{21,11},{22,12}}}}
{"unreachable",{{5,4},{3,19},{19,21}}}
{"show_longest",{{23,13},{21,15},{4,20},{7,21},{18,21}}}
</pre>
| |||