Reflections 2021

2016 / 2018 / 2019 / 2020 / 2021 / 2022 / 2023 / 2024

Day 1
Day 2
Day 3 (benchmark only)
Day 4 (benchmark only)
Day 5 (benchmark only)
Day 6 (benchmark only)
Day 7 (benchmark only)
Day 8 (benchmark only)
Day 9 (benchmark only)
Day 10 (benchmark only)
Day 11 (benchmark only)
Day 12 (benchmark only)
Day 13 (benchmark only)
Day 14 (benchmark only)
Day 15 (benchmark only)
Day 16 (benchmark only)
Day 17 (benchmark only)

Day 1

Top / Prompt / Code / Standalone

As a simple data processing thing, this one shines pretty well in Haskell :)

Assuming we have a list, we can get the consecutive items with a combination of zipWith and drop. Then we can just count how many pairs of items match the predicate (strictly increasing):

countIncreasesPart1 :: [Int] -> Int
countIncreasesPart1 xs = length (filter (== True) (zipWith (<) xs (drop 1 xs)))

Yes, filter (== True) is the same as filter id, but it's a bit easier to read this way :)

Remember that if xs is [2,4,6,5], then drop 1 xs is [4,6,5], and so zip xs (drop 1 xs) is [(2,4), (4,6), (6,5)] So zipWith (<) xs (drop 1 xs) is [True, True, False]. So counting all of the True items yields the right answer!

Part 2 is very similar, but we need to check if items three positions apart are increasing. That's because for each window, the sum of the window is increasing if the new item gained is bigger than the item that was just lost. So for an example like [3,5,6,4,7,8], as we move from [3,5,6] to [5,6,4], we only need to check if 4 is greater than 3. So we only need to compare 4 and 3, 7 and 5, and then 8 and 6.

countIncreasesPart2 :: [Int] -> Int
countIncreasesPart2 xs = length (filter (== True) (zipWith (<) xs (drop 3 xs)))

We just need to replace drop 1 xs with drop 3 xs to compare three-away items.

Anyway the parsing in Haskell is straightforward, at least -- we can just do map read . lines, to split our input into lines and then map read :: String -> Int over each line. Ta dah! Fun start to the year :)

Day 1 Benchmarks

>> Day 01a
benchmarking...
time                 21.56 μs   (21.53 μs .. 21.59 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 21.55 μs   (21.53 μs .. 21.58 μs)
std dev              79.03 ns   (62.41 ns .. 111.6 ns)

* parsing and formatting times excluded

>> Day 01b
benchmarking...
time                 19.43 μs   (19.39 μs .. 19.47 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 19.36 μs   (19.31 μs .. 19.41 μs)
std dev              146.8 ns   (116.7 ns .. 199.0 ns)

* parsing and formatting times excluded

Day 2

Top / Prompt / Code / Standalone

Day 2 has a satisfying "unified" solution for both parts that can be derived from group theory! The general group (or monoid) design pattern that I've gone over in many Advent of Code blog posts is that we can think of our "final action" as simply a "squishing" of individual smaller actions. The revelation is that our individual smaller actions are "combinable" to yield something of the same type, so solving the puzzle is generating all of the smaller actions repeatedly combining them to yield the final action.

In both of these parts, we can think of squishing a bunch of small actions (forward, up, down) into a mega-action, which represents the final trip as one big step. So here is our general solver:

-- | A type for x-y coordinates/2d vectors
data Point = P { pX :: Int, pY :: Int }

day02
    :: Monoid r
    => (Int -> r)            -- ^ construct a forward action
    -> (Int -> r)            -- ^ construct an up/down action
    -> (r -> Point -> Point) -- ^ how to apply an action to a point
    -> String
    -> Point                 -- ^ the final point
day02 mkForward mkUpDown applyAct =
      (`applyAct` P 0 0)             -- get the answer by applying from 0,0
    . foldMap (parseAsDir . words)   -- convert each line into the action and merge
    . lines                          -- split up lines
  where
    parseAsDir (dir:n:_) = case dir of
        "forward" -> mkForward amnt
        "down"    -> mkUpDown amnt
        "up"      -> mkUpDown (-amnt)
      where
        amnt = read n

And there we have it! A solver for both parts 1 and 2. Now we just need to pick the Monoid :)

For part 1, the choice of monoid is simple: our final action is a translation by a vector, so it makes sense that the intermediate actions would be vectors as well -- composing actions means adding those vectors together.

data Vector = V { dX :: Int, dY :: Int }

instance Semigroup Vector where
    V dx dy <> V dx' dy' = V (dx + dx') (dy + dy')
instance Monoid Vector where
    mempty = V 0 0

day02a :: String -> Int
day02a = day02
    (\dx -> V dx 0)   -- forward is just a horizontal vector
    (\dy -> V 0 dy)   -- up/down is a vertical vector
    (\(V dx dy) (P x0 y0) -> P (x0 + dx) (y0 + dy))

Part 2 is a little trickier because we have to keep track of dx, dy and aim. So we can think of our action as manipulating a Point as well as an Aim, and combining them together.

newtype Aim = Aim Int

instance Semigroup Aim where
    Aim a <> Aim b = Aim (a + b)
instance Monoid Aim where
    mempty = Aim 0

So our "action" looks like:

data Part2Action = P2A { p2Vector :: Vector, p2Aim :: Aim }

However, it's not exactly obvious how to turn this into a monoid. How do we combine two Part2Actions to create a new one, in a way that respects the logic of part 2? Simply adding them point-wise does not do the trick, because we have to somehow also get the Aim to factor into the new y value.

Group theory to the rescue! Using the monoid-extras library, we can can say that Aim encodes a "vector transformer". Applying an aim means adding the dy value by the aim value multiplied the dx component.

instance Action Aim Vector where
    act (Aim a) = moveDownByAimFactor
      where
        moveDownByAimFactor (V dx dy) = V dx (dy + a * dx)

Because of this, we can now pair together Vector and Aim as a semi-direct product: If we pair up our monoid (Vector) with a "point transformer" (Aim), then Semi Vector Aim is a monoid that contains both (like our Part2Action above) but also provides a Monoid instance that "does the right thing" (adds vector, adds aim, and also makes sure the aim action gets applied correctly when adding vectors) thanks to group theory.

-- constructors/deconstructors that monoid-extras gives us
inject :: Vector -> Semi Vector Aim
embed  :: Aim    -> Semi Vector Aim
untag  :: Semi Vector Aim -> Vector

day02b :: String -> Int
day02b = day02
    (\dx -> inject $ V dx 0)   -- forward just contributs a vector motion
    (\a  -> embed  $ Aim a )   -- up/down just adjusts the aim
    (\sdp (P x0 y0) ->
        let V dx dy = untag sdp
        in  P (x0 + dx) (y0 + dy)
    )

And that's it, we're done, thanks to the power of group theory! We identified that our final monoid must somehow contain both components (Vector, and Aim), but did not know how the two could come together to form a mega-monoid of both. However, because we saw that Aim also gets accumulated while also acting as a "point transformer", we can describe how it transforms points (with the Action instance) and so we can use Semi (semi-direct product) to encode our action with a Monoid instance that does the right thing.

What was the point of this? Well, we were able to unify both parts 1 and 2 to be solved in the same overall method, just by picking a different monoid for each part. With only two parts, it might not seem that worth it to abstract, but maybe if there were more we could experiment with what other neat monoids we could express our solution as! But, a major advantage we reap now is that, because each action combines into other actions (associatively), we could do all of this in parallel! If our list of actions was very long, we could distribute the work over multiple cores or computers and re-combine like a map-reduce. There's just something very satisfying about having the "final action" be of the same type as our intermediate actions. With that revelation, we open the door to the entire field of monoid-based optimizations and pre-made algorithms (like Semi)

(Thanks to mniip in libera irc's #adventofcode channel for helping me express this in terms of a semi-direct product! My original attempt used a 4x4 matrix that ended up doing the same thing after some symbolic analysis.)

(Thanks too to @lysxia on twitter for pointing out a nicer way of interpreting the action in terms of how it acts on points!)

Day 2 Benchmarks

>> Day 02a
benchmarking...
time                 2.068 μs   (2.065 μs .. 2.071 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 2.085 μs   (2.075 μs .. 2.108 μs)
std dev              50.18 ns   (32.67 ns .. 74.33 ns)
variance introduced by outliers: 29% (moderately inflated)

* parsing and formatting times excluded

>> Day 02b
benchmarking...
time                 959.8 μs   (957.4 μs .. 962.7 μs)
                     1.000 R²   (1.000 R² .. 1.000 R²)
mean                 954.7 μs   (952.9 μs .. 957.2 μs)
std dev              7.530 μs   (6.116 μs .. 9.523 μs)

Reflections 2021

Table of Contents

Day 1

Day 1 Benchmarks

Day 2

Day 2 Benchmarks

Day 3

Day 3 Benchmarks

Day 4

Day 4 Benchmarks

Day 5

Day 5 Benchmarks

Day 6

Day 6 Benchmarks

Day 7

Day 7 Benchmarks

Day 8

Day 8 Benchmarks

Day 9

Day 9 Benchmarks

Day 10

Day 10 Benchmarks

Day 11

Day 11 Benchmarks

Day 12

Day 12 Benchmarks

Day 13

Day 13 Benchmarks

Day 14

Day 14 Benchmarks

Day 15

Day 15 Benchmarks

Day 16

Day 16 Benchmarks

Day 17

Day 17 Benchmarks

Clone this wiki locally