patternMinor
Path sum - Dijkstra's algorithm in F#
Viewed 0 times
algorithmpathdijkstrasum
Problem
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.
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 [(x + 1, y); (x, y + 1)]
| x, y when (x [(x + 1, y)]
| x, y when (y [(x, y + 1)]
| _ -> []
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 331Find 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 [(x + 1, y); (x, y + 1)]
| x, y when (x [(x + 1, y)]
| x, y when (y [(x, y + 1)]
| _ -> []
Solution
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
It should not be surprising that more appropriate algorithm choice yields an overwhelming performance gain:
versus your solution yielding
In the light of this finding the further considerations about your solution may not matter.
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: 0versus your solution yielding
Real: 00:00:01.797, CPU: 00:00:01.778, GC gen0: 1, gen1: 0, gen2: 0In the light of this finding the further considerations about your solution may not matter.
Code Snippets
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]Real: 00:00:00.014, CPU: 00:00:00.015, GC gen0: 1, gen1: 1, gen2: 0Real: 00:00:01.797, CPU: 00:00:01.778, GC gen0: 1, gen1: 0, gen2: 0Context
StackExchange Code Review Q#12687, answer score: 6
Revisions (0)
No revisions yet.