Ok, so in part one we got the first part of the first day of last year’s Advent of Code puzzle working in Haskell. This post will be an exploration of the second part.
Each day of the Advent of Code has a puzzle with two parts; usually the second part will be a twist on the first part; sometimes, it’s simply a scale issue, where the first part solution was naive, and you can leave your solution running over night, or choose a more efficient solution for both parts. But sometimes, it blows everything up and you need to rethink your entire approach.
The second part of last year’s day one puzzle is defined as so:
During the second Go / No Go poll, the Elf in charge of the Rocket Equation Double-Checker stops the launch sequence. Apparently, you forgot to include additional fuel for the fuel you just added.
Fuel itself requires fuel just like a module - take its mass, divide by three, round down, and subtract 2. However, that fuel also requires fuel, and that fuel requires fuel, and so on. Any mass that would require negative fuel should instead be treated as if it requires zero fuel; the remaining mass, if any, is instead handled by wishing really hard, which has no mass and is outside the scope of this calculation.
So, for each module mass, calculate its fuel and add it to the total. Then, treat the fuel amount you just calculated as the input mass and repeat the process, continuing until a fuel requirement is zero or negative.
Ah, OK, this looks pretty reasonable; we just need to modify our
fuel function to take this into account. We keep the same inputs, so what we’ll do is write a new, pure
newFuel function, and then plug that into where our
fuel function is run. This is one of the most common early Advent of Code strategies; it’s a simple refinement of what we had before.
To recap, at the end of the last post, we had a pure function from
fuel as such:
fuel :: Int -> Int fuel mass = div mass 3 - 2
The expanded definition in Part 2 maintains the same fundamental structure, as a function from
fuel, so the type – how we describe this structure – will be the same:
newFuel :: Int -> Int
DIGRESSION: NAMING THINGS
newFuel is a terrible name. Why? Because it doesn’t actually convey any more information than that there exists, somewhere, an earlier function, called
fuel. This is a common problem writing software – naming is surprisingly difficult! Writing software is, in my experience, an exercise in manipulating state and abstraction, and that’s hard. Poor names make that harder – at best they
From the definition, it’s clearly a recursive problem; we’re feeding the results of
fuel back into
fuel. So how should we do that? Keeping in mind that we’re writing a function from
fuel. But, read the problem again: we compute fuel, and then to that number, add the fuel necessary for that fuel, and so on down until we get to a zero or negative number. This is the “base case” for recursion. But there’s an issue here: we get to zero, and we need to return some other number, representing the running total.
How do we manage this, given the type signature
Int -> Int? Well, we could define a helper function that maintains this running total. In a language like Python, we’d write a multiple argument function as:
def helper (mass, running_total): pass
What does that look like in Haskell? It looks like this:
helper :: Int -> Int -> Int helper mass runningTotal = ... -- something goes here
Let’s fill in the “something”. Rereading the definition, we can start with the base case:
helper mass runningTotal | fuel mass <= 0 = runningTotal
| character introduces something called a “guard”. The “guard” is an expression that gets evaluated; if
True, then the function body is called; if
False, we “fall through” to the next definition. Knowing that, we can see that if the computation of the fuel necessary to launch the given mass is 0 or lower, we return the running total we’ve been keeping.
Let’s see what happens when we run this!
λ> helper 0 1 1 λ> helper 123 3 *** Exception: /Users/jfb/Projects/AOC/2020/src/Day00.hs:26:1-56: Non-exhaustive patterns in function helper
Whoops! A moment’s reflection makes this pretty clear. We’ve not completely defined
helper – we can only handle a situation where the guard succeeds; in other words, where we’ve gotten to the base case. So, let’s put the second part in:
helper :: Int -> Int -> Int helper mass runningTotal | fuel mass <= 0 = runningTotal helper mass runningTotal | otherwise = helper (fuel mass) (runningTotal + fuel mass)
otherwise is seemingly a synonym for
True; we could leave it out, and just have the one equation with a guard, and one without. In an example this simple, it’s fine, but I prefer to use
otherwise in cases where there might be more than just one guard.
So, we have a
newFuel that is of type
Int -> Int, and a
helper of type
Int -> Int -> Int. How do we call
helper with some given mass? Well, we start out with the same
newFuel consumes, and our running total starts … at 0! So:
newFuel :: Int -> Int newFuel mass = helper mass 0
But that’s messy –