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
Part 1
The theme of my solution for Day 9 is to experiment with some of the more interesting list manipulation functions in Haskell. We are given a list of integers are asked to find the first integer that cannot be expressed as the sum of 2 of the 25 integers preceding it.
import D9input
-- input :: [Integer]
import qualified Data.List as List
import qualified Data.Maybe as Maybe
import qualified Data.Set as Set
import qualified Control.Monad as Monad
winLength :: Int
winLength = 25
windows :: [Integer] -> [[Integer]]
windows xs =
let headSlice list
| length list >= (winLength + 1) =
Just ((take (winLength + 1) list), tail list)
| otherwise = Nothing
in List.unfoldr headSlice xs
allPairSums :: [Integer] -> [Integer]
allPairSums list = do
(i,x) <- zip [0..] list
(j,y) <- zip [0..] list
Monad.guard (i < j)
return (x + y)
notSum :: [Integer] -> Maybe Integer
notSum list =
let sums = Set.fromList $ allPairSums $ take winLength list
value = head $ drop winLength list
in if Set.member value sums then Nothing else Just value
solve :: Integer
solve = head $ Maybe.catMaybes $ map notSum $ windows input
main :: IO ()
main = print $ solve
The first step is to break up the list into "windows" - sublists of (25 + 1) elements for which we can check whether the last element can be written as the sum of two of the first 25. This is done by the windows function, which exploits the unfoldr function. This function takes a seed value and a function that both generates a list element from the seed and advances the seed. Armed with this, unfoldr can construct an entire list from a given seed.
In this case, our seed is the entire input list of integers. Generating an element from the seed will simply slice the first 26 elements off (so that each element of our resulting windows list is itself a list of 26 elements). Advancing the seed is accomplished by taking the tail of the current seed; this will result in the next element of the result being a 26-element window starting from the next element, and so on. This is implemented by the headSlice function in the definition of windows. The one final quirk is that this function returns not just a (seed, element) pair, but rather a Maybe (seed, element) pair. When the result is Nothing, the list generated by unfoldr will end. Therefore, we make our headslice function return Nothing when there are not enough elements in the seed to form the next slice.
Once we've sliced the input up into subproblems, we turn our attention to the problem of verifying each 26-element window. The notSum function returns Nothing if the last element can be expressed as the sum of two integers. It returns the last element itself if it cannot be expressed so.
We take a brute force approach to this subproblem. We generate all pairwise sums of the first 25 elements and create a set from it. A simple call to Set's member then gives us our answer.
Constructing all pairwise sums was an ask of Day 1, but we need to be a little more careful here, since we want to make sure that we are only taking the sum of two distinct integers. This seemed like a good opportunity to play around in the list monad. Again, I'll only summarize that computing in the list monad can be thought of as each statement defining elements of a list. Each such list created this way is gathered into a cartesian product, and each element of the final list is computed by the return statement. This is probably a very unsatisfying explanation, but those looking for more information can check out this section of Learn You a Haskell. Let's take a closer look at allPairSums:
allPairSums :: [Integer] -> [Integer]
allPairSums list = do
(i,x) <- zip [0..] list
(j,y) <- zip [0..] list
Monad.guard (i < j)
return (x + y)
The first two assignments (of i,x and j,y) effectively accomplish looping over every pair of values, while tracking the indices as well. The Monad.guard call, when used in a do clause in the list monad, results in an empty list when the condition is false, or a singleton list if the condition is true. As a result, if i >= j, we in some sense have a for loop with zero steps, which suppresses the return statement, and the corresponding value will not be in the final list. If i < j, we have a for loop with one step. This gives us our list of sums, comprised only of sums from distinct integers.
For those more familiar with imperative paradigms, it may help to compare the above to the Python equivalent:
def allPairSums(list):
result = []
for i,x in enumerate(list):
for j,y in enumerate(list):
if i < j:
result.append(x + y)
return result
Part 2
Part 2 asks us to find a contiguous range of integers that add up to our answer from part 1. Conceptually, this is not a difficult problem, but the input list is long enough that we would like a solution that is more efficient than the brute force approach. Fortunately, this is a well-known problem that can be solve more quickly if we compute partial sums.
import D9input
-- input :: [Integer]
import qualified Data.List as List
import qualified Control.Monad as Monad
-- answer from part 1
invalid :: Integer
invalid = 133015568
partialSum :: [Integer] -> [Integer]
partialSum = scanl (+) 0
summingRangeIndices :: Integer -> [Integer] -> [(Int, Int)]
summingRangeIndices t list = do
(i, ps1) <- zip [0..] (partialSum list)
(j, ps2) <- zip [0..] (partialSum list)
Monad.guard (i < j)
Monad.guard (ps2 - ps1 == t)
return (i,j)
summingRange :: Integer -> [Integer] -> [Integer]
summingRange t list =
let (i,j) = head $ summingRangeIndices t list
in List.take (j - i) $ drop i list
solve :: Integer
solve =
let range = summingRange invalid input
in (minimum range) + (maximum range)
main :: IO ()
main = print $ solve
Partial sums is simply a slightly fancy name for "sum of the first n elements." The first thing we want to do is compute the partial sums for the input list (e.g., [1, 2, 3, 4] becomes [1, 1+2, 1+2+3, 1+2+3+4]). Haskell happens to have a function for just this purpose, called scanl, although it is generalized to allow the user to specify the binary operation. Note the similarity to folds - scanl is very similar to foldl, except that it keeps intermediate results as well. Implementing partialSum is therefore very easy. The binary operation we want is addition, and our initial value is just 0.
Why do we want to perform this computation? Having the partial sums enables us to compute the sum of a range of integers in O(1) time. For example, let's say we wanted to find the sum of elements 3, 4, 5, and 6. Instead of adding all 4 numbers together, we could instead (P6 - P2), where P6 is the sum of elements 0 to 6, and P2 is the sum of elements 0 to 2.
The function doing the heavy lifting here is summingRangeIndices. This takes the target sum and the list of integers, and returns the indices delimiting the range that adds up to the target sum. Even though we exactly only one such range to exist, our function actually returns a list of index pairs. This has the added advantage of enabling us to write our function inside the list monad. The algorithm itself is similar to part 1: for each pair of partial sums (each of which corresponds to a range of integers in the sequence), check whether their difference is our target, and, if so, add it to our list of index pairs. Again, here's what this might look like in Python:
def summingRangeIndices(t, list):
result = []
for i,ps1 in enumerate(partialSum(list)):
for j,ps2 in enumerate(partialSum(list)):
if i < j:
if ps1 + ps2 == t:
result.append(x + y)
return result
The rest of the problem is easy. Once we have the range, extract it, find the minimum and maximum, and add them together for our answer.
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