Multiplying numbers on horizontal, vertial, and diagonal lines

Question

I'm currently working on a project Euler problem (www.projecteuler.net) for fun but have hit a stumbling block. One of the problem provides a 20x20 grid of numbers and asks for the greatest product of 4 numbers on a straight line. This line can be either horizontal, vertical, or diagonal.

Using a procedural language I'd have no problem solving this, but part of my motivation for doing these problems in the first place is to gain more experience and learn more Haskell.
As of right now I'm reading in the grid and converting it to a list of list of ints, eg -- [[Int]]. This makes the horizontal multiplication trivial, and by transposing this grid the vertical also becomes trivial.

The diagonal is what is giving me trouble. I've thought of a few ways where I could use explicit array slicing or indexing, to get a solution, but it seems overly complicated and hackey. I believe there is probably an elegant, functional solution here, and I'd love to hear what others can come up with.

Answer 1

You can use the !! function to retrieve elements in a list by index. That with a fixed step either incrementing or decrementing the index gets you a diagonal.

Answer 2

Lists are the wrong data structure for this problem, as they don't provide random indexing in constant time -- they bias towards linear traversals. So your diagonals will always be more annoying/slower with lists.

How about using arrays? E.g. parallel vectors or regular vectors.

Answer 3

Well, for this particular problem, a single linear list or array is actually the easiest structure! The key is to think about these runs as skipping through the list with a given stride. If the grid is w × h in size, then

• a horizontal run has a stride of 1
• a vertical run has a stride of w
• one diagonal run has a stride of w-1
• one diagonal run has a stride of w+1

Now, for each of the four kinds of runs, you just need to compute the possible starting points. Something like this:

allRuns :: Int -> Int -> Int -> [a] -> [[a]]
allRuns n w h es = horiz ++ vert ++ acute ++ grave
    where horiz = runs [0..w-n]   [0..h-1] 1
          vert  = runs [0..w-1]   [0..h-n] w
          acute = runs [n-1..w-1] [0..h-n] (w-1)
          grave = runs [0..w-n]   [0..h-n] (w+1)

          runs xs ys s = [run (x+y*w) s | x <- xs, y <- ys]
          run i s = map (es!!) [i,i+s..i+(n-1)*s]

Of course, in an efficient implementation, you'd replace the [a] with something like Data.Array Int a and es!! with es!