# Project Euler Problem 81

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\Problem081.data" 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]

## Trackbacks & Pingbacks