Day 13: Shuttle Search

Functions:

next_departure(bus_id, min_time)	Compute the next departure of bus_id leaving earliest at min_time.
find_departure(start_time, bus_ids)	Find the earliest bus to catch after start_time.
parse_input(lines)	Parse the input into (earliest departure time, bus IDs).
main()	Execute the main routine.

next_departure(bus_id: int, min_time: int) → int

Compute the next departure of bus_id leaving earliest at min_time.

Requires

• bus_id > 0

• min_time >= 0

Ensures

• min_time == 0 ⇒ result == 0

  (All buses leave at time zero.)

• result < min_time + bus_id

• result >= min_time

find_departure(start_time: int, bus_ids: Set[int]) → Tuple[int, int]

Find the earliest bus to catch after start_time.

Requires

• all(i > 0 for i in bus_ids)

• len(bus_ids) > 0

• start_time >= 0

Ensures

• result[0] % result[1] == 0

  (Departure time matches at least one bus.)

• result[0] >= start_time

parse_input(lines: Lines) → Tuple[int, Set[int]]

Parse the input into (earliest departure time, bus IDs).

Requires

• len(lines) == 2
  and re.match(r"\d+", lines[0])
  and re.match(r"(\d+|x)(,(\d+|x))*", lines[1])
  

• len(lines) == 2

main() → None

Execute the main routine.