Skip to content

Instantly share code, notes, and snippets.

@jmonasterio
Created February 13, 2012 05:14
Show Gist options
  • Save jmonasterio/1813867 to your computer and use it in GitHub Desktop.
Save jmonasterio/1813867 to your computer and use it in GitHub Desktop.
Project Euler #81 - Shortest Path in F#
// 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