By: Julia on Eric Burden

Re-posted from: https://ericburden.work/blog/2022/01/06/advent-of-code-2021-day-25/

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub 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 25 – Sea Cucumber

Find the problem description HERE.

The Input – Echinodermic Perambulation

Here we are! The final advent puzzle, and after a brief jaunt into strange and unusual input formats (that we didn’t actually write parsing code for), here we are again. Parsing input from a text file, how I have missed you!

# No fancy data structures this time, just two `BitMatrix`, one representing the
# locations of east-bound cucumbers, and one representing the locations of
# sounth-bound cucumbers, on a 2D grid. Can you tell I'm ready to be done?
function ingest(path)
    eastlines  = []
    southlines = []
    open(path) do f
        for line in readlines(f)
            chars = collect(line)
            push!(eastlines,  chars .== '>')
            push!(southlines, chars .== 'v')
        end
    end
    eastmatrix  = reduce(hcat, eastlines)  |> transpose |> BitMatrix
    southmatrix = reduce(hcat, southlines) |> transpose |> BitMatrix
    return (eastmatrix, southmatrix)
end

Ah, the tried and true ‘parse the grid to a BitMatrix’ approach! With two matrices!

Part One – The Cucumbers Go Marching

It looks like, at some point, the sea cucumbers will deadlock and stop moving about so much, giving us space to land the submarine. Guess you have to land submarines, then? Never considered that, to be honest, it just hasn’t come up before. Ah well, the good news is that, even here on the ocean floor, traffic is bound to come to a standstill sooner or later. Since they’re apparently quite polite, a sea cucumber will only move if there’s an empty space in front of it at the start of a round, and all the east-bound cucumbers try to move before the south-bound cucumbers. With all that in mind, we’re ready to proceed.

# Helper Functions -------------------------------------------------------------

# For checking on the total state of cucumber migration.
function pprint(east::BitMatrix, south::BitMatrix)
    template = fill('.', size(east))
    template[east]  .= '>'
    template[south] .= 'v'
    for row in eachrow(template)
        for char in row
            print(char)
        end
        println()
    end
end

# Move all the east-bound cucumbers that can be moved
function moveeast(east::BitMatrix, south::BitMatrix)
    occupied   = east .| south      # Spaces occupied by any type of cucumber
    nextstate  = falses(size(east)) # An empty BitMatrix, same size as `east`
    ncols      = size(east, 2)      # Number of columns in the grid
    colindices = collect(1:ncols)   # Vector of column indices

    # For each pair of column index and column index + 1 (wrapped around due
    # to space-defying ocean currents)...
    for (currcol, nextcol) in zip(colindices, circshift(colindices, -1))
        # Identify the cucumbers who moved in `currcol` by the empty spaces
        # in `nextcol`
        moved = east[:,currcol]  .& .!occupied[:,nextcol]

        # Identify the cucumbers who waited in `currcol` by the occupied
        # spaces in `nextcol`
        stayed = east[:,currcol] .& occupied[:,nextcol]

        # Place the updated cucumber positions into `nextstate`
        nextstate[:,nextcol] .|= moved
        nextstate[:,currcol] .|= stayed
    end

    return nextstate
end

# Move all the south-bound cucumbers than can be moved
function movesouth(east::BitMatrix, south::BitMatrix)
    occupied   = east .| south       # Spaces occupied by any type of cucumber
    nextstate  = falses(size(south)) # An empty BitMatrix, same size as `south`
    nrows      = size(south, 1)      # Number of rows in the grid
    rowindices = collect(1:nrows)    # Vector of row indices

    # For each pair of row index and row index + 1 (wrapped around due to
    # intradimensional currents)...
    for (currrow, nextrow) in zip(rowindices, circshift(rowindices, -1))
        # Identify the cucumbers who moved in `currrow` by the empty spaces
        # in `nextrow`
        moved = south[currrow,:] .& .!occupied[nextrow,:]

        # Identify the cucumbers who waited in `currrow` by the occupied
        # spaces in `nextrow`
        stayed = south[currrow,:] .& occupied[nextrow,:]

        # Place the updated cucumber positions into `nextstate`
        nextstate[nextrow,:] .|= moved
        nextstate[currrow,:] .|= stayed
    end

    return nextstate
end

# Move the herd(s)! Get the next state for east-bound and south-bound cucumbers,
# check to see if any of their positions changed, and return the results
function move(east::BitMatrix, south::BitMatrix)
    nexteast  = moveeast(east, south)
    nextsouth = movesouth(nexteast, south)

    eastchanged  = east  .⊻ nexteast
    southchanged = south .⊻ nextsouth
    anychanged = any(eastchanged .| southchanged)

    return (anychanged, nexteast, nextsouth)
end


# Solve Part One ---------------------------------------------------------------

# Solve it! Just keep updating the cucumber positions in a loop until they don't
# change, then report the number of rounds that took.
function part1(input)
    (east, south) = input
    rounds = 0
    anychanged = true
    while anychanged
        (anychanged, east, south) = move(east, south)
        rounds += 1
    end
    return rounds
end

I bet that trip from one edge of the transit zone (?) to the other is wild! Good thing these space-warping ocean currents don’t seem to affect submarines, or we’d be in trouble…

Part Two – Reflection

If you haven’t heard, Day 25 – Part Two is always the “go back and finish the rest of the puzzles” challenge, so no extra coding needed here. Instead, I’d like to use this space to reflect on the Advent of Code puzzles for this year and my experience with them.

This is my second year with Advent of Code, as I was introduced to it last year by a friend on a community Slack channel. Just like last year, this experience created a lot of joy, frustration, annoyance, elation, and satisfaction for me, which is typical of my experience with good puzzles. Since last year, I’ve spent a lot more time honing my knowledge of algorithms and data structures, partly as a way to scratch the itch that AoC helped to create, and partly as a way of sharing this love of puzzles with others. You see, in that community Slack channel I mentioned, some friends and I have starting hosting regular meetups aimed at both spending some time solving puzzles and helping some of the folks who are newer to our community practice live-coding for technical interviews. It’s been a blast, and I look forward to continuing into the new year. (Here’s the GitHub repo if you’re curious about our meetups, anyone is welcome to join).

This year came with it’s own set of challenges, from figuring out how to see family during the holidays (thanks Omicron!) to navigating my own bout of non-COVID related illness (I’m fine, but those were an unpleasant few days). There were a few days of puzzles that set me back on my “solve AoC > write blog post” daily cycle, and I had to consider my holiday priorities as a result. In the end, since this blog post isn’t going up until a few days into January, you can probably guess how that worked out. I really enjoy solving these puzzles, and I can get a bit obsessive when I’ve got an unsolved problem lying around in my head, but time with my family is just too precious to short-change. That’s an area I can get better in, to be honest. Weird how coding puzzles can teach life lessons, too.

I’ve been working through the AoC puzzles in Julia this year, and I’m not sure if it’s because of how similar some of the concepts are to R (my most proficient language), the amount of practice I’ve put in over the year, or just general growth as a programmer, but I found thinking through these puzzles in Julia to be a pretty seamless experience. When I did this with Rust, there was definitely a learning curve related to getting the code to do the things I had in my head, but it just seemed to flow a lot more smoothly in Julia. There’s a lot of really ergonomic syntax in Julia, enabled in part by it being a dynamic language, but I don’t think that’s the whole story. My recent time in Rust encouraged me to add Types in lots of places that, according to the Julia documentation and other talks/articles I’ve seen and read, I really didn’t have to and probably shouldn’t have. Frankly, I like Types, and I find being explicit about data types in my code tends to make it easier for me to reason about and clarifies what I did when I come back to it later. In particular, I found the syntax for single-line function assignment, multiple dispatch, native multidimensional array support, and the breadth and diversity of the Base package to be some of the really compelling features of Julia. The speed gains over R and Python (those operations not directly backed by Rust or C or FORTRAN) are significant, but not always as significant as I would have hoped. There’s probably a lot of room for me to improve in optimizing Julia code, though, so I suspect I’ve left a lot of performance on the table. Guess this means I’ll have to keep writing Julia code, then. As a next step, I’d like to get familiar with the Dataframes.jl and Makie.jl (data frames and plotting) packages, since that’s the kind of work I most often tend to do for my day job. Who knows, maybe Julia will inspire me to finally dabble in a bit of machine learning? I hear that’s a pretty hot topic…

I’ve really enjoyed writing this blog series. As usual, explaining how I did things (even to what I imagine to be, like, five random people on the internet who stumble across this site or these articles wherever they get posted) really helped me to clarify, correct, refactor, and update my own understanding. I recommend coding puzzles regularly to new and aspiring programmers, but I’d also recommend finding someone who could benefit from your knowledge (whatever level you feel like you’re at) and giving teaching/explaining a go. Communication skills are important for growing your career (and being a good human), and I feel like teaching, even a little, is a great way to grow those skills and your understanding of the topic.

Just like last year, I’d like to send out a huge thank you to Eric Wastl and his crew of helpers for putting this event/phenomenon on and keeping it running. If you can, please consider donating to this effort to help keep the magic going, I guarantee there will be a lot of coders (215,955 completed at least one puzzle this year, as of the time of writing) who will be glad you did.

If you’re interested, you can find all the code from this blog series on GitHub, please feel free to submit a pull request if you’re really bored. Happy Holidays!

By: Julia on Eric Burden

Re-posted from: https://www.ericburden.work/blog/2022/01/06/advent-of-code-2021-day-25/

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub 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 25 – Sea Cucumber

Find the problem description HERE.

The Input – Echinodermic Perambulation

Here we are! The final advent puzzle, and after a brief jaunt into strange and unusual input formats (that we didn’t actually write parsing code for), here we are again. Parsing input from a text file, how I have missed you!

# No fancy data structures this time, just two `BitMatrix`, one representing the
# locations of east-bound cucumbers, and one representing the locations of
# sounth-bound cucumbers, on a 2D grid. Can you tell I'm ready to be done?
function ingest(path)
    eastlines  = []
    southlines = []
    open(path) do f
        for line in readlines(f)
            chars = collect(line)
            push!(eastlines,  chars .== '>')
            push!(southlines, chars .== 'v')
        end
    end
    eastmatrix  = reduce(hcat, eastlines)  |> transpose |> BitMatrix
    southmatrix = reduce(hcat, southlines) |> transpose |> BitMatrix
    return (eastmatrix, southmatrix)
end

Ah, the tried and true ‘parse the grid to a BitMatrix’ approach! With two matrices!

Part One – The Cucumbers Go Marching

It looks like, at some point, the sea cucumbers will deadlock and stop moving about so much, giving us space to land the submarine. Guess you have to land submarines, then? Never considered that, to be honest, it just hasn’t come up before. Ah well, the good news is that, even here on the ocean floor, traffic is bound to come to a standstill sooner or later. Since they’re apparently quite polite, a sea cucumber will only move if there’s an empty space in front of it at the start of a round, and all the east-bound cucumbers try to move before the south-bound cucumbers. With all that in mind, we’re ready to proceed.

# Helper Functions -------------------------------------------------------------

# For checking on the total state of cucumber migration.
function pprint(east::BitMatrix, south::BitMatrix)
    template = fill('.', size(east))
    template[east]  .= '>'
    template[south] .= 'v'
    for row in eachrow(template)
        for char in row
            print(char)
        end
        println()
    end
end

# Move all the east-bound cucumbers that can be moved
function moveeast(east::BitMatrix, south::BitMatrix)
    occupied   = east .| south      # Spaces occupied by any type of cucumber
    nextstate  = falses(size(east)) # An empty BitMatrix, same size as `east`
    ncols      = size(east, 2)      # Number of columns in the grid
    colindices = collect(1:ncols)   # Vector of column indices

    # For each pair of column index and column index + 1 (wrapped around due
    # to space-defying ocean currents)...
    for (currcol, nextcol) in zip(colindices, circshift(colindices, -1))
        # Identify the cucumbers who moved in `currcol` by the empty spaces
        # in `nextcol`
        moved = east[:,currcol]  .& .!occupied[:,nextcol]

        # Identify the cucumbers who waited in `currcol` by the occupied
        # spaces in `nextcol`
        stayed = east[:,currcol] .& occupied[:,nextcol]

        # Place the updated cucumber positions into `nextstate`
        nextstate[:,nextcol] .|= moved
        nextstate[:,currcol] .|= stayed
    end

    return nextstate
end

# Move all the south-bound cucumbers than can be moved
function movesouth(east::BitMatrix, south::BitMatrix)
    occupied   = east .| south       # Spaces occupied by any type of cucumber
    nextstate  = falses(size(south)) # An empty BitMatrix, same size as `south`
    nrows      = size(south, 1)      # Number of rows in the grid
    rowindices = collect(1:nrows)    # Vector of row indices

    # For each pair of row index and row index + 1 (wrapped around due to
    # intradimensional currents)...
    for (currrow, nextrow) in zip(rowindices, circshift(rowindices, -1))
        # Identify the cucumbers who moved in `currrow` by the empty spaces
        # in `nextrow`
        moved = south[currrow,:] .& .!occupied[nextrow,:]

        # Identify the cucumbers who waited in `currrow` by the occupied
        # spaces in `nextrow`
        stayed = south[currrow,:] .& occupied[nextrow,:]

        # Place the updated cucumber positions into `nextstate`
        nextstate[nextrow,:] .|= moved
        nextstate[currrow,:] .|= stayed
    end

    return nextstate
end

# Move the herd(s)! Get the next state for east-bound and south-bound cucumbers,
# check to see if any of their positions changed, and return the results
function move(east::BitMatrix, south::BitMatrix)
    nexteast  = moveeast(east, south)
    nextsouth = movesouth(nexteast, south)

    eastchanged  = east  .⊻ nexteast
    southchanged = south .⊻ nextsouth
    anychanged = any(eastchanged .| southchanged)

    return (anychanged, nexteast, nextsouth)
end


# Solve Part One ---------------------------------------------------------------

# Solve it! Just keep updating the cucumber positions in a loop until they don't
# change, then report the number of rounds that took.
function part1(input)
    (east, south) = input
    rounds = 0
    anychanged = true
    while anychanged
        (anychanged, east, south) = move(east, south)
        rounds += 1
    end
    return rounds
end

I bet that trip from one edge of the transit zone (?) to the other is wild! Good thing these space-warping ocean currents don’t seem to affect submarines, or we’d be in trouble…

Part Two – Reflection

If you haven’t heard, Day 25 – Part Two is always the “go back and finish the rest of the puzzles” challenge, so no extra coding needed here. Instead, I’d like to use this space to reflect on the Advent of Code puzzles for this year and my experience with them.

This is my second year with Advent of Code, as I was introduced to it last year by a friend on a community Slack channel. Just like last year, this experience created a lot of joy, frustration, annoyance, elation, and satisfaction for me, which is typical of my experience with good puzzles. Since last year, I’ve spent a lot more time honing my knowledge of algorithms and data structures, partly as a way to scratch the itch that AoC helped to create, and partly as a way of sharing this love of puzzles with others. You see, in that community Slack channel I mentioned, some friends and I have starting hosting regular meetups aimed at both spending some time solving puzzles and helping some of the folks who are newer to our community practice live-coding for technical interviews. It’s been a blast, and I look forward to continuing into the new year. (Here’s the GitHub repo if you’re curious about our meetups, anyone is welcome to join).

This year came with it’s own set of challenges, from figuring out how to see family during the holidays (thanks Omicron!) to navigating my own bout of non-COVID related illness (I’m fine, but those were an unpleasant few days). There were a few days of puzzles that set me back on my “solve AoC > write blog post” daily cycle, and I had to consider my holiday priorities as a result. In the end, since this blog post isn’t going up until a few days into January, you can probably guess how that worked out. I really enjoy solving these puzzles, and I can get a bit obsessive when I’ve got an unsolved problem lying around in my head, but time with my family is just too precious to short-change. That’s an area I can get better in, to be honest. Weird how coding puzzles can teach life lessons, too.

I’ve been working through the AoC puzzles in Julia this year, and I’m not sure if it’s because of how similar some of the concepts are to R (my most proficient language), the amount of practice I’ve put in over the year, or just general growth as a programmer, but I found thinking through these puzzles in Julia to be a pretty seamless experience. When I did this with Rust, there was definitely a learning curve related to getting the code to do the things I had in my head, but it just seemed to flow a lot more smoothly in Julia. There’s a lot of really ergonomic syntax in Julia, enabled in part by it being a dynamic language, but I don’t think that’s the whole story. My recent time in Rust encouraged me to add Types in lots of places that, according to the Julia documentation and other talks/articles I’ve seen and read, I really didn’t have to and probably shouldn’t have. Frankly, I like Types, and I find being explicit about data types in my code tends to make it easier for me to reason about and clarifies what I did when I come back to it later. In particular, I found the syntax for single-line function assignment, multiple dispatch, native multidimensional array support, and the breadth and diversity of the Base package to be some of the really compelling features of Julia. The speed gains over R and Python (those operations not directly backed by Rust or C or FORTRAN) are significant, but not always as significant as I would have hoped. There’s probably a lot of room for me to improve in optimizing Julia code, though, so I suspect I’ve left a lot of performance on the table. Guess this means I’ll have to keep writing Julia code, then. As a next step, I’d like to get familiar with the Dataframes.jl and Makie.jl (data frames and plotting) packages, since that’s the kind of work I most often tend to do for my day job. Who knows, maybe Julia will inspire me to finally dabble in a bit of machine learning? I hear that’s a pretty hot topic…

I’ve really enjoyed writing this blog series. As usual, explaining how I did things (even to what I imagine to be, like, five random people on the internet who stumble across this site or these articles wherever they get posted) really helped me to clarify, correct, refactor, and update my own understanding. I recommend coding puzzles regularly to new and aspiring programmers, but I’d also recommend finding someone who could benefit from your knowledge (whatever level you feel like you’re at) and giving teaching/explaining a go. Communication skills are important for growing your career (and being a good human), and I feel like teaching, even a little, is a great way to grow those skills and your understanding of the topic.

Just like last year, I’d like to send out a huge thank you to Eric Wastl and his crew of helpers for putting this event/phenomenon on and keeping it running. If you can, please consider donating to this effort to help keep the magic going, I guarantee there will be a lot of coders (215,955 completed at least one puzzle this year, as of the time of writing) who will be glad you did.

If you’re interested, you can find all the code from this blog series on GitHub, please feel free to submit a pull request if you’re really bored. Happy Holidays!

By: Julia on Eric Burden

Re-posted from: https://www.ericburden.work/blog/2022/01/05/advent-of-code-2021-day-24/

It’s that time of year again! Just like last year, I’ll be posting my solutions to the Advent of Code puzzles. This year, I’ll be solving the puzzles in Julia. I’ll post my solutions and code to GitHub 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.

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…

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).

#(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!