Advent of Code 2020 - Day 25

By Eric Burden | December 26, 2020

In the spirit of the holidays (and programming), I’ll be posting my solutions to the Advent of Code 2020 puzzles here, at least one day after they’re posted (no spoilers!). I’ll be implementing the solutions in R because, well, that’s what I like! What I won’t be doing is posting any of the actual answers, just the reasoning behind them.

Also, as a general convention, whenever the puzzle has downloadable input, I’m saving it in a file named input.txt.

Day 25 - Combo Breaker

Find the problem description HERE.

Part One - Stairmaster

This is it! Having reached our hotel and climbed an unnecessary number of stairs, we’re at our resort! Now we just need to break into the room. No sweat. The instructions for this part were a bit confusing, so I’m going to paraphrase and hopefully not make it worse (using the numbers from the example):

  • There is a number called the ‘subject number’, it starts with a value of 7.
  • There is a number called ‘value’, it starts with a value of 1.
  • Your card and door have public keys:
    • ‘card public key’ = 5764801
    • ‘door public key’ = 17807724
  • If you repeatedly update the ‘value’ according to the following formula: value = (value * subject number) mod 20201227, the number of times you need to perform that operation in order to get one of the public keys is that public key’s ’loop size’. Each public key has its own loop size, which we’ll call ‘card loop size’ and ‘door loop size’. You only need one of these.
  • Once you have a ’loop size’, you can use the other public key to calculate the encryption key using that public key as a ‘subject number’ and iterating ’loop size times’. For example, say you have the ‘card loop size’, the encryption key can be calculated by (‘value’ starts at 1 again): encryption key = { value = (value * door public key) mod 20201227 } iterated 'card loop size' times

Ta-da! On to the show!

subject <- 7                        # The given subject number
public_keys <- c(3248366, 4738476)  # The given public keys
loops <- numeric(2)                 # An empty vector
value <- 1                          # The starting value

i <- 1  # Iteration count

# Until we add a number to the `loops` vector
while (loops[1] == 0 & loops[2] == 0) {
  value <- (value * subject) %% 20201227  # Calculate the new value
  
  # If the calculated value equals one of the public keys, add the iterator
  # value to `loops` at the appropriate index
  if (value == public_keys[1]) { loops[1] <- i }
  if (value == public_keys[2]) { loops[2] <- i }
  
  i <- i + 1
}

# Depending on which loop size we found, prepare to calculate the
# encryption key with a `new_subject` number and a known number of
# iterations
if (loops[1] > 0) {
  new_subject <- public_keys[2]
  loops <- loops[1]
} else {
  new_subject <- public_keys[1]
  loops <- loops[2]
}

# Start calculating again, same process as before
value <- 1
for (i in 1:loops) { value <- (value * new_subject) %% 20201227 }

answer1 <- value  # The answer

No functions, no real set up, just straight processing. According to some commentary I’ve read, this is similar (the same?) to how Diffie-Hellman cryptographic handshakes occur, and there are some cool, math-y ways to do this more efficiently. That’s great! I encourage everyone to read up on this stuff, and I need to as well.

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.

If you’ve poked around my site, then you should have gotten the idea that I’m not a traditional programmer. My education includes a Bachelor’s in Chemistry, an unfinished PhD in Polymer Science, and a Master’s in Social Work. When it comes to coding, I’m mostly self-taught with a mix of tutorials, online classes, and documentation, with a bit of stubbornness thrown in for good measure. My day-to-day work consists of a mix of data analysis and business process design, with a healthy dose of quality improvement thrown into the mix. I’m as likely to be speaking with someone about the vagaries of HIPAA or accountable data collection as I am to be writing code.

I say all that as a way of meandering to this point: A lot of my coding efforts have been aimed at solving problems that rarely depend on the types of implementation concerns that were raised in the Advent of Code puzzles, and I love AoC for that. I’ve been dipping my toe into more ‘programmer’ circles this year as I have grown more confident in my technical skillset, and AoC really gave me the opportunity to explore some concepts and approaches that I haven’t really considered before. There are more than a couple of things that I’ve learned over this past month that will help me write cleaner, more performant, and more readable code, and for that I am grateful.

In addition, I learned about Advent of Code just this year, thanks to the truly awesome community at Code Connector. I won’t name names (because I haven’t asked for permission, yet), but if you are a new developer, experienced industry veteran, or just someone who thinks learning to code would be neat, you won’t find a more welcoming, supportive community anywhere online. Especially if you’re in the Memphis, TN or Birmingham, AL areas (where the in-person meetups occur when there’s no pandemic raging), I encourage you to connect, or take advantage of the fact that space is relative in the age of COVID and the internet and join the online meetups and Slack. It was these folks who kept me inspired and motivated to finish out AoC despite all the ’extra’ going on this holiday season.

So, if you haven’t yet started coding your own solutions to Advent of Code, I encourage you to do so. In fact, I may use this opportunity next year (or sooner, the puzzles from past years stay up all year) to work on a new language. I’m thinking Rust, maybe. A huge thank you to Eric Wastle 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 (158,221 completed at least one puzzle this year) 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!

comments powered by Disqus