Jump to content

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 13:17, 30 August 2018

6,583 bytes added ,  5 years ago
→‎{{header|Phix}}
Line 147:
......00001120000......
.........00000.........""",'\n')
 
constant width = length(gmooh[1]),
height = length(gmooh),
Line 153:
{-1, 0}, {+1, 0},
{-1,+1},{0,+1},{+1,+1}}
 
sequence routes -- {cost,fromy,fromx} for each gmooh[][].
 
procedure search(integer y, x)
-- simple breasthbreadth-first search, populates routes
-- (this isn't strictly dijkstra, because graph edges are not weighted)
integer cost = 0
sequence route = {{y,x}},
thisnext = {}, -- (at cost)
next = {} -- (at cost+1)
routes = repeat(repeat(0,width),height)
routes[y,x] = {0,{}y,x} -- zero-cost the starting point
while 1 do
integer n = gmooh[y,x]-'0'
Line 170:
integer {rx,ry} = {x+n*dx,y+n*dy}
if rx>=1 and rx<=width
and ry>=1 and ry<=height then
and gmooh[ry,rx]>='0' then
object ryx = routes[ry,rx]
if ryx=0
or ryx[1]>cost+1 then
sequence newrouteroutes[ry,rx] = append(route,{rycost+1,rxy,x})
routes[ry,rx] = {cost+1,newroute}
if gmooh[ry,rx]>'0' then
next = append(next,{cost+1,ry,rx,newroute})
-- (if the graph was weighted, at this point
-- that would get shuffled up into place.)
end if
end if
end if
end for
if length(thisnext)=0 then exit end if
{cost,y,x} = if length(next)=0 then exit end if[1]
next cost += 1next[2..$]
this = next
next = {}
end if
{y,x,route} = this[1]
this = this[2..$]
end while
end procedure
 
function get_route(sequence yx)
procedure show_shortest_route_to_safety()
integer {y,x} = yx, cost
sequence res = {{y,x}}
while 1 do
{cost,y,x} = routes[y,x]
if cost=0 then exit end if
res = prepend(res,{y,x})
end while
return res
end function
 
procedure show_shortest_routes_to_safety()
integer shortest = 9999
sequence routeres = {}
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
and integer cost = ryx[1]<shortest then
{shortest,route}if cost<=shortest ryxthen
if cost<shortest then
res = {}
shortest = cost
end if
res = append(res,{y,x})
end if
end if
end if
end for
end for
string {areis,s} = iff(length(res)>1?{"are","s"}:{"is",""})
?{"show_shortest_route_to_safety",shortest,route}
printf(1,"There %s %d shortest route%s of %d days to safety:\n",{areis,length(res),s,shortest})
for i=1 to length(res) do
?get_route(res[i])
end for
end procedure
 
Line 220 ⟶ 238:
end for
end for
?{puts(1,"The following cells are unreachable:\n",res})
?res
end procedure
 
procedure show_longest()
integer longest = 0
Line 232 ⟶ 251:
if ryx!=0 then
integer rl = ryx[1]
if rl>=longest then
resif =rl>longest {{y,x}}then
longest res = rl{}
elsif rl= longest then= rl
end if
res = append(res,{y,x})
end if
Line 242 ⟶ 262:
end for
end for
printf(1,"There are %d cells that take %d days to send reinforcements to\n",{length(res),longest})
?{"show_longest",res}
for i=1 to length(res) do
?get_route(res[i])
end for
end procedure
 
procedure main()
search(12,12)
show_shortest_routes_to_safety()
show_shortest_route_to_safety()
 
-- see also below
search(22,12)
?{puts(1,"The shortest route from 22,12 to 2,12:\n",routes[2,12]})
search?get_route({2,12})
?{"shortest route from 2,12 to 22,12",routes[22,12]}
 
search(2,12)
puts(1,"The shortest route from 2,12 to 22,12:\n")
?get_route({22,12})
search(12,12)
-- </see also below>
 
show_unreachable()
show_longest()
 
end procedure
main()</lang>
{{out}}
Note: Phix indexes are 1-based and therefore so too are these results.
<pre>
There are 40 shortest routes of 4 days to safety:
{{12,12},{12,13},{9,10},{15,4},{12,1}}
{{12,12},{11,12},{8,9},{8,6},{13,1}}
{{12,12},{13,11},{14,11},{14,6},{14,1}}
{{12,12},{12,13},{9,10},{9,4},{7,2}}
{{12,12},{12,13},{9,10},{9,4},{9,2}}
{{12,12},{11,11},{9,9},{13,5},{10,2}}
{{12,12},{11,11},{13,9},{17,5},{14,2}}
{{12,12},{11,11},{9,9},{13,5},{16,2}}
{{12,12},{11,11},{13,9},{17,5},{17,2}}
{{12,12},{11,11},{9,9},{9,5},{7,3}}
{{12,12},{13,12},{16,9},{16,6},{19,3}}
{{12,12},{12,11},{11,10},{10,10},{4,4}}
{{12,12},{11,12},{14,9},{15,8},{19,4}}
{{12,12},{11,11},{9,11},{6,8},{3,5}}
{{12,12},{11,12},{8,9},{5,6},{4,5}}
{{12,12},{11,11},{13,9},{17,5},{20,5}}
{{12,12},{11,12},{8,9},{8,6},{3,6}}
{{12,12},{11,12},{8,12},{8,13},{2,7}}
{{12,12},{11,11},{9,9},{5,9},{2,9}}
{{12,12},{11,11},{9,11},{6,14},{2,10}}
{{12,12},{12,13},{15,10},{19,14},{23,10}}
{{12,12},{13,12},{16,9},{19,12},{23,12}}
{{12,12},{11,11},{9,13},{7,13},{1,13}}
{{12,12},{11,11},{9,11},{6,14},{2,14}}
{{12,12},{12,13},{15,10},{19,14},{23,14}}
{{12,12},{11,12},{8,9},{5,12},{2,15}}
{{12,12},{12,13},{9,10},{3,16},{2,16}}
{{12,12},{13,11},{14,11},{19,16},{22,16}}
{{12,12},{12,13},{9,10},{3,16},{2,17}}
{{12,12},{12,13},{9,10},{3,16},{3,17}}
{{12,12},{11,11},{13,9},{17,13},{21,17}}
{{12,12},{13,12},{13,15},{9,19},{4,19}}
{{12,12},{12,13},{15,16},{17,16},{20,19}}
{{12,12},{11,12},{14,12},{18,16},{21,19}}
{{12,12},{13,12},{10,15},{7,18},{5,20}}
{{12,12},{11,12},{11,15},{13,17},{17,21}}
{{12,12},{12,13},{12,16},{12,18},{8,22}}
{{12,12},{13,12},{13,15},{17,19},{14,22}}
{{12,12},{12,13},{12,16},{12,18},{16,22}}
{{12,12},{13,12},{13,15},{17,19},{17,22}}
The shortest route from 22,12 to 2,12:
{{22,12},{21,11},{20,10},{19,10},{14,5},{7,12},{5,12},{2,12}}
The shortest route from 2,12 to 22,12:
{{2,12},{3,11},{6,14},{10,10},{16,4},{21,9},{21,11},{22,12}}
The following cells are unreachable:
{{5,4},{3,19},{19,21}}
There are 5 cells that take 6 days to send reinforcements to
{{12,12},{11,11},{13,9},{17,13},{21,13},{22,12},{23,13}}
{{12,12},{12,13},{15,16},{17,18},{18,17},{19,17},{21,15}}
{{12,12},{13,12},{10,15},{7,18},{5,18},{4,18},{4,20}}
{{12,12},{11,12},{8,12},{8,13},{8,19},{8,21},{7,21}}
{{12,12},{11,12},{11,15},{13,17},{13,21},{16,21},{18,21}}
</pre>
Alternative using Floyd-Warshall for Part 2, and finding the longest shortest path between any two points.
<lang Phix>--(same constants as above: gmooh, width, height, d)
constant inf = 1e300*1e300
 
sequence dist, next, pmap = {}
function fw_path(integer u, v)
sequence res = {}
if next[u,v]!=null then
sequence path = {sprintf("{%d,%d}",pmap[u])}
while u!=v do
u = next[u,v]
path = append(path,sprintf("{%d,%d}",pmap[u]))
end while
res = join(path,"->")
end if
return res
end function
 
procedure show_fw_path(integer u, v)
printf(1,"{%d,%d}->{%d,%d} %2d %s\n",pmap[u]&pmap[v]&{dist[u,v],fw_path(u,v)})
end procedure
procedure FloydWarshall()
integer point = 0
sequence weights = {},
points = repeat(repeat(0,width),height)
-- First number the points...
for x=1 to width do
for y=1 to height do
if gmooh[y,x]>='0' then
point += 1
points[y,x] = point
pmap = append(pmap,{y,x})
end if
end for
end for
-- ...and then a set of edges (all of which have a "weight" of 1 day)
for x=1 to width do
for y=1 to height do
if gmooh[y,x]>'0' then
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
and gmooh[ry,rx]>='0' then
-- weights = append(weights,{points[y,x],points[ry,rx],1})
weights = append(weights,{points[y,x],points[ry,rx]})
end if
end for
end if
end for
end for
-- Before applying Floyd-Warshall
integer V = length(pmap)
dist = repeat(repeat(inf,V),V)
next = repeat(repeat(null,V),V)
for k=1 to length(weights) do
-- integer {u,v,w} = weights[k]
integer {u,v} = weights[k]
-- dist[u,v] := w -- the weight of the edge (u,v)
dist[u,v] := 1 -- the weight of the edge (u,v)
next[u,v] := v
end for
-- standard Floyd-Warshall implementation,
-- with the optimisation of avoiding processing of self/infs,
-- which surprisingly makes quite a noticeable difference.
for k=1 to V do
for i=1 to V do
if i!=k and dist[i,k]!=inf then
for j=1 to V do
if j!=i and j!=k and dist[k,j]!=inf then
atom d = dist[i,k] + dist[k,j]
if d<dist[i,j] then
dist[i,j] := d
next[i,j] := next[i,k]
end if
end if
end for
end if
end for
end for
show_fw_path(points[22,12],points[2,12])
show_fw_path(points[2,12],points[22,12])
 
integer maxd = 0, mi, mj
for i=1 to V do
for j=1 to V do
if j!=i then
atom d = dist[i,j]
if d!=inf and d>maxd then
{maxd,mi,mj} = {d,i,j}
end if
end if
end for
end for
printf(1,"Maximum shortest distance:\n")
show_fw_path(mi,mj)
end procedure
 
FloydWarshall()</lang>
{{out}}
<pre>
{"show_shortest_route_to_safety"22,4,{{12}->{2,12}, 7 {1222,1312},->{921,1011}->{20,11}->{15,411}->{11,11}->{129,19}->{5,9}->{2,12}
{"shortest route from 2,12}->{22,12} to 2,12",{7, {{222,12},->{213,11},->{206,1014},->{1910,10},->{1416,54},->{721,129},->{521,1211},->{222,12}}}}
Maximum shortest distance:
{"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}}}}
{8,4}->{21,15} 9 {8,4}->{9,5}->{11,7}->{12,8}->{16,12}->{17,12}->{18,13}->{18,17}->{19,17}->{21,15}
{"unreachable",{{5,4},{3,19},{19,21}}}
{"show_longest",{{23,13},{21,15},{4,20},{7,21},{18,21}}}
</pre>
Petelomax
7,822

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/283976"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information