🎄

Advent of Code 2020 day13

5 min read

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) * 59295 が解になる。

問題の通り、すべての有効な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_00 から順番に試して求めてみると

\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 = 770番目と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} + 1664397番目も満たすものは 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}ad が互いに素であるとして 高々 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
    }

Discussion

ログインするとコメントできます