# Advent of Code Day 13 with Sympy¶

```
import numpy as np
from sympy.solvers.diophantine import diophantine
from sympy import N
import math
from sympy import reduce_inequalities
from sympy import symbols
```

# Part 1¶

The idea is quite simple.

A bus arrives every $n$ minutes, where $n$ is the bus id. So the longest wel will have to wait a given bus is $n$ minutes.

$timestamp \ \% \ n$ gives us the time since the last multiple of n.

```
# Input from the challenge
inp = """1007153
29,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,37,x,x,x,x,x,433,x,x,x,x,x,x,x,x,x,x,x,x,13,17,x,x,x,x,19,x,x,x,23,x,x,x,x,x,x,x,977,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,x,41"""
```

```
depature_ts = int(inp.split('\n')[0])
bus_ids = [int(t) for t in inp.split('\n')[1].split(',') if t != 'x']
```

```
bus_ids
```

```
waiting_time_for_bus = []
for t in bus_ids:
r = depature_ts % t
to_wait = t-r
waiting_time_for_bus.append(to_wait)
```

```
idx = np.argmin(waiting_time_for_bus)
```

```
waiting_time_for_bus[idx]*bus_ids[idx]
```

# Part 2¶

This one is much less straight forward.

Let's take the example, and pull out two parts. The bus ids, and the required offset in minutes from the first timestamp.

$ids = [7, 13, 59, 31, 19]$

$offsets = [ 0, 1, 4, 6, 7]$

This problem actually has a nice recursion; we can consider two buses, 7 and 13, with offset 1 for 13 as a single event. As per the previous example, just like bus 7 has a period of 7 minutes, the event "bus 13 arriving 1 minute after bus 7" has a period of $LCM(7, 13) = 7*13 = 91$.

So, the event "13 arrives 1 minute after 7 and 59 arrives 4 minutes after bus 7", is the same as a synthetic bus event that occurs at period 91 and a bus with period 59.

Lets write these as equations:

$x=7n_{1}$

$x+1=13n_{2}$

Rearranging to get x on the lhs and combining, we get:

$7n_{1} = 13n_{2}-1$

This is a linear diophantine equation. https://en.wikipedia.org/wiki/Diophantine_equation

We can use scipy to help us out.

```
n1, n2, t_0 = symbols(["n1", "n2", "t_0"], integer=True)
```

```
res = diophantine(7*n1 - 13*n2 + 1)
res
```

As its two unknowns in one equation, we have a free parameter, t_0, that the values of our terms are a function of. We can read each element of the result tuple to be the values of (n1, n2).

We want positive solutions, so we can use sympy's inequality functionality.

```
r = list(res)[0]
bounds = reduce_inequalities([r[0]>0, r[1]>0])
bounds
```

So we get the lower bound for t0 such that both n1 and n2 are positive. We can get this as a float, round it up to an int and compute n_1 with this value of t0.

```
lhs = float(bounds.lhs.evalf())
t = math.ceil(lhs)
# Now put this numerical value back into the symbolic equation
n_1 = r[0].subs({t_0:t})
n_1
```

Going back to the original equation, we can see this is the number of cycles for bus id 7. So the first timestamp we get 13 one minute after 7 is at timestamp 77, with a subsequent period of 91 minutes between these occuring.

Now let's do the next one.

We have a bus which arrives at timestamp $x = 77+91m_{1}$

and a bus $x+4 = 59m_{2}$.

$0 = 77+91m_{1} -59m_{2} + 4 $

Solving as per the last example:

```
m1, m2, t_0 = symbols(["m1", "m2", "t_0"], integer=True)
res = diophantine(91*m1 - 59*m2 + 81)
r = list(res)[0]
bounds = reduce_inequalities([r[0]>0, r[1]>0])
lhs = float(bounds.lhs.evalf())
t = math.ceil(lhs)
# Now put this numerical value back into the symbolic equation
m_1 = r[0].subs({t_0:t})
m_1
```

This first occurs at $77 + 91*3 = 350$, and happens with a period of lcm(91, 59) = 5369.

We could continue like this simply. Let's implement this in a slightly more generic way.

```
def get_first_occurance(i1, i2, offset):
"""As before, returns the number of iterations of bus i1,
and the number of minutes this corresponds to."""
res = diophantine(i1*n1 -i2*n2 + offset)
t_0 = symbols("t_0", integer=True)
for r in res:
red = reduce_inequalities([r[0]>0, r[1]>0])
lhs = float(red.lhs.evalf())
n_1 = math.ceil(lhs)
n_1 = r[0].subs({t_0:n_1})
return n_1, n_1*i1
def get_period(i1, i2):
"""Gets the period of two buses to return to a given state.
Dtype important to prevent overflow!"""
return np.lcm(i1, i2, dtype=np.uint64)
```

```
get_first_occurance(7, 13, 1)
```

One last detail, is that the offsets accumulate. Unlike the original problem, this one doesn't have each "synthetic bus" start at 0, and so we need to keep track of accumulated shift in starting state.

We'll define a 2 dimensional state, corresponding to the period and first occurance in minutes of the sequence we have already done.

```
def get_earliest_timestamp(bus_ids, offsets):
"""Take a list of bus ids and offsets.
Return the earliest timestamp this state occurs.
No error handling - assumes theres a solution that fits in a uint64!!
"""
state = (bus_ids[0], offsets[0])
bus_ids = bus_ids[1:]
offsets = offsets[1:]
for i in range(len(bus_ids)):
d = state[1]+offsets[i]
n_its, first_in_mins = get_first_occurance(state[0], bus_ids[i], d)
p = get_period(state[0], bus_ids[i])
state = (p, first_in_mins+state[1])
return state[1]
```

```
m = np.array([7, 13, 59, 31, 19])
o = np.array([ 0, 1, 4, 6, 7])
```

```
get_earliest_timestamp(m, o)
```

As per the example, this works, and much more quickly than brute force (if you ignore the hours of work to formulate it this way)!

```
%%timeit
get_earliest_timestamp(m, o)
```

```
def get_input_data(input_string):
l2 = input_string.split('\n')[1]
bus_ids, offsets = [], []
for i, token in enumerate(l2.split(',')):
if token != 'x':
bus_ids.append(int(token))
offsets.append(i)
return bus_ids, offsets
```

```
bus_ids, offsets = get_input_data(inp)
bus_ids, offsets
```

```
get_earliest_timestamp(bus_ids, offsets)
```

```
%%timeit
get_earliest_timestamp(bus_ids, offsets)
```