🎄

Advent of Code 2020 day25

2021/01/12に公開

Rust

adventofcode

tech

https://adventofcode.com/2020/day/25

part1

5764801
17807724

のような入力が与えられる。カードの公開鍵とドアの公開鍵をそれぞれ表している。
カードとドアの間でそれぞれ秘密のloop sizeを使ってhandshakeが行われる。

まずsubject numberをtransformするという手続きがあり、これは値を1から始めて「subject numberを掛けた値を20201227で割ったもの」に変換する。これをloop size回繰り返す。

カードはsubject number 7でカードのloop size回のtransformを行う。これがカードの公開鍵の値となる。
ドアも同様にsubject number 7でドアのloop size回のtransformを行う。これがドアの公開鍵の値となる。
カードはドアの公開鍵をsubject numberとしてカードのloop size回のtransformを行う。これが求める暗号キーになる。
ドアも同様にカードの公開鍵をsubject numberとしてドアのloop size回のtransformを行う。これがカードで計算した暗号キーと同じ値になる。

上の例でいうと、最初のsubject number 7を8回transformすることで 5764801が求められる、のでカードのloop sizeは8、同様に考えてドアのloop sizeは11ということが分かる。

>>> (7 ** 8) % 20201227
5764801
>>> (7 ** 11) % 20201227
17807724

なのでドアの公開鍵 17807724 をカードのloop size 8でtransformしていくことで暗号キー 14897079が求められる。同様にしてカードの公開鍵 5764801 をドアのloop size 11でtransformしても同じ値が求められる。

>>> (17807724 ** 8) % 20201227
14897079
>>> (5764801 ** 11) % 20201227
14897079

そういうものなの…？
ともかく、このようにして求められる暗号キーを算出せよ、という問題。

brute forceで最初のsubject number 7を繰り返しtransformしていくことで両公開鍵になるためのloop sizeを求められるので、それを求めたらあとはどちらかの公開鍵を使ってもう片方のloop size回だけtransformしてやれば良い。

struct Solution {
    card_key: u64,
    door_key: u64,
}

const DIV: u64 = 20_201_227;

impl Solution {
    fn new(inputs: Vec<u64>) -> Self {
        Self {
            card_key: inputs[0],
            door_key: inputs[1],
        }
    }
    fn solve_1(&self) -> u64 {
        fn loop_size(target: u64) -> Option<usize> {
            let mut value = 1;
            for i in 0..DIV as usize {
                if value == target {
                    return Some(i);
                }
                value = (value * 7) % DIV;
            }
            None
        }
        if let Some(card_loop_size) = loop_size(self.card_key) {
            if let Some(door_loop_size) = loop_size(self.door_key) {
                if card_loop_size != door_loop_size {
                    return (0..card_loop_size).fold(1, |acc, _| (acc * self.door_key) % DIV);
                }
            }
        }
        unreachable!()
    }
}

part2

ここまでで49個(ここまでの24日×2つずつ+この日のpart1)の星を集めていれば、自動的にpart2もcomplete、となる。

50個の星がすべて集まった、おめでとう！

part1

part2

Discussion