Advent of Code 2021 - Day 24
Tags: julia, adventofcode, coding
Published: 2022-01-06 22:12:17

---
title: Advent of Code 2021 - Day 24
published: true
date: 2022-01-05 00:00:00 UTC
tags: julia, adventofcode, coding
canonical_url: https://www.ericburden.work/blog/2022/01/05/advent-of-code-2021-day-24/
series: Advent of Code 2021
---

It’s that time of year again! Just like last year, I’ll be posting my solutions to the [Advent of Code](https://adventofcode.com/) puzzles. This year, I’ll be solving the puzzles in [Julia](https://julialang.org). I’ll post my solutions and code to [GitHub](https://github.com/ericwburden/advent_of_code_2021) as well. I had a blast with AoC last year, first in R, then as a set of exercises for learning Rust, so I’m really excited to see what this year’s puzzles will bring. If you haven’t given AoC a try, I encourage you to do so along with me!

# Day 24 - Arithmetic Logic Unit

Find the problem description [HERE](https://adventofcode.com/2021/day/24).

## The Puzzle - The Whole Enchilada

> MONAD imposes additional, mysterious restrictions on model numbers, and legend says the last copy of the MONAD documentation was eaten by a tanuki. **You’ll need to figure out what MONAD does some other way.**

Today’s puzzle took a bit of effort on my part just to figure out exactly what it was we were trying to do. Essentially, we are given a set of instructions (with some explanation about how to parse them), then informed that _somehow_ this set of instructions can be used to validate a 14 digit number. 14 digits, eh? You know, after looking at that input program, it looks like there are 14 different chunks there, as well…

 ![Table comparing the 14 chunks of the puzzle input](https://www.ericburden.work/blog/2022/01/05/advent-of-code-2021-day-24/images/AoC%20Day%2024%20Table%201.png)

In fact, among those 14 chunks, there are only three lines that differ from one chunk to the next. Those must be the important bits! Let’s give each of them a name. I opted for `optype`, `correction`, and `offset`, for reasons that might make sense as we continue. Working through each chunk, we get the following pseudocode which expresses the operation of each ALU code chunk:

```
x = ((z mod 26) + correction) != w
z = floor(z / optype)
z = z * ((25 * x) + 1)
z = z + ((w + offset) * x)

```

You’ll either need to trust me on that or work through one of the chunks yourself (it’s a bit tedious, but not too bad). As you can see, `y` ends up being unnecessary to keep track of (`mul x 0` and `mul y 0` reset `x` and `y` to zero, respectively) and we only need `w` to determine whether `x` is a 1 or 0, a boolean value. The last line modifies `z` depending on whether or not `w` is true or false. If that sounds a bit like a conditional expression, then you’re right! The chunk above can then be simplified to:

```
if (z mod 26) + correction != w
    z = floor(z / optype)
    z = z * 26
    z = z + (w + offset)
else
    z = floor(z / optype)
end

```

Another look at our input program reveals that `optype` can only be `1` or `26`, which will determine what type of operation we perform (`optype`, get it?).

```
optype == 1                        | optype == 26
if (z mod 26) + correction != w    | if (z mod 26) + correction != w
    z = z * 26                     |     z = floor(z / 26) 
    z = z + (w + offset)           |     z = z * 26
end                                |     z = z + (w + offset)
                                   | else
                                   |     z = floor(z / 26)
                                   | end

```

Ok, so what does this mean, exactly? For one, we were able to drop the `else` clause from the `optype == 1` case, since `z == floor(z / 1)` for all integers. For another, let’s consider our input again, particularly chunks 3 and 4, which have an `optype` of 1 and 26, respectively. What, then, do those chunks _do_? Let’s try them and see! We’ll assume, for the sake of experimentation, that `z` is 0 going into chunk 3.

```
chunk 3: optype => 1; correction => 14; offset => 8

Assume z == 0 (it doesn't really matter, as you'll see, but it does simplify 
the expressions a bit. For fun, try working through this with any positive 
integer value for z and see what happens)

(0 mod 26) + 14 -> 14 != w # Since 1 <= w <= 9, w _can't_ == 14
    z = 0 * 26 -> 0
    z = (w + 8)


chunk 4: optype => 26; correction => -5; offset => 5

We'll use `w3` as a standin for the w from chunk 3, to differentiate. I'm 
leaving the variable in to demonstrate what's really being compared. So, to 
start chunk 4, z = (w3 + 8)

(z mod 26) -> (w3 + 8)
(w3 + 8) - 5 -> (w3 + 3)

There are two scenarios here. Either w3 + 3 == w4, or it doesn't...

w3 + 3 != w4                      | w3 + 3 == w4
    # w3 + 8 is less than 26      |     z = floor((w3 + 8) / 26) -> 0
    z = floor((w3 + 8) / 26) -> 0 |
    z = 0 * 26 -> 0               |
    z = (w4 + 5)                  |

```

So, the only thing chunk 3 _can_ do here is multiply `z` by 26 and add `w<3> + offset<3>`. Chunk 4 is going to remove `w<3> + offset<3>` from `z` regardless, but if `w<4> != w<3> + offset<3> + correction<4>`, then chunk 4 will add `w<4> + offset<4>` back to `z`. This means that z is a base-26 number, and each time `optype == 1`, z is shifted to the left and the value of `w + offset` is tacked on to the end. Each time `optype = 26`, depending on the `w` (input) values, either the last value tacked on to `z` is erased, or the last value is erased and replaced with a different `w + offset`. Since our goal is to have `z == 0` at the end of this process, we should then strive to identify values of `w` that can be ‘canceled out’ from one chunk to the next. This also means that, for every `optype == 1` chunk, there should be a corresponding `optype == 26` chunk. And, wouldn’t you know, there are 7 of each kind of chunk, for 14 total digits. Let’s try to pair them off:

```
chunk  1: optype == 1 ─────┐
chunk  2: optype == 1 ────┐│
chunk  3: optype == 1  ┐  ││
chunk  4: optype == 26 ┘  ││
chunk  5: optype == 1 ───┐││
chunk  6: optype == 1  ─┐│││
chunk  7: optype == 1  ┐││││    ________________
chunk  8: optype == 26 ┘││││  < That's a stack! >
chunk  9: optype == 26 ─┘│││    ----------------
chunk 10: optype == 1  ┐ │││        \  ^__^
chunk 11: optype == 26 ┘ │││         \ (oo)\ _______
chunk 12: optype == 26 ──┘││           (__)\        )\/\
chunk 13: optype == 26 ───┘│                ||----w |
chunk 14: optype == 26 ────┘                ||     ||

```

You know what, cow, you’re right! That _does_ look exactly like a stack. And, based on what we learned earlier, it’s a stack that gets pushed to every time `optype == 1`, and that get’s popped (and optionally pushed) every time `optype == 26`. Based on these pairings, we can now deduce the relationships between each of the digits in our final number. I’ll be filling in values for offset and correction from the table above.

```
offset<1> + correction<14> == -1
w<1> - 1 == w<14> <|> w<14> + 1 == w<1>

offset<2> + correction<13> == -6
w<2> - 6 == w<13> <|> w<13> + 6 == w<2>

offset<3> + correction<4> == +3
w<3> + 3 == w<4> <|> w<4> - 3 == w<3>

offset<5> + correction<12> == +8
w<5> + 8 == w<12> <|> w<12> - 8 == w<5>

offset<6> + correction<9> == +1
w<6> + 1 == w<9> <|> w<9> - 1 == w<6>

offset<7> + correction<8> == -8
w<7> - 8 == w<8> <|> w<8> + 8 == w<7>

offset<10> + correction<11> == +2
w<10> + 2 == w<11> <|> w<11> - 2 == w<10>

```

Well, now, I daresay we know everything we need to start filling in digits, and solving this puzzle! Again, looking at the pair between chunks 3 and 4, we see that `w<3> + 3 == w<4>`. The largest digits we can place into `w<3>` and `w<4>` that will satisfy this constraint (while keeping each digit in the range from 1 -> 9), are `w<3> = 6` and `w<4> = 9`. Do this for the rest of the digit pairs, and you have your answer to part one of the puzzle!

Since part two asks for the smallest valid model number, we don’t need to deduce anything new. Instead, we just need to fill in the smallest digits that will meet our constraints. For the chunk 3/chunk 4 pairing, that works out to `w<3> = 1` and `w<4> = 4`. Fill out the rest of the digits, and we’ve earned ourselves another gold star.

## Some Code - You Complete Me

There wasn’t any way that I was going to finish up this blog post without _any_ code, however. While I solved the puzzle without any code, I did write the function below which could be used to validate model numbers using the method we described above. Fun fact: there are only two valid model numbers anyway! (Can you tell why that is? Hint: check out chunks 5/12 and chunks 7/8).

```julia
#(optype, correction, offset)
const PARAMS = [
    ( 1, 13, 0), # d[1] + 0 - 1 == d[14] -> d[1] - 1 == d[14] | 9 | 2
    ( 1, 11, 3), # d[2] + 3 - 9 == d[13] -> d[2] - 6 == d[13] | 9 | 7
    ( 1, 14, 8), # d[3] + 8 - 5 == d[4] -> d[3] + 3 == d[4] | 6 | 1
    (26, -5, 5), # d[4] - 8 + 5 == d[3] -> d[4] - 3 == d[3] | 9 | 4
    ( 1, 14, 13), # d[5] + 13 - 5 == d[12] -> d[5] + 8 == d[12] | 1 | 1
    ( 1, 10, 9), # d[6] + 9 - 8 == d[9] -> d[6] + 1 == d[9] | 8 | 1
    ( 1, 12, 6), # d[7] + 6 - 14 == d[8] -> d[7] - 8 == d[8] | 9 | 9
    (26, -14, 1), # d[8] - 6 + 14 == d[7] -> d[8] + 8 == d[7] | 1 | 1
    (26, -8, 1), # d[9] - 9 + 8 == d[6] -> d[9] - 1 == d[6] | 9 | 2
    ( 1, 13, 2), # d[10] + 2 - 0 == d[11] -> d[10] + 2 == d[11] | 7 | 1
    (26, 0, 7), # d[11] - 2 + 0 == d[10] -> d[11] - 2 == d[10] | 9 | 3
    (26, -5, 5), # d[12] - 13 + 5 == d[5] -> d[12] - 8 == d[5] | 9 | 9
    (26, -9, 8), # d[13] - 3 + 9 == d[2] -> d[13] + 6 == d[2] | 3 | 1
    (26, -1, 15) # d[14] - 0 + 1 == d[1] -> d[14] + 1 == d[1] | 8 | 1
] 

# This function can be used to check whether a given number is a valid model
# number, according to the MONAD program.
function isvalid(n::Int64)
    ndigits = reverse(digits(n))

    # Valid model numbers don't contain `0` as a digit
    0 ∈ ndigits && return false
    stack = []; sizehint!(stack, length(ndigits))

    for (w, (optype, correction, offset)) in zip(ndigits, PARAMS)
        if optype == 1
            push!(stack, w + offset)
            continue
        end
        stack[end] + correction == w && pop!(stack)
    end

    # In a valid model number, half the digits will be "canceled" out by the
    # other half, leaving an empty stack
    return isempty(stack)
end

```

# Wrap Up

At first, I wasn’t sure how to feel about this puzzle. On the one hand, I do AoC primarily to practice my coding skills (in Julia, this year). On the other hand, this required a fair bit of deduction and mental flexing to suss out, which is massively satisfying once the puzzle is complete. You know what? I had fun. I suppose that’s pretty important, too, now and again. Only one more day (and one more puzzle) left to go!

If you found a different solution (or spotted a mistake in one of mine), please drop me a line!