[Haskell-cafe] Hints for Euler Problem 11

[Krzysztof Kościuszkiewicz]

On Thu, Jul 19, 2007 at 11:39:26PM -0400, Ronald Guida wrote:

> In Problem 11, a 20x20 grid of numbers is given, and the problem is to
> find the largest product of four numbers along a straight line in the
> grid.  The line can be horizontal, vertical, or diagonal.

I found it easier to work with Arrays in this example:

> > grid :: [[Integer]]
> > grid = readGrid gridText

> gridArr :: [[Integer]] -> Array (Int, Int) Integer
> gridArr = array ((0, 0), (19, 19))

Then you can define a handy function for extracting whatever combination of
indices you need:

> extractBy :: (Ix i, Ord a) => ((i, e) -> a) -> Array i e -> [[e]]
> extractBy f = 
>   map (map snd) . groupBy (equals f) . sortBy (comparing f) . assocs

And from there on you can work your way out of this problem by replacing
??? with functions that map ((i, j), v) to some value common for same
row, col, or diagonal:

> rows = extractBy ???
> cols = extractBy ???
> diags = extractBy ???
> adiags = extractBy ???

> > makeGroups :: Int -> [a] -> [[a]]
> > makeGroups 0 _ = []
> > makeGroups n xs = let ys = take n xs in
> >                  if n == length ys
> >                    then ys : (makeGroups n $ tail xs)
> >                    else []

The above can be shortened to:

> makeGroupsOf n = map (take n) . tails

>From here on you should be able to compute products of whatever is required.
Good luck and have fun!

Regards,
-- 
Krzysztof Kościuszkiewicz
Skype: dr.vee,  Gadu: 111851,  Jabber: kokr at jabberpl.org
Phone IRL: +353851383329,  Phone PL: +48783303040
"Simplicity is the ultimate sophistication" -- Leonardo da Vinci