Skip to content

Project Euler Problem 11

October 15, 2011

Project Euler Problem 11 did not impose any troubles for the general solution approach: we produce the sequence of all valid products and find the max of them. Apparently we can limit ourselves in generating products to the following directional moves:

  1. E – horisontal from left to right
  2. SE – diagonally down to the right
  3. S – vertical down
  4. SW – diagonally down to the left
open System
open System.IO

type Direction = E | SE | S | SW
let span = 4
let side = 20

let grid: int[,] = Array2D.zeroCreate side side

let tracer =
    dict [
        (E,[(0,0); (1,0); (2,0); (3,0)]);
        (SE,[(0,0); (1,1); (2,2); (3,3)]);
        (S,[(0,0); (0,1); (0,2); (0,3)]);
        (SW,[(0,0); (-1,1); (-2,2); (-3,3)]);
    ]

let foldDirection direction x y =
    tracer.Item(direction)
    |> List.fold (fun acc (dx,dy) -> acc * grid.[x + dx, y + dy]) 1

let run direction x y =
    match direction with
    | E when x  foldDirection E x y
    | SE when x  foldDirection SE x y
    | S when y  foldDirection S x y
    | SW when x >= span - 1 && y  foldDirection SW x y
    | _ -> Int32.MinValue

// Fill the grid from file
let fileContents = File.ReadAllLines(@"..\..\..\Datafiles\grid.data")
for x = 0 to side - 1 do
    let inputLine = fileContents.[x].Split(' ')
    for y = 0 to side - 1 do
        grid.[y,x] <- Convert.ToInt32(inputLine.[y])

let products =
    [
        for y in 0 .. side - 1 do
            for x in 0 .. side - 1 do
                yield run E x y; yield run SE x y;
                yield run S x y; yield run SW x y; 
    ]

let problem011 () =
    products |> Seq.max

A bit on bulky side; someday I may look into using an active pattern allowing to get rid of guards and squeeze the code a bit.

Advertisements

From → Project Euler

Leave a Comment

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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: