5
\$\begingroup\$

I'm learning F# and I've decided to solve Project Euler's Problem #81 with Dijkstra's algorithm.

In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.

131   673 234 103 18
201   96  342 965 150
630   803 746 422 111
537   699 497 121 956
805   732 524 37  331

Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, from the top left to the bottom right by only moving right and down.

Are there any obvious mistakes, inefficiency, any obvious possible improvements, any non-idiomatic use of the F# language?

open System
open System.IO
open Microsoft.FSharp.Collections

// Solving Project Euler #81 with Dijkstra's algorithm
// http://projecteuler.net/problem=81
// Explanation of the algorithm can be found here (Dijkstra is A* with H = 0)
// http://www.policyalmanac.org/games/aStarTutorial.htm

// The costs are provided in a text file and are comma-separated
// We read them into a jagged array of ints
let costs = File.ReadAllLines("matrix.txt")
            |> Array.map(fun line -> line.Split(',') |> Array.map int32)
let height = costs.Length;
let width = costs.[0].Length;


// A node has fixed coords, but both its parent and cost can be changed
type Node = { 
    Coords: int*int
    mutable Parent: Node
    mutable Cost: int 
    }        

// The total cost of moving to a node is the cost of moving to its parent
// plus the inherent cost of the node as given by the file
let cost srcNode (x, y) =
    srcNode.Cost + costs.[y].[x]

// This function returns the next nodes to explore
// In this particular problem, we can only move down or right (no diagonals either)
let neighbours node =
    let coords = function
        | x, y when (x < width - 1 && y < height - 1) -> [(x + 1, y); (x, y + 1)]
        | x, y when (x < width - 1) -> [(x + 1, y)]
        | x, y when (y < height - 1) -> [(x, y + 1)]
        | _ -> []
    coords(node.Coords) |> List.map (fun coord -> { node with Coords = coord; 
                                                                Parent = node; 
                                                                Cost = cost node coord })

// Start is top-left; end is bottom-right
let rec startNode = { Coords = 0, 0; Parent = startNode; Cost = costs.[0].[0] }
let rec endNode = { Coords = width - 1, height - 1; Parent = endNode; Cost = Int32.MaxValue }
let currentNode = startNode

let openSet = new ResizeArray<Node>()
let closedSet = new ResizeArray<Node>()

// returns whether node exists in set
let existsIn set node = 
    set |> Seq.exists(fun n -> n.Coords = node.Coords)

// This is the main function. It returns the path as a list of nodes.
let findPath() =
    // 1) Add the starting square (or node) to the open list.
    openSet.Add(startNode)

    // 2) Repeat the following:
    while not(endNode |> existsIn closedSet) do
        // a) Look for the lowest cost node on the open list. 
        // We refer to this as the current node.
        let currentNode = openSet |> Seq.minBy (fun node -> node.Cost)
        // b) Switch it to the closed list.
        // Note that using "Remove" would cause Stackoverflow with the starting node
        // since it is defined recursively
        openSet.RemoveAll(fun node -> node.Coords = currentNode.Coords) |> ignore
        closedSet.Add(currentNode)
        // c) For each of the nodes adjacent to this current node …
        //    If it is not walkable or if it is on the closed list, ignore it.
        let neighbourNodes = neighbours currentNode |> List.filter ((existsIn closedSet) >> not)
        for node in neighbourNodes do            
            // If it isn’t on the open list, add it to the open list. 
            // Make the current node the parent of this node. 
            // Record the cost of the node. 
            match openSet |> Seq.tryFind (fun n -> n.Coords = node.Coords) with
            | None -> (openSet.Add(node)
                       node.Parent <- currentNode
                       node.Cost <- cost currentNode node.Coords)
            // If it is on the open list already, check to see if this path to that node is better.
            // A lower G cost means that this is a better path. 
            // If so, change the parent of the square to the current square, 
            // and recalculate the G and F scores of the square. 
            | Some(n) -> (let newCost = cost currentNode n.Coords
                          if newCost < n.Cost then
                              n.Parent <- currentNode
                              n.Cost <- newCost)

    // 3) Save the path. Working backwards from the target square, 
    // go from each square to its parent square until you reach the starting square. 
    // That is your path. 
    let rec walkBack node =
        seq {
            if node.Coords <> startNode.Coords then
                yield! walkBack node.Parent
            yield node
        }
    walkBack (closedSet.Find(fun n -> n.Coords = endNode.Coords))

// Execute and print!
do
    let path = findPath()
    for n in path do
        let x, y = n.Coords
        printfn "%A %A" n.Coords costs.[y].[x]
    printfn "Total cost : %A" (Seq.last path).Cost
\$\endgroup\$

migrated from stackoverflow.com Jun 18 '12 at 13:25

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ "Code Review - Stack Exchange is for sharing code from projects you are working on" -> This is not a project I'm working on. It's a short piece of code I wrote in an hour. \$\endgroup\$ – Dr_Asik Jun 16 '12 at 4:13
  • \$\begingroup\$ Given that you state that you are looking for a code review, arguably, codereview seems a better fit. \$\endgroup\$ – Mathias Jun 16 '12 at 4:21
  • \$\begingroup\$ Ok I don't state it anymore. Happy? My question would be off-topic on codereview by their own rules. \$\endgroup\$ – Dr_Asik Jun 16 '12 at 4:22
  • \$\begingroup\$ How exactly do you think your rewording is any more fit for SO? "This question is ambiguous, vague, incomplete, overly broad, or rhetorical" \$\endgroup\$ – ildjarn Jun 16 '12 at 4:35
  • 3
    \$\begingroup\$ @Dr_Asik - there isn't really any good answer - there are many possible performance improvements that would make the code less idiomatic and also more idiomatic methods which are slower. As a result, any answer is subjective, which is not the sort of question for SO \$\endgroup\$ – John Palmer Jun 16 '12 at 5:09
6
\$\begingroup\$

Apparently there is a strong opinion that this is not a good question for SO, hence no good answer may be given. Nevertheless, I'll try to approach it from efficiency side.

Regardless of quality of given implementation of Dijkstra's algorithm it may be not a good approach for solving Project Euler Problem 81. The latter has specifics allowing for much shorter and significantly more effective imperative greedy solution. Assuming function getData("matrix.txt, costs) can populate Array2D of costs, the rest of the solution is just:

let problemEuler81() =
    let side = 80
    let costs = Array2D.zeroCreate side side
    getData("matrix.txt", costs)
    for i = side - 2 downto 0 do
        costs.[side-1,i] <- costs.[side-1,i] + costs.[side-1,i+1]
        costs.[i,side-1] <- costs.[i,side-1] + costs.[i+1,side-1]

    for i = side - 2 downto 0 do
        for j = side - 2 downto 0 do
            costs.[i,j] <- costs.[i,j] + (min costs.[i+1,j] costs.[i,j+1])

    printfn "%A" costs.[0, 0]

It should not be surprising that more appropriate algorithm choice yields an overwhelming performance gain:

Real: 00:00:00.014, CPU: 00:00:00.015, GC gen0: 1, gen1: 1, gen2: 0

versus your solution yielding

Real: 00:00:01.797, CPU: 00:00:01.778, GC gen0: 1, gen1: 0, gen2: 0

In the light of this finding the further considerations about your solution may not matter.

\$\endgroup\$
  • \$\begingroup\$ Thanks for answering. I'm not sure why your solution works, could you explain it shortly? I tried to code for clarity and conciseness rather than performance; I didn't use a priority queue as is customary for instance, so the performance is probably not representative of Dijkstra's algorithm. \$\endgroup\$ – Dr_Asik Jun 16 '12 at 15:44
  • 1
    \$\begingroup\$ You can find the algorithm's detailed description here. \$\endgroup\$ – Gene Belitski Jun 18 '12 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.