💾 Archived View for desu-cartes.org › ~sage › 2020-aoc-day1.gmi captured on 2022-06-03 at 22:47:35. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
So the first problem we have is the following, ignoring the parsing step, given a list of positive integers, find the two that add to 2020, and return their product.
I "solved" it inefficiently in haskell:
day1p1 :: [Integer] -> Integer day1p1 ns = head $ [m*n | m <- ns, n <- ns, m + n == 2020]
This actually doesn't work, as it can pull the same element twice, so it can give the wrong answer if 1010 is in the list. However, it worked for my input. Also, it's O(n^2), not exactly efficient.
I wrote another solution, using tail recursion this time:
(|>) :: a -> (a -> b) -> b
(|>) a b = b a
day1p1r :: [Integer] -> Integer
day1p1r [] = 0
day1p1r (n : ms) =
case added of
[] -> day1p1r ms
[m] -> m * n
_ -> 0
where added = ms
|> map (\m -> (m, n + m))
|> filter (\(_,x) -> x == 2020)
|> map (\(x,_) -> x)
This one should be more efficient, since it checks less cases (though you never really know with haskell lol), and doesn't fall apart on the 1010 case. Originally I (ab)used the $ operator to write out that pipeline, but the pipe operator makes it much cleaner.
Of course, every AoC has two parts. The second part is to do the same thing, but with three numbers. Predictably, I ran for the list comprehension (though it is wrong), which worked for my input.
day1p2 :: [Integer] -> Integer day1p2 ns = head $ [m*n*k | m <- ns, n <- ns, k <- ns, m + n + k == 2020]
Similarly, I went to fix it with a recursive version. First I abstracted out the pattern from the last time, as expressing nested loops with tail recursion is hell. Then just loop over again, like part 1.
pairSum :: Integer -> [Integer] -> Integer
pairSum _ [] = 0
pairSum total (n : ms) =
case added of
[] -> pairSum total ms
[m] -> m * n
_ -> 0
where added = ms
|> map (\m -> (m, n + m))
|> filter (\(_,x) -> x == total)
|> map (\(x,_) -> x)
day1p2r :: [Integer] -> Integer
day1p2r [] = 0
day1p2r (n : ms) =
if pairSum (2020 - n) ms /= 0
then n * pairSum (2020 - n) ms
else day1p2r ms
Finally, we bring in the burritos, I mean monads, to actually read and parse (did I say we could ignore the parsing step? haha no) the file and calculate the result. (Thanks prez!)
input :: FilePath -> IO [Integer]
input f = map read <{body}gt; lines <{body}gt; readFile f
main :: IO (Integer, Integer)
main = do
nums <- input "./input-day1"
return (day1p1r nums, day1p2r nums)
I'm not too satisfied with my solutions, since they are kind of ugly. (0 as a sentinel value, really? Especially in a language with Algebraic Data Types. Those functions should really return a Maybe type. Also, I'm using partial functions like head, which kind of sucks.)
I also have solutions in Common Lisp which are more efficient (using a hashtable to cache the sums to lower complexity). I may write them up later. There was also a method involving FFTs, which was supposed to be the fastest, but I have not figured that out yet.