Skip to content

Project Euler Problem 82

April 29, 2012

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

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\" // 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

From → Project Euler

One Comment

Trackbacks & Pingbacks

  1. Project Euler Problem 83 « In F# Major

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: