# Advent Of Code Day 13: This Is Why I'm Not A Math Major

For Day 13, the puzzle involves bus departure times. Given input like this:

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

The first line is your arrival time, and the second line is the list of buses currently in service. Each bus departs at times that are a multiple of its ID; bus 5 departs at timestamp 0, 5, 10, etc. The first part of the puzzle asks for the earliest bus you could depart on. This was trivial to solve:

```
min_wait = None
min_bus = None
for bus in times:
if not np.isnan(bus):
departure = bus
while departure < arrival:
departure += bus
wait = departure - arrival
if min_wait is None or min_wait > wait:
min_wait = wait
min_bus = bus
p1 = int(min_wait * min_bus)
```

The second part took me a long time. The puzzle asked for a very particular set of departure times. Given an input string such as the above, the answer to the puzzle requires finding a timestamp such that the buses depart exactly one minute apart form each other, according to their place in the departure schdule line. From the puzzle:

```
7,13,x,x,59,x,31,19
An x in the schedule means there are no constraints on what bus IDs
must depart at that time.
This means you are looking for the earliest timestamp (called t) such
that:
Bus ID 7 departs at timestamp t.
Bus ID 13 departs one minute after timestamp t.
There are no requirements or restrictions on departures at two or
three minutes after timestamp t.
Bus ID 59 departs four minutes after timestamp t.
There are no requirements or restrictions on departures at five
minutes after timestamp t.
Bus ID 31 departs six minutes after timestamp t.
Bus ID 19 departs seven minutes after timestamp t.
```

This confused me for a while, given the huge search space, until I found a suggestion on the subreddit that the Chinese Remainder Theorem would be of use here. I am not a number theorist, I leave the deep math to my sister. I read over the information on the Wikipedia page until I felt like I could implement the direct construction solution described there. Quoting from Wikipedia:

“Let $$N_{i}=N/n_{i}$$ be the product of all moduli but one. As the
$$n_{i}$$ are pairwise coprime, $$N_{i}$$ and $$n_{i}$$ are
coprime. Thus Bézout’s identity applies, and there exist integers
$$M_{i}$$ and $$m_{i}$$ such that $$M_{i}N_{i}+m_{i}n_{i}=1$$. A
solution of the system of congruences is $$x=\sum
*{i=1}^{k}a*{i}M_{i}N_{i}$$. In fact, as $$N_{j}$$ is a multiple of
$$n_{i}$$ for $$i\neq j$$ we have $$x\equiv a_{i}M_{i}N_{i}\equiv
a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}}$$, for every $$i$$.”

The last part was very familiar to me, as that is a statement of modular congruence. Which is a solution I have programmed quite a few times for classes and programming challenges:

```
def euclidx(a, b):
if a == 0:
return 0
if b % a == 0:
return 1
return b - euclidx(b % a, a) * b // a
```

With this implemented, the solution became:

```
a = np.where(~np.isnan(times))[0]
n = times[a].astype(np.ulonglong)
N = n.prod()
x = np.sum(
[a[i] * (N // n[i]) * euclidx(N // n[i], n[i]) for i in np.arange(n.shape[0])]
)
p2 = int(N - x % N)
```

So, not very visualizable, but a very interesting trip into number theory!