Saturday, January 17, 2009

Erlang solution for Euler problem 11

In project Euler problem number 11 we are asked to find the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in a given 20 by 20 grid of numbers.

Once again, the problem is solved using the brute force method of simply trying all possible combinations of four adjacent numbers.

In previous assignment I tended to write recursion functions from scratch. In this assignment I tried to use lists and functions from the Erlang lists module (lists:seq, lists:map, and lists:max).


%% Project Euler, problem 11
%%
%% What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally)
%% in the 20×20 grid given below?

-module(euler11).
-author('Cayle Spandon').

-export([solve/0]).

-define(PRODUCT_SIZE, 4).
-define(GRID_SIZE, 20).
-define(GRID, [[08, 02, 22, 97, 38, 15, 00, 40, 00, 75, 04, 05, 07, 78, 52, 12, 50, 77, 91, 08],
[49, 49, 99, 40, 17, 81, 18, 57, 60, 87, 17, 40, 98, 43, 69, 48, 04, 56, 62, 00],
[81, 49, 31, 73, 55, 79, 14, 29, 93, 71, 40, 67, 53, 88, 30, 03, 49, 13, 36, 65],
[52, 70, 95, 23, 04, 60, 11, 42, 69, 24, 68, 56, 01, 32, 56, 71, 37, 02, 36, 91],
[22, 31, 16, 71, 51, 67, 63, 89, 41, 92, 36, 54, 22, 40, 40, 28, 66, 33, 13, 80],
[24, 47, 32, 60, 99, 03, 45, 02, 44, 75, 33, 53, 78, 36, 84, 20, 35, 17, 12, 50],
[32, 98, 81, 28, 64, 23, 67, 10, 26, 38, 40, 67, 59, 54, 70, 66, 18, 38, 64, 70],
[67, 26, 20, 68, 02, 62, 12, 20, 95, 63, 94, 39, 63, 08, 40, 91, 66, 49, 94, 21],
[24, 55, 58, 05, 66, 73, 99, 26, 97, 17, 78, 78, 96, 83, 14, 88, 34, 89, 63, 72],
[21, 36, 23, 09, 75, 00, 76, 44, 20, 45, 35, 14, 00, 61, 33, 97, 34, 31, 33, 95],
[78, 17, 53, 28, 22, 75, 31, 67, 15, 94, 03, 80, 04, 62, 16, 14, 09, 53, 56, 92],
[16, 39, 05, 42, 96, 35, 31, 47, 55, 58, 88, 24, 00, 17, 54, 24, 36, 29, 85, 57],
[86, 56, 00, 48, 35, 71, 89, 07, 05, 44, 44, 37, 44, 60, 21, 58, 51, 54, 17, 58],
[19, 80, 81, 68, 05, 94, 47, 69, 28, 73, 92, 13, 86, 52, 17, 77, 04, 89, 55, 40],
[04, 52, 08, 83, 97, 35, 99, 16, 07, 97, 57, 32, 16, 26, 26, 79, 33, 27, 98, 66],
[88, 36, 68, 87, 57, 62, 20, 72, 03, 46, 33, 67, 46, 55, 12, 32, 63, 93, 53, 69],
[04, 42, 16, 73, 38, 25, 39, 11, 24, 94, 72, 18, 08, 46, 29, 32, 40, 62, 76, 36],
[20, 69, 36, 41, 72, 30, 23, 88, 34, 62, 99, 69, 82, 67, 59, 85, 74, 04, 36, 16],
[20, 73, 35, 29, 78, 31, 90, 01, 74, 31, 49, 71, 48, 86, 81, 16, 23, 57, 05, 54],
[01, 70, 54, 71, 83, 51, 54, 69, 16, 92, 33, 48, 61, 43, 52, 01, 89, 19, 67, 48]]).

get_value(X, Y) ->
lists:nth(X, lists:nth(Y, ?GRID)).

product(XStart, YStart, XDelta, YDelta) ->
if
XStart + ?PRODUCT_SIZE * XDelta - 1 > ?GRID_SIZE ->
0;
XStart + ?PRODUCT_SIZE * XDelta - 1 < 1 ->
0;
YStart + ?PRODUCT_SIZE * YDelta - 1 > ?GRID_SIZE ->
0;
YStart + ?PRODUCT_SIZE * YDelta - 1 < 1 ->
0;
true ->
product(XStart, YStart, XDelta, YDelta, ?PRODUCT_SIZE)
end.

product(XStart, YStart, XDelta, YDelta, N) ->
V = get_value(XStart, YStart),
if
N == 1 ->
V;
N > 1 ->
V * product(XStart + XDelta, YStart + YDelta, XDelta, YDelta, N-1)
end.

highest_product(X, Y) ->
lists:max([product(X, Y, 1, 0), % horizontal,
product(X, Y, 0, 1), % vertical,
product(X, Y, 1, 1), % diagonal down right
product(X, Y, 1, -1)]). % diagonal up right

highest_product(Y) ->
lists:max(lists:map(fun(X) -> highest_product(X, Y) end, lists:seq(1, ?GRID_SIZE))).

highest_product() ->
lists:max(lists:map(fun(Y) -> highest_product(Y) end, lists:seq(1, ?GRID_SIZE))).

solve() ->
highest_product().

No comments: