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.

PART TWO

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 mass to 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 mass to 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

RECURSION 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 mass into 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

The | 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!

#+begin_example λ> 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 #+end_example

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)

Tidbits: 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. ## HELPER FUNCTIONS 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 mass as newFuel consumes, and our running total starts … at 0! So:

newFuel :: Int -> Int
newFuel mass =
  helper mass 0

But that’s messy –