Chapter 14

Day 13: Shuttle Search

sugyan
sugyan
2021.03.09に更新

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 以降では ID 59 のバスが 944 に到着するのが最も早いので (944 - 939) * 59295 が解となる。

考え方

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

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 を求める手続きで書いていけば良い。

解答例

from itertools import count
from typing import List


class Solution:
    def __init__(self, inputs: List[str]) -> None:
        self.lines = inputs

    def part_1(self) -> int:
        timestamp = int(self.lines[0])

        # timestamp以降に待つ時間を求める
        def wait(id: int) -> int:
            return id * (timestamp // id + 1) - timestamp

        # 各IDに対して最短の待ち時間になるIDを求める
        min_id = min([int(x) for x in self.lines[1].split(",") if x != "x"], key=wait)
        return min_id * wait(min_id)

    def part_2(self) -> int:
        a, b = 1, 0
        # `a * m + b` で表したときの次の `a` と `b` を順番に求めていく
        for i, id_str in enumerate(self.lines[1].split(",")):
            if id_str != "x":
                bus_id = int(id_str)
                m = next(filter(lambda m: (a * m + b + i) % bus_id == 0, count()))
                a, b = a * bus_id, a * m + b
        return b