Advent of Code 2020: Day 25

, 6 min read
advent of code 2020

Part 1

You finally reach the check-in desk. Unfortunately, their registration systems are currently offline, and they cannot check you in. Noticing the look on your face, they quickly add that tech support is already on the way! They even created all the room keys this morning; you can take yours now and give them your room deposit once the registration system comes back online.

The room key is a small RFID card. Your room is on the 25th floor and the elevators are also temporarily out of service, so it takes what little energy you have left to even climb the stairs and navigate the halls. You finally reach the door to your room, swipe your card, and - beep - the light turns red.

Unfortunately for the door, you know a thing or two about cryptographic handshakes.

The handshake used by the card and the door involves an operation that transforms a subject number. To transform a subject number, start with the value 1. Then, a number of times called the loop size, perform the following steps:

  1. Set the value to itself multiplied by the subject number.
  2. Set the value to the remainder after dividing the value by 20201227.

The card always uses a specific, secret loop size when it transforms a subject number. The door always uses a different, secret loop size.

The cryptographic handshake works like this:

  1. The card transforms the subject number of 7 according to the card’s secret loop size. The result is called the card’s public key.
  2. The door transforms the subject number of 7 according to the door’s secret loop size. The result is called the door’s public key.
  3. The card and door use the wireless RFID signal to transmit the two public keys (your puzzle input) to the other device. Now, the card has the door’s public key, and the door has the card’s public key. Because you can eavesdrop on the signal, you have both public keys, but neither device’s loop size.
  4. The card transforms the subject number of the door’s public key according to the card’s loop size. The result is the encryption key.
  5. The door transforms the subject number of the card’s public key according to the door’s loop size. The result is the same encryption key as the card calculated.

If you can use the two public keys to determine each device’s loop size, you will have enough information to calculate the secret encryption key that the card and door use to communicate; this would let you send the unlock command directly to the door!

At this point, you can use either device’s loop size with the other device’s public key to calculate the encryption key. Transforming the subject number of 17807724 (the door’s public key) with a loop size of 8 (the card’s loop size) produces the encryption key, 14897079.

What encryption key is the handshake trying to establish?

You can read the full text here. Well since it’s christmas day, I’m glad that this puzzle didn’t take too long to solve. We need to “crack” some encryption.

Fortunately, we know a lot about how the encryption works. The process starts with a number, 1. We then loop through, n times, multiply the current value by the subject value and take the remainder with 20201227. Fortunately, the input is just two numbers today so we’ll start by writing out basic transform function,

1
2
3
4
5
6
7
long int transform(long int current, long int subject, long int loop_size){
    for(int i=0; i<loop_size; i++){
        current *= subject;
        current %= 20201227;
    }
    return current;
}

I’ve made this a little general. Thus instead of starting with the value 1 hardcoded, we can start at any value, current. This allows us to transform a number, look at the value and then re-enter that value into the function to transform it again. We know that the starting value is 1, and than the subject is 7. We then need to figure out the loop size for our two device numbers (the puzzle input).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
long int key1 = 9789649;
long int key2 = 3647239;

long int guess = 1;
long int i = 1;
long int n1 = 0, n2 = 0;
while (n1 * n2 == 0){
    guess = transform(guess, 7, 1);
    if (guess == key1)
        n1 = i;
    if (guess == key2)
        n2 = i;
    i++;
}

We just loop through from the starting value and repeatedly transform the value until we find the keys that we are looking for. When we find the value we are looking for we store how many transformations this process took.

Now we have the number of loops we can generate the encryption key. All we need to do is,

1
2
ans1 = transform(1, key1, n2);
std::cout << "Answer 1: " << ans1 << std::endl;

Perfect! We have the first star, ⭐ of Christmas Day!

The full code can be found on github

Part 2

The light turns green and the door unlocks. As you collapse onto the bed in your room, your pager goes off!

“It’s an emergency!” the Elf calling you explains. “The soft serve machine in the cafeteria on sub-basement 7 just failed and you’re the only one that knows how to fix it! We’ve already dispatched a reindeer to your location to pick you up.”

You hear the sound of hooves landing on your balcony.

The reindeer carefully explores the contents of your room while you figure out how you’re going to pay the 50 stars you owe the resort before you leave. Noticing that you look concerned, the reindeer wanders over to you; you see that it’s carrying a small pouch.

“Sorry for the trouble,” a note in the pouch reads. Sitting at the bottom of the pouch is a gold coin with a little picture of a starfish on it.

Looks like you only needed 49 stars after all.

You can read the full text here.

We got part 2 for free today, thanks! ⭐⭐

The full code can be found on github

Reflections

In part 1 the obvious optimisation is to break from the loop when we find either n1 or n2. This is because we can reach the final answer with just a single of these values.

However, even with that optimisation the current code is still a brute force technique. So, how can we improve on that? Maybe, but it’s Christmas day, so we won’t bother.

Happy Christmas and thanks for much for following!

. . . .

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Back to my advent calendar

Comments

Back to all posts