Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25
It begins...
The internet doesn't have enough blogs about Advent of Code solutions, so here's one more. I've been dabbling in functional programming for a while now, and I thought attempting AoC in Haskell would be a good way to develop some of these fledgeling skills. On that note, a quick disclaimer: the code I present here should not necessarily be taken as representative of good Haskell practices or even good Haskell style.
My approach is heavily inspired by Michael Gilliland's video series on Youtube. I use light vim editing to massage the input into a format that can be assigned directly to a Haskell entity, and then write a program that spits out the answer. (Even though AoC typically gives pretty clean inputs, I wasn't too interested in dealing with input parsing.) Anyone interested in seeing the input files as well can view my solutions with the inputs at this Github repository. I also freely exploit guarantees provided by the problem on input, and therefore typically end up quite light on the error handling in my solutions.
All right, enough preamble... let's look at Day 1.
Part 1
Day 1 keeps things simple, and essentially boils down to finding two numbers in a list that add up to the target number 2020. We take the naive approach of enumerating all possible pairs and then searching for the pair with the desired sum.
import D1input
-- input :: [Int]
-- targetSum :: Int
cartesianProduct :: [Int] -> [Int] -> [(Int, Int)]
cartesianProduct xs ys = [(x, y) | x <- xs, y <- ys]
findPair :: [Int] -> Int -> (Int, Int)
findPair entries target =
let pairs = cartesianProduct entries entries
in head $ filter (\(x,y) -> x + y == target) pairs
solve :: Int
solve =
let (x,y) = findPair input targetSum
in x * y
main :: IO ()
main = print solve
We first define a cartesianProduct function that takes two lists of integers and returns a list of pairs by taking one integer from each list. This will allow us to generate a list of every candidate pair of entries by passing the list of entries twice to cartesianProduct. Those of you familiar with Python will note the syntax similarity to list comprehensions.
The main algorithm is captured in the findPair function, which takes the list of entries and the target, and then returns the pair of integers we want. This uses the cartesianProduct function we wrote earlier to generate all candidates, and then the filter function to keep only the pair that sums to the target. We also assume that exactly one such pair will be found, so we use head to extract it.
Finally, the solve function uses findPair to do the heavy lifting, and then performs the final multiplication that the problem demands.
It's also worth noting that this algorithm is not quite correct, since the cartesianProduct will also generate pairs that consist of two of the same entry. This would cause a problem if the list contains a single instance of the value 1010, resulting in the pair (1010, 1010) in the list of pairs. However, a quick search on the input shows that 1010 does not appear.
Part 2
The problem is then extended to finding three entries that add up to 2020. Some might recognize this as the well-known 3-sum problem, for which an O(n^2) solution is still possible. However, in this case, there are only about 200 entries, so we instead extend our naive search to obtain an O(n^3) algorithm, which does the job just fine.
import D1input
-- input :: [Int]
-- targetSum :: Int
cartesianProduct :: [Int] -> [Int] -> [Int] -> [(Int, Int, Int)]
cartesianProduct xs ys zs = [(x, y, z) | x <- xs, y <- ys, z <- zs]
findTriple :: [Int] -> Int -> (Int, Int, Int)
findTriple entries target =
let triples = cartesianProduct entries entries entries
in head $ filter (\(x,y,z) -> x + y + z == target) triples
solve :: Int
solve =
let (x,y,z) = findTriple input targetSum
in x * y * z
main :: IO ()
main = print solve
Jump to:
D1 | D2 | D3 | D4 | D5 | D6 | D7 | D8 | D9 | D10 | D11 | D12 | D13 | D14 | D15 | D16 | D17 | D18 | D19 | D20 | D21 | D22 | D23 | D24 | D25