Created
February 13, 2012 05:14
-
-
Save jmonasterio/1813867 to your computer and use it in GitHub Desktop.
Project Euler #81 - Shortest Path in F#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Project Euler #81 - Shortest Path in F# | |
// Doesn't seem very functional, but my first shot at it. | |
// Using Dijkstra's algorithm from wikipedia. | |
let matrix = | |
File.ReadAllLines(@"Matrix.txt") |> Array.map( fun line -> line.Split(",".ToCharArray()) |> Array.map( Int32.Parse)); | |
type Coord = { | |
row: int; | |
col: int; | |
} | |
type Node = { | |
rc : Coord; | |
distance : int; | |
mutable unvisited : bool; | |
mutable tentative_distance : int; | |
} | |
let MAX_ROW = matrix.GetUpperBound(0)+1; | |
let MAX_COL = MAX_ROW; | |
let MAX_DISTANCE = Int32.MaxValue; | |
let array = Array2D.init MAX_ROW MAX_COL (fun i j -> { new Node with distance = matrix.[i].[j] and unvisited = true and tentative_distance = MAX_DISTANCE and rc = { row = i; col = j } } ); | |
let neighborNodes (c:Node) = [ | |
// Right | |
if c.rc.row < MAX_ROW-1 then | |
yield array.[c.rc.row+1,c.rc.col]; | |
// Down | |
if c.rc.col < MAX_COL-1 then | |
yield array.[c.rc.row, c.rc.col+1]; | |
]; | |
let unvisitedNodes (arr: Node[,]) = [ | |
for ii in 0..(MAX_ROW-1) do | |
for jj in 0..(MAX_COL-1) do | |
if( arr.[ii,jj].unvisited) then | |
yield arr.[ii,jj]; | |
]; | |
let nodeWithSmallestTentativeDistance (arr:Node[,]) = | |
unvisitedNodes arr |> List.minBy( fun x -> x.tentative_distance); | |
let mutable CurrentNode = array.[0,0]; | |
CurrentNode.tentative_distance <- CurrentNode.distance; | |
let DestinationNode = array.[MAX_ROW-1, MAX_COL-1]; | |
while DestinationNode.unvisited = true do | |
for n in (neighborNodes CurrentNode) do | |
//printf "%A\n" n.rc | |
if n.unvisited then | |
let tentativeDistance = CurrentNode.tentative_distance + n.distance; | |
if tentativeDistance < n.tentative_distance then | |
n.tentative_distance <- tentativeDistance; | |
CurrentNode.unvisited <- false; | |
if DestinationNode.unvisited = true then | |
CurrentNode <- nodeWithSmallestTentativeDistance array; | |
printf "Answer is: %A\n" DestinationNode.tentative_distance ; | |
printf "Done\n"; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment