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 n
th 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.