Project Euler Problem 82

Project Euler Problem 82 is an extension of Project Euler Problem 81 that requires extending the solution approach accordingly.

Let’s use pretty much the same dynamic programming approach as in the previous problem solution, but this time we’ll build the solution calculating shortest paths for each column of the source matrix moving from rightmost column to the first on the left column by column.

While working on a certain column we first traverse our vector of current shortest paths from top to bottom setting for each cell if stepping right is better, than stepping up. Then we traverse the same vector and column bottom-up setting for each cell if stepping down is better, than the whatever course we picked on the first pass.

When eventually we finish processing the leftmost column the minimum element of vector of shortest paths will be the solution.

open System.IO

[<Literal>]
let SIDE = 80
let matrix: int[,] = Array2D.zeroCreate SIDE SIDE
let shortest: int[] = Array.zeroCreate SIDE

let getData (path: string) =
    use sr = new StreamReader(path)
    let line, col = ref 0, ref 0
    while not sr.EndOfStream do
        col := 0
        sr.ReadLine().Split(',') |> Array.iter (fun x -> matrix.[!line, !col] <- int x; incr col)
        incr line

let problem082() =
    getData @"..\..\..\Datafiles\Problem081.data" // same data P.81 & 82
    List.iter (fun row -> shortest.[row] <- matrix.[row, SIDE-1]) [0..SIDE-1]
    List.iter (fun col ->
        shortest.[0] <- shortest.[0] + matrix.[0, col]
        List.iter (fun i -> shortest.[i] <- matrix.[i, col] + min shortest.[i-1] shortest.[i]) [1..SIDE-1]
        List.iter (fun i -> shortest.[i] <- min shortest.[i] (shortest.[i+1] + matrix.[i, col])) [SIDE-2..-1..0]
        ) [SIDE-2..-1..0]
    Array.min shortest