I'm a software engineer, get me out of here: Difference between revisions
No edit summary |
Realize Part 1 in F# |
||
Line 38: | Line 38: | ||
# [[Dijkstra's algorithm]] |
# [[Dijkstra's algorithm]] |
||
# [[Floyd-Warshall algorithm]] |
# [[Floyd-Warshall algorithm]] |
||
=={{header|F_Sharp|F#}}== |
|||
This task uses [http://www.rosettacode.org/wiki/Dijkstra%27s_algorithm#F.23 Dijkstra's algorithm (F#)] |
|||
This task uses [http://www.rosettacode.org/wiki/CSV_data_manipulation#F.23 readCSV (F#)] |
|||
===Part 1=== |
|||
<lang fsharp> |
|||
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") |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
[(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)] |
|||
</pre> |
Revision as of 13:24, 9 August 2018
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
- Is there any cell in the country that can not be reached from HQ?
- Which cells will it take longest to send reinforcements to from HQ?
Related tasks:
F#
This task uses Dijkstra's algorithm (F#)
This task uses readCSV (F#)
Part 1
<lang fsharp> 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") </lang>
- 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)]