Advent of Code 2020 day13

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

part1

939
7,13,x,x,59,x,31,19

のような入力が与えられる。
1行目はバス乗り場への到着時間、2行目は各バスのID(=運行間隔)を示している。
part1ではxは無視してよく、それ以外の各IDのバスが0から開始しそのID時間の間隔で到着する。ID7のバスは 7, 14, 21, ... , 938, 945, ... の時間に、ID13のバスは 13, 26, 39, ..., 936, 949, ... の時間に来る。
基準の到着時間より後で最も早く到達するバスを求め、そのIDと待ち時間を掛けた値を求めよ、という問題。上の例でいうと 939以降では ID59のバスが944に到着するのが最も早いので (944 - 939) * 59 で 295 が解になる。

問題の通り、すべての有効なIDについて基準のtimestamp以降に現れる時間を算出して最小値を求めれば良い。
基準timestampまでいちいち足していては無駄なので、(timestamp % id != 0という前提で)(id * (timestamp / id + 1) - timestampで各IDの待ち時間を求められる。

struct Solution {
    inputs: Vec<String>,
}

impl Solution {
    fn new(inputs: Vec<String>) -> Self {
        Self { inputs }
    }
    fn solve_1(&self) -> i32 {
        let timestamp = self.inputs[0].parse::<i32>().unwrap();
        if let Some((minutes, id)) = self.inputs[1]
            .split(',')
            .filter_map(|s| s.parse::<i32>().ok())
            .map(|id| (id * (timestamp / id + 1) - timestamp, id))
            .min_by_key(|&e| e.0)
        {
            id * minutes
        } else {
            0
        }
    }
}

part2

今度は1行目の時間は無視で、2行目のバスIDたちだけを使う。「i番目のバスがある時刻よりi経過した時刻に到着する」という条件をすべてのiが満たす最初の時刻を求めよ、という問題。例の

7,13,x,x,59,x,31,19

で言うと、

• 0番目の、ID 7のバスが 時刻t + 0に到着
• 1番目の、ID 13のバスが 時刻t + 1に到着
• 2, 3番目は無視
• 4番目の、ID 59のバスが 時刻t + 4に到着
• 5番目は無視
• 6番目の、ID 31のバスが 時刻t + 6に到着
• 7番目の、ID 19のバスが 時刻t + 7に到着

をすべて満たす t を求める必要がある。

これをどうやって求めるか。

まず0番目を考えると、7ごとに到着するバスがtぴったりになるので $t\equiv{0}\pmod{7}$ と表せる。1番目は 13ごとに到着するものがt + 1になるので $t+1\equiv{0}\pmod{13}$ 、4番目は $t+4\equiv{0}\pmod{59}$ 、といった具合になる。これらをすべて満たす $t$ を求めるために以下のような合同方程式を解けると良い。

$$\begin{aligned} t + 0 &\equiv 0 \pmod{7} \\ t + 1 &\equiv 0 \pmod{13} \\ t + 4 &\equiv 0 \pmod{59} \\ t + 6 &\equiv 0 \pmod{31} \\ t + 7 &\equiv 0 \pmod{19} \\ \end{aligned}$$

簡単に0番目と1番目だけを満たすものを考えてみる。0番目は任意の整数 $m_{0}$ で $t= 7 m_{0}$ と表せるので、これを1番目に代入して $7 m_{0} + 1 \equiv{0} \pmod{13}$ となる。これを満たす $m_0$ を $0$ から順番に試して求めてみると

$$\begin{aligned} 7 * 0 + 1 &= 1 \equiv{1} \pmod{13} \\ 7 * 1 + 1 &= 8 \equiv{8} \pmod{13} \\ 7 * 2 + 1 &= 15 \equiv{2} \pmod{13} \\ 7 * 3 + 1 &= 22 \equiv{9} \pmod{13} \\ 7 * 4 + 1 &= 29 \equiv{3} \pmod{13} \\ 7 * 5 + 1 &= 36 \equiv{10} \pmod{13} \\ 7 * 6 + 1 &= 43 \equiv{4} \pmod{13} \\ 7 * 7 + 1 &= 50 \equiv{11} \pmod{13} \\ 7 * 8 + 1 &= 57 \equiv{5} \pmod{13} \\ 7 * 9 + 1 &= 64 \equiv{12} \pmod{13} \\ 7 * 10 + 1 &= 71 \equiv{6} \pmod{13} \\ 7 * 11 + 1 &= 78 \equiv{0} \pmod{13} \\ \end{aligned}$$

…と、 $m_0 = 11$の とき、つまり $t = 77$ で0番目と1番目を満たす。
そしてその後も等間隔で続くので、 $7 * 13 = 91$ の周期で繰り返すはず。よって 任意の整数 $m_{01}$ で $t = 91 m_{01} + 77$ と表せる。

>>> (77 + 0) % 7
0
>>> (77 + 1) % 13
0

続いて 4番目も満たすものを考えると、 $91 m_{01} + 77 + 4 \equiv{0} \pmod{59}$ となるので、これを満たすものを探す。

$$\begin{aligned} 91 * 0 + 77 + 4 &= 81 \equiv{22} \pmod{59} \\ 91 * 1 + 77 + 4 &= 172 \equiv{54} \pmod{59} \\ 91 * 2 + 77 + 4 &= 263 \equiv{27} \pmod{59} \\ 91 * 3 + 77 + 4 &= 354 \equiv{0} \pmod{59} \\ \end{aligned}$$

と、 $m_{01} = 3$ のとき、つまり $t = 350$ のときと そこから $7 * 13 * 59 = 5369$ 周期になるので $t = 5369 m_{014} + 350$ のときに 0, 1, 4 番目に関する条件を満たすことになる。

>>> (350 + 0) % 7
0
>>> (350 + 1) % 13
0
>>> (350 + 4) % 59
0

同様に求めていくことで 6番目も満たすものは $t = 70147 m_{0146} + 166439$ 、 7番目も満たすものは $t = 3162341 m_{01467} + 1068781$ と表すことが出来るようになる。このうち最初に現れるのが $m_{01467} = 0$ のときなので 1068781 が解となる。

>>> (1068781 + 0) % 7
0
>>> (1068781 + 1) % 13
0
>>> (1068781 + 4) % 59
0
>>> (1068781 + 6) % 31
0
>>> (1068781 + 7) % 19
0

Chinese remainder theorem 中国の剰余定理 がまさにこういう考え方、なのかな。

つまり順番に満たすべき $t$ を求めていけばよく、$t = a m_{i} + b$ と表現される場合、そこからさらに $t + c \equiv{0} \pmod {d}$ を満たす $t$ の条件を求めたい場合は $(a m_{i} + b) + c \equiv{0} \pmod {d}$ となる $m_{i}$ を求めてやれば、新しく $t = (a * d) m_{i+1} + (a m_{i} + b)$ で表せる。 $m_{i}$ は $a$ と $d$ が互いに素であるとして 高々 $d$ 回の試行で求められる。

最初は $a = 1, b = 0$ と考えて、次の $a, b$ を求める手続きで書いていけば良い。

    fn solve_2(&self) -> i64 {
        self.inputs[1]
            .split(',')
            .enumerate()
            .filter_map(|(i, s)| {
                if let Ok(id) = s.parse::<i64>() {
                    Some((i as i64, id))
                } else {
                    None
                }
            })
            .fold((1, 0), |(a, b), (i, id)| {
                let m = (0..).find(|m| (a * m + b + i) % id == 0).unwrap();
                (a * id, a * m + b)
            })
            .1
    }