コード2020 -日13の出現

https://adventofcode.com/2020/day/13 (「シャトル検索」)
第1部では、最小時間以上の最小倍数のバス番号を探す必要がある.
これについて考える1つの方法は、各バスが最短時間前の分までに実行したルートの完全な回路の数を見ることです.これを知って、我々は次の出発時刻を決定することができます、そして、これは最小の時間に等しいかより大きい最初の出発です.
最小時間がmin_time バス番号はbus_no そして、min_time - 1 は(min_time - 1) // bus_no . 次の出発時刻は次の回路の終了時刻となり、前回の結果(もう1つの回路)に1を加え、バス番号で乗算します.((min_time - 1) // bus_no + 1) * bus_no .
使用することに注意min_time - 1 ここでは我々の可能性を処理するmin_time それ自体はバスの1つの次の可能な出発時間です.
Pythonでは次のようになります.

def part1():
    # Puzzle input is sufficiently small there's no need to 
    # read in from a file.
    min_time = 1003681
    bus_nos = [int(n) for n in '23,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,431,x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,x,x,x,x,x,x,x,x,409,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29'.split(',') if n != 'x']
    # Map each bus number to a pair of (bus_no, next_departure)
    # and then find the pair with the minimum next_departure 
    # value.
    (first_bus, departure_time) = min(((bus_no, ((min_time - 1) // bus_no + 1) * bus_no) for bus_no in bus_nos), key=lambda x: x[1])
    # Calculate the waiting time and multiply by the bus number.
    return (departure_time - min_time) * first_bus

パート2は他の道をやりたいと思っています.特定のタイムスタンプの周りのバスの出発を探す代わりに、特定のパターンを持っているタイムスタンプを見つける必要があります.
最初に正確に何が求められているかを理解しましょうt インデックスのバスのようなi リストには出発がありますt + i . つまり、もし[(i_0, b_0), (i_1, b_1), ..., (i_n, b_n)] インデックスとバス番号のペアのリストですn バスを探しているt 以下のようにします:

(t + i_n) % b_n = 0  for all n

今最も簡単なアプローチはt = 0 そして、それぞれt かどうかを調べる(t + i_n) % b_n = 0 すべてのためにn . しかし、これはコードパズルの出現の一部であることは非常に可能性がありますこれは賢明な時間で完了しないだろう!
このような式のシステムを解決するのにはるかに速い方法があることがわかります

t % b_n = r_n  for all n

元の式は以下の通りです.

((t % b_n) + (i_n % b_n)) % b_n = 0  for all n

これから我々はi_n % b_n 右側には、マイナスにする.しかし、我々はモジュロb_n 我々は無料で追加することですb_n 物事を積極的に保つ

t % b_n = (b_n - i_n % b_n) % b_n  for all n

だから我々はr_n = (b_n - i_n % b_n) % b_n .
パズルからの例は、次のとおりです(i_n, b_n) インデックス/バス番号ペア:

[(0, 7), (1, 13), (4, 59), (6, 31), (7, 19)]

計算r_n それぞれのペアのために、我々は以下を得ます(r_n, b_n) 対

[(0, 7), (12, 13), (55, 59), (25, 31), (12, 19)]

この例では、したがって、私たちは価値を探していますt 以下のようにします:

t % 7 = 0
t % 13 = 12
t % 59 = 55
t % 31 = 25
t % 19 = 12

今何をしますか.
最初のことは、例のすべてのバス番号が素数であることです.簡単なチェックは、これもパズルの入力の場合であることを示しており、これは私たちがChinese Remainder Theorem 解決策を見つけるために!
我々は最大のバス番号で起動し、我々の方法を動作する場合、答えに到達する最速ですので、方程式を再注文することができます:

t % 59 = 55
t % 31 = 25
t % 19 = 12
t % 13 = 12
t % 7 = 0

まず最初に、リストの最初の2つのバスのために働く解決策を見つけましょう.t = 55 明らかに第1の方程式を満たすでしょうt = 55 + 59 , t = 55 + 59 * 2 59を追加し続けるならば、我々は最終的にt ここで、我々はまた、第二の方程式が保持されることがわかります.これを呼びましょうt_2 , それで

t_2 % 59 = 55
t_2 % 31 = 25

今、巧妙なトリック来る:私たちが追加された場合59 * 31 to t_2 私たちは別の価値を得るt これは、これらの2つの方程式を満たす:私たちは59の合計数を追加しましたので、59によって分割するときに残りが変更されませんが、私たちはまた、31によって分割するときに残りの部分は、31 sのすべての番号を追加しましたので、どちらも変更されません.実際には、任意の複数の59 * 31 我々は物事を変えることなく好きだ.これは私たちに価値のために探索を続ける方法を与えますt 私たちが方程式1と2を壊さないことを確認している間、それは第3の方程式を満たします.付け加えてから言いましょう59 * 31 to t_2 十分な数の我々は、値の値になるt これは最初の3つの式で動作しますt_3 .
一歩後退するならば、上記のプロセスが最初の2つの方程式を解決するときに、私たちがどうしたかを正確に見ることができます.

t % (59 * 31) = t_2
t % 19 = 12

我々は今価値を探すために同じことをすることができますt_4 それは4から始まる4番目の式を満たすでしょうt_3 そして繰り返し続ける59 * 31 * 19 . これは、1対の方程式を解くことと等価です.

t % (59 * 31 * 19) = t_3
t % 13 = 12

最後に我々は繰り返し追加59 * 31 * 19 * 13 to t_4 値を見つけるt_5 それは第5の方程式を満足させます.

t % (59 * 31 * 19 * 13) = t_4
t % 7 = 0

したがって、フォームの方程式のペアを解く関数が必要です.

x % p_1 = a_1
x % p_2 = a_2

次のようになります.

def solve(p_1, a_1, p_2, a_2):
    x = a_1
    while x % p_2 != a_2:
        x += p_1
    return x

さて、パート2を解決するために、これらの手順に従ってください.

def part2():
    # Get the bus numbers from the input along with the 
    # corresponding indices.
    buses = [(i, int(n)) for (i, n) in enumerate('23,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,431,x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,x,x,x,x,x,x,x,x,409,x,x,x,x,x,x,x,x,x,41,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,29'.split(',')) if n != 'x']

    # Figure out for each bus the remainder t must have 
    # when divided by the bus number.
    buses = [((b - i % b) % b, b) for (i, b) in buses]

    # Sort in decreasing order of bus number.
    buses.sort(key=lambda bus: -bus[1])

    # Starting with the first two equations, repeatedly 
    # solve to generate a new equation t % p = a where p is the
    # product of the moduli used so far and a is the result of 
    # solving the previous pair of equations.
    (a, p) = buses[0]
    for (remainder, bus_no) in buses[1:]:
        a = solve(p, a, bus_no, remainder)
        p *= bus_no

    return a

もともとこのパズルをやったとき、私は完全に中国の残りの定理について忘れていたでしょう.しかし、バス番号がすべてのプライムであるという事実は何かが上がったことを示しました.私は、モジュロ算術の中にいくつかのものがあったことを知っていました.そして、使用中の様々なモジュロが共素性であるならば(すなわち、1以外の共通の要因を共有しません)、Wikipediaを通しての速いRummageは定理を指し示しました.