Skip to content

Project Euler Problem 81

March 28, 2012

Project Euler Problem 81 solution approach can be built on walking the matrix backwards from bottom right to top left at each point greedily picking the path to the target of the minimal weight (remember that at each point we have a choice of no more, than two allowed steps). When eventually we reach the top left cell the minimal weight there represented by min(matrix[0,1], matrix[1,0]) will be the problem answer.
As to the process of walking matrix back, first we fill cells of the rightmost column from bottom to top and cells of bottom row from right to left as involved cells allow only single path to the target. Then for each unprocessed rightmost column and lowest row we can fill them bottom up and right to left respectively by adding to original cell contents the minimum of two numbers taken one from down and one from right cells.
The process ends when we reach the matrix top left cell:

open System.IO
open System

let side = 80
let matrix: int[,] = Array2D.zeroCreate side side

let getData (path: string) =
    use sr = new StreamReader(path)
    let line = ref 0
    let col = 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 problem081() =
    getData @"..\..\..\Datafiles\"
    for i = side - 2 downto 0 do
        matrix.[side - 1, i] <- matrix.[side - 1, i] + matrix.[side - 1, i+1]
        matrix.[i,side - 1] <- matrix.[i,side - 1] + matrix.[i+1, side - 1]

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

    matrix.[0, 0]

From → Project Euler

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: