Project Euler problem 11, finding adjacent numbers with the greatest sum

Question

The full description of the problem to solve can be found here. The code I have written works fine but seems extremely verbose for what it's doing, I'm not sure if list comprehensions are meant to be used in the way that I have (maybe some kind of other construct would be more suitable?). Would be great for there to be a way to make the numberPairs function to be more DRY.

Also get the sense that I don't use function composition enough . and instead use $ for most nested function calls. Is this bad practice? How could I rewrite some of the functions in this using composition?

I am fairly new to Haskell so am unaware of any typical coding practices.

gridOfNumbers evaluates to a string containing the grid numbers from the problem with each number in a row separated by spaces and each row separated by newlines. Didn't seem worth including here (although I may be mistaken).

-- | In the `gridOfNumbers` find the 4 adjacent numbers in the given
-- | direction that have the greatest sum.
problem_11 :: Direction -> Int
problem_11 dir = 
 maximum $ map (\(x1,x2,x3,x4) -> product $ x1:x2:x3:x4:[]) $ numberPairs dir
data Direction = UpDown | SideWays | LeftStartDiagonal | RightStartDiagonal
numberPairs :: Direction -> [(Int,Int,Int,Int)]
numberPairs UpDown = 
 [(x1,x2,x3,x4) | 
 currentRow <- [0..16],
 currentCol <- [0..19],
 let x1 = (listifyGrid !! currentRow) !! currentCol,
 let x2 = (listifyGrid !! (currentRow + 1)) !! currentCol,
 let x3 = (listifyGrid !! (currentRow + 2)) !! currentCol,
 let x4 = (listifyGrid !! (currentRow + 3)) !! currentCol] 
numberPairs SideWays =
 [(x1,x2,x3,x4) |
 currentRow <- [0..19],
 currentCol <- [0..16],
 let x1 = (listifyGrid !! currentRow) !! currentCol,
 let x2 = (listifyGrid !! currentRow) !! (currentCol + 1),
 let x3 = (listifyGrid !! currentRow) !! (currentCol + 2),
 let x4 = (listifyGrid !! currentRow) !! (currentCol + 3)]
numberPairs LeftStartDiagonal =
 [(x1,x2,x3,x4) |
 currentRow <- [0..16],
 currentCol <- [0..16],
 let x1 = (listifyGrid !! currentRow) !! currentCol,
 let x2 = (listifyGrid !! (currentRow + 1)) !! (currentCol + 1),
 let x3 = (listifyGrid !! (currentRow + 2)) !! (currentCol + 2),
 let x4 = (listifyGrid !! (currentRow + 3)) !! (currentCol + 3)]
numberPairs RightStartDiagonal =
 [(x1,x2,x3,x4) |
 currentRow <- [0..16],
 currentCol <- [3..19],
 let x1 = (listifyGrid !! currentRow) !! currentCol,
 let x2 = (listifyGrid !! (currentRow + 1)) !! (currentCol - 1),
 let x3 = (listifyGrid !! (currentRow + 2)) !! (currentCol - 2),
 let x4 = (listifyGrid !! (currentRow + 3)) !! (currentCol - 3)]
listifyGrid :: [[Int]]
listifyGrid = map (map read) doubleListOfStrings 
 where doubleListOfStrings = map (S.split " ") $ lines gridOfNumbers 

• Landei: product $ x1:x2:x3:x4:[] could be product [x1,x2,x3,x4]
• Josh Taylor: Yes that's a better way of defining the list in-line. Cheers Landei!

Answer 1

The code I have written works fine but seems extremely verbose for what it's doing ... Would be great for there to be a way to make the numberPairs function to be more DRY.

I agree that there's a fair bit of repetition happening. This makes things very explicit, but at the cost of more boilerplate, as you said.

I suggest that the movement patterns for each direction be separated from the actual functionality of extracting a "line" of adjacent numbers from the board. That way, it's easier to see the differences between each direction:

quads :: Direction -> [[Int]]
quads UpDown
 = getLines 4 [0..16] [0..19] succ id
quads SideWays
 = getLines 4 [0..19] [0..16] id succ
quads LeftStartDiagonal
 = getLines 4 [0..16] [0..16] succ succ
quads RightStartDiagonal
 = getLines 4 [0..16] [3..19] succ pred

I've renamed numberPairs to quads because "pair" usually refers to a 2-tuple. succ and pred are just equivalent to (+ 1) and (- 1).

Now you can define getLines more generally (albeit with an uglier signature), in terms of iterating the row and column position with the supplied rowFn and colFn:

getLines :: Int -> [Int] -> [Int] -> (Int -> Int) -> (Int -> Int) -> [[Int]]
getLines n rows cols rowFn colFn =
 [line |
 row <- rows,
 col <- cols,
 let coordPairs = zip (iterate rowFn row) (iterate colFn col),
 let line = take n $ map gridGet coordPairs]
gridGet :: (Int, Int) -> Int
gridGet (row, col) = listifyGrid !! row !! col

This is just rearranging your code, except that I've used [Int] instead of (Int,Int,Int,Int) as the type of each number line. I'm not an experienced Haskeller, but I think that, here, the list is considerably easier to deal with than the tuple, at the expense of giving up an explicit length guarantee.

Using a list also makes it easy to adapt to other lengths than 4, since it's just a take n. The tuple code, at least structured as you have it right now, would grow linearly.

---

Also get the sense that I don't use function composition enough . and instead use $ for most nested function calls. Is this bad practice? How could I rewrite some of the functions in this using composition?

Again, keeping in mind that I haven't done a whole lot of Haskell: I don't see anywhere in your code where $ looks out of place.

One place where composition is nice, though, is with map and nested lists. This:

listifyGrid :: [[Int]]
listifyGrid = map (map read) doubleListOfStrings 
 where doubleListOfStrings = map (S.split " ") $ lines gridOfNumbers

could use composition if you want, as well as the words function:

listifyGrid = (map . map) read $ map words $ lines gridOfNumbers

(map . map) is so elegant that the equivalent in Python, for example, just seems obtuse. Oh, Haskell, you charmer.

Anyway, the main problem_11 function:

problem_11 :: Direction -> Int
problem_11 dir = 
 maximum $ map (\(x1,x2,x3,x4) -> product $ x1:x2:x3:x4:[]) $ numberPairs dir

can also be defined as a pointfree composition, if that's your style, especially now that we can use map directly without unwrapping the tuple:

problem_11 = maximum . (map product) . quads