AdventOfCode Day 1 : find X element matching a criteria in haskell

Question

This problem is from https://adventofcode.com/2020/ day 1.

I need to find the N entries of inputs that sum to 2020 and then multiply those N numbers together.

inputs = [1721, 979, 366, 299, 675, 1456]

I have 2 cases N = 2 and N = 3

I have done this with list comprehension

N = 2 :

main = print $ head [ i * j |
                      i <- inputs ,
                      j <- inputs ,
                      i+j == 2020]
                            

N = 3 :

main = print $ head [ i * j * k  |
                      i <- inputs ,
                      j <- inputs ,
                      k <- inputs ,
                      i+j+k == 2020]

But it scales badly, if y need N = 100 that's a lot of <-.

So I have done this :

solution n =  foldl1 (*) $ head [ x | x <- sequence $ replicate n inputs , (foldl1 (+) x == 2020 )]

main = print $ solution 3

I wonder if there is a more idiomatic way to do this and if there is a way of using list comprehension with N variables ?

Note : I know that with these solutions, the same entries can be used multiple times, and I am ok with it.

Answer 1

While the code certainly works, I wouldn't necessarily call it idiomatic. Haskell's safety and robustness stems from its types, and the type signatures are completely missing. Sure, it works fine. However, all integers are Integer by default, a type that has some nice properties (arbitrary large numbers) and some drawbacks (sub par performance compared to Int).

However, to introduce type signatures, we need a function. The third variant introduces a fine candidate: solution.

solution :: Int -> Int
solution n =  foldl1 (*) $ head [ x | x <- sequence $ replicate n inputs , (foldl1 (+) x == 2020 )]

Now that we have a safe foundation and get type errors if we do anything unexpected, let's have a look at the code and the used functions. foldl1 (*) is product and foldl1 (+) is sum, although both alternatives act slightly different on an empty list.. Yes, both functions will use foldr internally, but that is fine. If we are going for strictness, then we want to use foldl1' instead, but that's not necessary with numbers from my experience. Also, sequence . replicate is replicateM (from Control.Monad), and the parentheses around fold1 (+) x == 2020 aren't necessary. Note that hlint will report those changes, too.

So without changing the original algorithm, we end up at

import Control.Monad (replicateM)

inputs :: [Int]
inputs = [ ... ]

solution :: Int -> Int
solution n =  product $ head [ xs | xs <- replicateM n inputs
                                  , sum xs == 2020]

main :: IO ()
main = print $ solution 3

Note that we changed x to xs, as we're not dealing with a single element, but instead with lists. This new variant ticks all the boxes:

• it has explicit types on its top-level structures ✔
• it uses named variants of folds (product for foldl (*) 1, sum for foldl (+) 0) ✔
• it uses typical naming (xs for lists) ✔
• it splits functionality into reasonable parts (main and solution) ✔

However, there's nothing wrong with your old variant, as it was semantically equivalent (except for empty intermediate lists). If I was to solve AoC, I would have used a similar script-style Haskell format, except for solution's type; I'd use [Int] -> Int or even [Int] -> Maybe Int instead to interact with map read . lines <$> readFile "inputs". But that's personal preference.

And last but not least: Your choice to use the list monad to easily check all \$n\$ combinations was really nice!

Answer 2

The library gives you all idioms you need

import Data.List
main=print.product.head.
     filter((2020==).sum).subsequences$
     [1721,979,366,299,675,1456]

Try it online!