How to resolve the algorithm I'm a software engineer, get me out of here step by step in the F# programming language
How to resolve the algorithm I'm a software engineer, get me out of here step by step in the F# programming language
Table of Contents
Problem Statement
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. 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), and the longest shortest route between any two points.
Extra Credit
Related tasks:
Let's start with the solution:
Step by Step solution about How to resolve the algorithm I'm a software engineer, get me out of here step by step in the F# programming language
Source code in the fsharp programming language
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")
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 ""
You may also check:How to resolve the algorithm Polynomial regression step by step in the Python programming language
You may also check:How to resolve the algorithm Time a function step by step in the Phixmonti programming language
You may also check:How to resolve the algorithm Roman numerals/Decode step by step in the 360 Assembly programming language
You may also check:How to resolve the algorithm Loops/Continue step by step in the TUSCRIPT programming language
You may also check:How to resolve the algorithm Determinant and permanent step by step in the D programming language