I'm a software engineer, get me out of here

From Rosetta Code
I'm a software engineer, get me out of here is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Your latest contract has hit a snag. You came to update the army payroll system, but awoke this morning to the sound of mortars landing not far away and panicked generals banging on you door. The President has loaded his gold on trucks and needs to find the shortest route to safety. You are given the following map. The top left hand corner is (0,0). You and The President are located at HQ in the centre of the country (11,11). Cells marked 0 indicate safety. Numbers other than 0 indicate the number of cells that his party will travel in a day in any direction up, down, left, right, or diagonally.

         00000         
      00003130000      
    000321322221000    
   00231222432132200   
  0041433223233211100  
  0232231612142618530  
 003152122326114121200 
 031252235216111132210 
 022211246332311115210 
00113232262121317213200
03152118212313211411110
03231234121132221411410
03513213411311414112320
00427534125412213211400
 013322444412122123210 
 015132331312411123120 
 003333612214233913300 
  0219126511415312570  
  0021321524341325100  
   00211415413523200   
    000122111322000    
      00001120000      
         00000         

Part 1 Use Dijkstra's algorithm to find a list of the shortest routes from HQ to safety.
Part 2
Six days later and you are called to another briefing. The good news is The President and his gold are safe, so your invoice may be paid if you can get out of here. To do this a number of troop repositions will be required. It is concluded that you need to know the shortest route from each cell to every other cell. You decide to use Floyd's algorithm. Print the shortest route from (21,11) to (1,11) and from (1,11) to (21,11).
Extra Credit

  1. Is there any cell in the country that can not be reached from HQ?
  2. Which cells will it take longest to send reinforcements to from HQ?


Related tasks:

  1. Dijkstra's algorithm
  2. Floyd-Warshall algorithm

F#[edit]

This task uses Dijkstra's algorithm (F#)

This task uses readCSV (F#)

Part 1[edit]

 
let safety=readCSV '\t' "gmooh.dat"|>Seq.choose(fun n->if n.value="0" then Some (n.row,n.col) else None)
let board=readCSV '\t' "gmooh.dat"|>Seq.choose(fun n->match n.value with |"0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9" as g->Some((n.row,n.col),int g)|_->None)|>Map.ofSeq
let adjacent((n,g),v)=List.choose(fun y->if y=(n,g) then None else match Map.tryFind y board with |None->None|_->Some ((y),1)) [(n+v,g);(n-v,g);(n,g+v);(n,g-v);(n+v,g+v);(n+v,g-v);(n-v,g+v);(n-v,g-v);]
let adjacencyList=new System.Collections.Generic.Dictionary<(int*int),list<(int*int)*int>>()
let rec mkAdj start=
let n=((start),Map.find start board)
let g=adjacent n
adjacencyList.Add((fst n),g)
List.iter(fun ((n),_)->if (not (adjacencyList.ContainsKey n )) then mkAdj n) g
mkAdj (11,11)
let nodes=adjacencyList.Keys |> List.ofSeq
let G=nodes |>List.collect(fun n->List.map(fun (n',g)->(((n),(n')),g))(adjacencyList.Item n))|>Map.ofList
let paths=Dijkstra nodes G (11,11)
let _,res=safety|>Seq.choose(fun n->paths n) |> Seq.groupBy(fun n->List.length n)|>Seq.minBy fst
res |> Seq.iter (printfn "%A")
 
Output:
[(11, 11); (10, 11); (7, 11); (6, 12); (0, 12)]
[(11, 11); (10, 11); (7, 11); (7, 12); (1, 6)]
[(11, 11); (10, 10); (8, 8); (4, 8); (1, 8)]
[(11, 11); (11, 12); (8, 9); (2, 9); (1, 9)]
[(11, 11); (10, 10); (8, 10); (5, 13); (1, 13)]
[(11, 11); (10, 11); (7, 8); (4, 11); (1, 14)]
[(11, 11); (11, 12); (8, 9); (2, 15); (1, 15)]
[(11, 11); (11, 12); (8, 9); (2, 15); (1, 16)]
[(11, 11); (10, 10); (8, 10); (5, 7); (2, 4)]
[(11, 11); (10, 11); (7, 8); (7, 5); (2, 5)]
[(11, 11); (11, 12); (8, 15); (9, 16); (2, 16)]
[(11, 11); (12, 10); (11, 9); (9, 9); (3, 3)]
[(11, 11); (10, 11); (7, 8); (4, 5); (3, 4)]
[(11, 11); (12, 11); (12, 14); (8, 18); (3, 18)]
[(11, 11); (12, 11); (9, 14); (6, 17); (4, 19)]
[(11, 11); (11, 12); (8, 9); (8, 3); (6, 1)]
[(11, 11); (12, 11); (12, 8); (8, 4); (6, 2)]
[(11, 11); (11, 12); (11, 15); (11, 17); (7, 21)]
[(11, 11); (11, 12); (8, 9); (8, 3); (8, 1)]
[(11, 11); (12, 11); (12, 8); (12, 4); (9, 1)]
[(11, 11); (11, 12); (8, 9); (14, 3); (11, 0)]
[(11, 11); (10, 11); (7, 8); (7, 5); (12, 0)]
[(11, 11); (12, 10); (13, 10); (13, 5); (13, 0)]
[(11, 11); (12, 11); (12, 8); (16, 4); (13, 1)]
[(11, 11); (12, 11); (12, 14); (16, 18); (13, 21)]
[(11, 11); (12, 11); (12, 8); (12, 4); (15, 1)]
[(11, 11); (11, 12); (11, 15); (11, 17); (15, 21)]
[(11, 11); (12, 11); (12, 8); (16, 4); (16, 1)]
[(11, 11); (10, 11); (10, 14); (12, 16); (16, 20)]
[(11, 11); (12, 11); (12, 14); (16, 18); (16, 21)]
[(11, 11); (12, 11); (15, 8); (15, 5); (18, 2)]
[(11, 11); (10, 11); (13, 8); (14, 7); (18, 3)]
[(11, 11); (12, 11); (15, 8); (18, 5); (19, 4)]
[(11, 11); (11, 12); (14, 15); (16, 15); (19, 18)]
[(11, 11); (12, 11); (15, 11); (16, 12); (20, 16)]
[(11, 11); (10, 11); (13, 11); (17, 15); (20, 18)]
[(11, 11); (12, 10); (13, 10); (18, 15); (21, 15)]
[(11, 11); (11, 12); (14, 9); (18, 13); (22, 9)]
[(11, 11); (12, 11); (15, 8); (18, 11); (22, 11)]
[(11, 11); (11, 12); (14, 9); (18, 13); (22, 13)]

Part 2[edit]

This task uses Floyd-Warshall algorithm#F.23

 
let board=readCSV '\t' "gmooh.dat"|>Seq.choose(fun n->match n.value with |"0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9" as g->Some((n.row,n.col),int g)|_->None)|>Map.ofSeq
let nodes=board|>Seq.map(fun n->n.Key)|>Set.ofSeq
let adjacent (n,g) v=List.choose(fun y->if y=(n,g) then None else match Set.contains y nodes with |true->Some ((y),1)|_->None) [(n+v,g);(n-v,g);(n,g+v);(n,g-v);(n+v,g+v);(n+v,g-v);(n-v,g+v);(n-v,g-v);]
let adjacencyList=board |>Seq.collect (fun n->Seq.map(fun ((n'),g')->((n.Key,n'),g'))(adjacent n.Key n.Value))|> Map.ofSeq
let _,paths=Floyd (nodes|>Set.toArray) adjacencyList
paths (21,11) (1,11) |>Seq.iteri(fun n g->if n>0 then printf "->"; printf "%A" g else printf "%A" g) ; printfn ""
paths (1,11) (21,11) |>Seq.iteri(fun n g->if n>0 then printf "->"; printf "%A" g else printf "%A" g) ; printfn ""
 
Output:
(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)

Phix[edit]

Using a simple breadth-first search. Parts 1 and 2 and extra credit.

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()

Note: Phix indexes are 1-based and therefore so too are these results.

Output:
{"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}}}