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
More sequences of integers! Day 10 starts off with a fair simple warm-up, in which we need to count the jumps in the sorted sequence.
import D10input
-- input :: [Int]
import Data.List
countIf :: (a -> Bool) -> [a] -> Int
countIf f xs = length $ filter f xs
diffHist :: [Int] -> (Int, Int, Int)
diffHist list =
let sorted = sort list
diffs = map (\(x,y) -> y - x) $ zip sorted (tail sorted)
ones = countIf (==1) diffs
twos = countIf (==2) diffs
threes = countIf (==3) diffs
in (ones, twos, threes)
solve :: Int
solve =
let (ones, twos, threes) = diffHist (0:input)
in ones * (threes + 1)
main :: IO ()
main = print $ solve
Interestingly enough, this is the first time we've been required to sort a list. Haskell, like many other languages, has built-in library support for sorting a sequence, so this an easy step.
Then, we need to get the jumps at each step; i.e., the difference between every pair of adjacent elements. In Haskell, the idiomatic way to do this is to zip the list with its own tail (effectively creating a list of adjacent pairs), and then mapping a difference operation onto it. Once we have that, we can simply count the number of each jump with the help of a countIf function (which we also saw back in Day 2
One quick note on the solve function. The problem statement says the input gives all of the elements except for an implicit 0 at the beginning and an implicit (max + 3) at the end. The 0 is manually added before passing it to our main algorithm. The (max + 3) is not added, but instead if handled by adding an additional three-count before outputting the final answer.
Part 2
Part 2 was quite a bit harder! It asks us to count the number of possible sequences that could link 0 to the (max + 3) step, under the constraint that each jump must be no greater than 3. This is actually a very common flavor of a dynamic programming problem. Our strategy will be to construct the number of ways to reach a target N assuming that we already know the number of ways to reach N-1, N-2, N-3, etc.
Here is my first attempt, with values representing the set of integers, end being the target end of the sequence, and (ways values end) returning the number of ways to build a sequence up to end using elements of values:
ways :: Set.Set Int -> Int -> Int
ways values end
| end == 0 = 1
| otherwise =
let a1 = if Set.member (end - 1) values
then ways values (end - 1)
else 0
a2 = if Set.member (end - 2) values
then ways values (end - 2)
else 0
a3 = if Set.member (end - 3) values
then ways values (end - 3)
else 0
in a1 + a2 + a3
This is correct for the smaller sample inputs (and likely correct for the full input), but it takes way too long. I am including it in this post anyways, though, because I think it nicely captures the recursion. If we are asking for a sequence ending in 0, there is exactly 1 way to do so (a sequence consisting of only 0). This is our base case. Otherwise, we want to count the number of ways to reach (end-1), (end-2), and (end-3). If the value is in our set of values, a recursive call provides us the contribution to the final result. Of course, the value is not in our set of values, there is no way to make a sequence that ends in that value, so there is 0 contribution.
Note that there is no memoization being done here. When we compute (ways value 4), we need to compute (ways values 3), (ways values 2), and (ways values 1). When we compute (ways values 5), we need to compute (ways values 4), (ways values 3), and (ways values 2). There is a lot of wasted computation here, since (ways values 3), for example, is not going to change the second time we try to compute it. It would be much more efficient if we could remember what the result is for (ways values 3), etc., and simply use it instead of recomputing. This is the core principle behind dynamic programming. I was naively hoping that Haskell would memoize for me, but, judging from the runtime, it most certainly does not in this case.
We know the algorithm is correct, but we need to make sure we do not recompute calls to which we already know the result. This is how I rearranged the code to accomplish that:
import D10input
-- input :: [Int]
import qualified Data.Vector as Vector
import qualified Data.Set as Set
countWays :: Set.Set Int -> Int -> Int
countWays s n =
let countAux i
| i == 0 = 1
| Set.member i s =
let w1 = memo Vector.! (i - 1)
w2 = if i > 1 then memo Vector.! (i - 2) else 0
w3 = if i > 2 then memo Vector.! (i - 3) else 0
in w1 + w2 + w3
| otherwise = 0
memo = Vector.generate (n+1) countAux
in memo Vector.! n
solve :: Int
solve =
let end = (maximum input) + 3
values = Set.fromList (0:end:input)
in countWays values end
main :: IO ()
main = print $ solve
countWays has the same signature. It takes the set of values s, the target end value n, and returns the number of ways to construct a sequence that ends in n. The trick here is to return the final result out of a Data.Vector called memo. This is constructed via a call to generate, which is fed an auxiliary countAux function that implements the same recursion outlined above: if the value is in the set, compute it from the solution to the three subproblems below it; otherwise, return 0. Note that the solutions to the subproblems are now obtained by indexing into the memo Vector, rather than directly via recursive call. Because we only ask for values smaller than i, we are guranteed that generate will have already computed the result for it. This results in a much faster algorithm, which solves my puzzle input almost instantly.
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