Dec 1, 2019

Since I'm releasing a book on practical lenses and optics later this month I thought it would be fun to do a few of this year's Advent of Code puzzles using optics as much as possible!

I'm not sure how many I'll do, or even if any problems will yield interesting solutions with optics, but there's no harm trying! The goal is to use optics for as much of the solution as possible, even if it's awkward, silly, or just plain overkill. Maybe we'll both learn something along the way. Let's have some fun!

You can find the first puzzle here.

## Part One

So the gist of this one is that we have a series of input numbers (mass of ship modules) which each need to pass through a pipeline of mathematic operations (fuel calculations) before being summed together to get our puzzle solution (total fuel required).

This immediately makes me think of a reducing operation, we want to fold many inputs down into a single solution. We also need to map each input through the pipeline of transformations before adding them. Were I to use "normal" Haskell I could just `foldMap` to do both the fold and map at once! With optics however, the ideas of folds already encompass both the folding and mapping pieces. The optic we use provides the selection of elements as well as the mapping, and the action we run on it provides the reductions step (the fold).

Let's see if we can build up a fold in pieces to do what we need.

Assuming we have a `String` representing our problem input we need to break it into tokens to get each number from the file. Writing a parser is overkill for such a simple task; we can just use the `worded` fold which splits a String on whitespace and folds over each word individually!

Here's what we've got so far:

``````import Control.Lens

solve :: IO ()
solve =  do
print \$ input ^.. worded``````

Running this yields something like this:

``````>>> solve
["76542","97993","79222"...] -- You get the idea``````

Now we need to parse the strings into a numeric type like `Double`. There's a handy prism in `lens` called `_Show` which will use `Read` instances to parse strings, simply skipping elements which fail to parse. Our input is valid, so we don't need to worry about errors, meaning we can use this prism confidently.

Here's the type of `_Show` by the way:

``_Show :: (Read a, Show a) => Prism' String a``

I'll add a type-application to tell it what the output type should be so it knows what type to parse into (i.e. which `Read` instance to use for the parsing):

``````{-# LANGUAGE TypeApplications #-}

solve :: IO ()
solve =  do
print \$ input ^.. worded
. _Show @Double

>>> solve
[76542.0,97993.0,79222.0...]``````

Looks like that's working!

Next we need to pipe it through several numeric operations. I like to read my optics pipelines sequentially, so I'll use `to` to string each transformation together. If you prefer you can simply compose all the arithmetic into a single function and use only one `to` instead, but this is how I like to do it.

The steps are:

1. Divide by 3
2. Round down
3. Subtract 2

No problem:

``````solve :: IO ()
solve =  do
print \$ input ^.. worded
. _Show
. to (/ 3)
. to (floor @Double @Int)
. to (subtract 2)

>>> solve
[25512,32662,26405...]``````

I moved the type application to `floor` so it knows what its converting between, but other than that it's pretty straight forward.

Almost done! Lastly we need to sum all these adapted numbers together. We can simply change our aggregation action from `^..` (a.k.a. `toListOf`) into `sumOf` and we'll now collect results by summing!

``````solve :: IO ()
solve =  do
print \$ input & sumOf ( worded
. _Show
. to (/ 3)
. to (floor @Double @Int)
. to (subtract 2)
)

>>> solve
3154112``````

First part's all done! That's the correct answer.

As a fun side-note, we could have computed the ENTIRE thing in a fold by using `lens-action` to thread the `readFile` into IO as well. Here's that version:

``````import Control.Lens
import Control.Lens.Action ((^!), act)

solve' :: IO (Sum Int)
solve' =  "./src/Y2019/day01.txt"
. worded
. _Show
. to (/3)
. to floor @Double @Int
. to (subtract 2)
. to Sum

>>> solve'
Sum {getSum = 3154112}``````

The `^!` is an action from `lens-action` which lets us 'view' a result from a Fold which requires IO. `act` allows us to lift a monadic action into a fold. By `viewing` we implicitly fold down the output using it's Monoid (in this case `Sum`).

I think the first version is cleaner though.

On to part 2!

## Part 2

Okay, so the gist of part two is that we need to ALSO account for the fuel required to transport all the fuel we add! Rather than using calculus for this we're told to fudge the numbers and simply iterate on our calculations until we hit a negative fuel value.

So to adapt our code for this twist we should split it up a bit! First we've got a few optics for parsing the input, those are boring and don't need any iteration. Next we've got the pipeline part, we need to run this on each input number, but will also need to run it on each iteration of each input number. We'll need to somehow loop our input through this pipeline.

As it turns out, an iteration like we need to do here is technically an unfold (or anamorphism if you're feeling eccentric). In optics-land unfolds can be represented as a normal `Fold` which adds more elements when it runs. Lensy folds can focus an arbitrary (possibly infinite) number of focuses! Even better, there's already a fold in `lens` which does basically what we need!

``iterated :: (a -> a) -> Fold a a``

`iterated` takes an iteration function and, well, iterates! Let's try it out on it's own first to see how it does its thing:

``````>>> 1 ^.. taking 10 (iterated (+1))
[1,2,3,4,5,6,7,8,9,10]
>>>``````

Notice that I have to limit it with `taking 10` or it'd go on forever. So it definitely does what we expect! Notice also that it also emits its first input without any iteration; so we see the `1` appear unaffected in the output. This tripped me up at first.

Okay, so we've got all our pieces, let's try patching them together!

``````solve2 :: IO ()
solve2 =  do
print
\$ input
& toListOf ( worded
. _Show
. taking 20 (iterated calculateRequiredFuel)
)
where
calculateRequiredFuel :: Double -> Double
calculateRequiredFuel = (fromIntegral . subtract 2 . floor @Double @Int . (/ 3))

>>> solve2
[76542.0,25512.0,8502.0,2832.0,942.0,312.0,102.0,32.0,8.0,0.0,-2.0,-3.0,-3.0
...79222.0,26405.0,8799.0,2931.0...]``````

I've limited our iteration again here while we're still figuring things out, I also switched back to `toListOf` so we can see what's happening clearly. I also moved the fuel calculations into a single pure function, and added a `fromIntegral` so we can go from `Double -> Double` as is required by `iterated`.

In the output we can see the fuel numbers getting smaller on each iteration, until they eventually go negative (just like the puzzle predicted). Eventually we finish our 20 iterations and the fold moves onto the next input so we can see the numbers jump back up again as a new iteration starts.

The puzzle states we can ignore everything past the point where numbers go negative, so we can stop iterating at that point. That's pretty easy to do using the higher-order optic `takingWhile`; it accepts a predicate and another optic and will consume elements from the other optic until the predicate fails, at which point it will yield no more elements. In our case we can use it to consume from each iteration until it hits a negative number, then move on to the next iteration.

``````solve2 :: IO ()
solve2 =  do
print \$
input & toListOf
( worded
. _Show
. takingWhile (>0) (iterated calculateRequiredFuel)
)

>>> solve2
[76542.0,25512.0,8502.0,2832.0,942.0,312.0,102.0,32.0,8.0
,97993.0,32662.0,10885.0,3626.0,1206.0,400.0,131.0,41.0,11.0...]``````

We don't need the `taking 20` limiter anymore since now we stop when we hit `0` or below. In this case we technically filter out an actual `0`; but since `0` has no effect on a `sum` it's totally fine.

Okay, we're really close! On my first try I summed up all these numbers and got the wrong answer! As I drew attention to earlier, when we use `iterated` it passes through the original value as well. We don't want the weight of our module in our final sum, so we need to remove the first element from each set of iterations. I'll use ANOTHER higher-order optic to wrap our iteration optic, dropping the first output from each iteration:

``````solve2 :: IO ()
solve2 =  do
print \$
input & sumOf
( worded
. _Show
. takingWhile (>0) (dropping 1 (iterated calculateRequiredFuel))
)

>>> solve2
4728317.0``````

It depends on how you like to read your optics, but I think the multiple nested higher-order-optics is a bit messy, we can re-arrange it to use fewer brackets like this; but it really depends on which you find more readable:

``````solve2 :: IO ()
solve2 =  do
print
\$ input
& sumOf (worded
. _Show
. (takingWhile (> 0) . dropping 1 . iterated) calculateRequiredFuel
)``````

That'll do it!

Once you get comfortable with how folds nest inside paths of optics, and how to use higher-order folds (spoilers: there's a whole chapter on this in my book launching later this month: Optics By Example), then we can solve this problem very naturally with optics! I hope some of the other problems work out just as well.

See you again soon!

Hopefully you learned something ðŸ¤ž! Did you know I'm launching a book about lenses and optics this month? It takes you all the way from an beginner to wizard in all categories of optics! Sign up here or follow the book on twitter to hear when it's released.