# [Day 13](https://adventofcode.com/2020/day/13): Shuttle Search


```python
with open("../data/13.txt", "r") as f:
    t0, times = (l.strip() for l in f.readlines())
    
t0 = int(t0)
times = times.split(",")
times = [(o, int(p)) for o, p in enumerate(times) if p != "x"]
offsets, periods = zip(*times)
```

## Part 1


```python
wait, period = min(zip((-t0 % p for p in periods), periods))
assert 2092 == wait * period
```

## Part 2

The earliest timestamp ($t$) satisfies the system of congruences
$$
\eqalign{
t+T_0&\equiv0\pmod{P_0},\cr
t+T_1&\equiv0\pmod{P_1},\cr
&\dots\cr}
$$
where $T_n$, $P_n$ are the offsets and periods. The [Chinese Remainder Theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) yields a solution.


```python
from sympy import gcd
from sympy.ntheory.modular import crt
from itertools import combinations

# Verify that we can apply the Chinese Remainder Theorem
for m, n in combinations(periods, 2):
    assert gcd(m, n) == 1

timestamp, _ = crt(periods, (-o for o in offsets))
assert 702970661767766 == int(timestamp)
```

6f70e4cfbfc0f90f2e5e477f5e63c1c5d639e555
ipynb
Jupyter Notebook
solutions/13.ipynb
egnha/AoC-2020
bf52430e59ff4a6346c65dea41fcb663b5c76036
MIT
solutions/13.ipynb
egnha/AoC-2020
bf52430e59ff4a6346c65dea41fcb663b5c76036
MIT
solutions/13.ipynb
egnha/AoC-2020
bf52430e59ff4a6346c65dea41fcb663b5c76036
MIT
Qwen/Qwen-72B
1. YES
2. YES