# Advent of Code 2020, preparing, part 02

Posted on

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
``````

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

``````λ> 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)
``````

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 –