2020-12-13 - Shuttle Search
(original .ipynb)
Day 13 puzzle input is a starting timestamp followed by a comma-separated list of integers representing a bus schedule (mine is here). Part 1 involves finding the first bus to arrive after the given timestamp. As soon as I saw this puzzle I knew Part 2 would be a pain in the arse, and it was. So we basically needed to find the first timestamp where the buses would arrive at a given order.
test_input_str = """939
7,13,x,x,59,x,31,19"""
puzzle_input_str = open("puzzle_input/day13.txt", "r").read()
def parse_bus(bus_str):
if bus_str != "x":
return int(bus_str)
return None
def part1(input_str):
input_lines = input_str.split("\n")
start_timestamp = int(input_lines[0])
bus_schedule = [parse_bus(b) for b in input_lines[1].split(",") if b != "x"]
buses = [b for b in bus_schedule if b]
current_timestamp = start_timestamp
while True:
for bus in buses:
if current_timestamp % bus == 0:
return bus * (current_timestamp - start_timestamp)
current_timestamp += 1
assert 295 == part1(test_input_str)
part1(puzzle_input_str)
161
# Ok this problem most likely involves https://en.wikipedia.org/wiki/Chinese_remainder_theorem
# and honestly I hate problems like these. The "solution" I have is inspired by someone who posted
# that they used their input to generate a set of equations and just bashed them into wolfram alpha
# which solved them for them so that's what we are going to do.
def generate_equation(offset, bus):
return f"(t + {offset}) mod {bus} = 0"
def part2(input_str):
input_lines = input_str.split("\n")
bus_schedule = [(i,parse_bus(b)) for i,b in enumerate(input_lines[1].split(","))]
equations = [generate_equation(offset,bus) for offset, bus in bus_schedule if bus]
return ",".join(equations)
part2(puzzle_input_str)
'(t + 0) mod 29 = 0,(t + 19) mod 41 = 0,(t + 29) mod 661 = 0,(t + 42) mod 13 = 0,(t + 43) mod 17 = 0,(t + 52) mod 23 = 0,(t + 60) mod 521 = 0,(t + 66) mod 37 = 0,(t + 79) mod 19 = 0'
The answer can be determined by following this link which produced the following:
t = 1463175673841141n + 213890632230818, n ∈ Z
This gives us a general formula for all timesteps (the nth solution) so if we want to find the first time all these buses arrive in the given order we plug n=0 in and get 213890632230818.
I enjoy the compsci puzzles but I truly despise the maths ones with a passion so I'm happy to give myself a "bye" on this.