Day 25: Combo Breaker

Puzzle Description

Advent of Code 2020, Day 25

Full Solution Source

My Solution for 2020, Day 25

Solution Summary

1. Parse input into two Longs (order doesn't matter)
2. Calculate loop size for one value
3. Use loop size and key of other value to get encryption key

Solution

Alright, first let's get our input parsed:

def parse(str: String): (Long, Long) =
  val Array(card, door) =
    str.linesIterator.map(_.toLong).toArray: @unchecked
  (card, door)

Ok, to actually solve this, we'll need to know some things about our situation -

20201227 is a prime number. When doing modular arithmetic with a prime divisor, we get some extra properties.

The key property we get is multiplicative inverse. This means in a $modn$ system, foreach number $a$ in 1 until n, there is a number $u$ where $au=1$ This effectively gives us divison, which is the exact operation we need to easily reverse this encryption procedure. Divison by any $a$ is equivilant to multiplying by its $u$.

Of course it's expensive to calculate all of these for a rather high prime number, but thankfully we only need one inverse: the inverse of 7. Let's calculate that now:

def part1(input: (Long, Long)): Long =
  val (card, door) = input

  val inverseSeven = (0 until 20201227).find(it => ((7 * it) % 20201227) == 1)

Then, to find the loop size, we just keep dividing by 7 until our initial value is 1, and count the steps it took. I used Monad[Id].tailRecM, which is a shortcut for this recursive tailrec function:

@tailrec def tailRec[A, B](a: A)(f: A => Either[A, B]): B =
  f(a) match
    case Left(a1) => tailRec(a1)(f)
    case Right(b) => b

Basically, we keep going until we return a Right. This works for all monads, and the Id type is just type Id[A] = A, but that's enough for Monad (and a lot of other weird instances but that's neither here nor there)

Let's add this to our part1 function:

  val doorLoopSize =
    Monad[Id].tailRecM((door, 0)): (v, n) =>
      if v == 1 then Right(n)
      else
        val newV = (v * inverseSeven) % 20201227L
        Left((newV, n + 1))

We know the loop size of the door AND the card's public ID, which is enough to complete our puzzle. Let's first add a transform function:

def transform(subject: Long, loopSize: Int): Long =
  def transformStep(n: Long): Long = (n * subject) % 20201227L
  transformStep.repeated(loopSize)(1L)

This is a BIT overkill but I really wanted to avoid using while here.

Then let's append the transform to our part1 function:

  transform(card, doorLoopSize)

And we're done! That's all that's needed, and it's rather fast too!

Final code

def parse(str: String): (Long, Long) =
  val Array(card, door) =
    str.linesIterator.map(_.toLong).toArray: @unchecked
  (card, door)

def transform(subject: Long, loopSize: Int): Long =
  def transformStep(n: Long): Long = (n * subject) % 20201227L
  transformStep.repeated(loopSize)(1L)

def part1(input: (Long, Long)): Long =
  val (card, door) = input

  val inverseSeven = (0 until 20201227).find(it => ((7 * it) % 20201227) == 1)

  val doorLoopSize =
    Monad[Id].tailRecM((door, 0)): (v, n) =>
      if v == 1 then Right(n)
      else
        val newV = (v * inverseSeven) % 20201227L
        Left((newV, n + 1))

  transform(card, doorLoopSize)

Benchmark

Part 1

Run it in the browser!