Page Navigation
Problem Intro
It is the Reindeer Olympics. We’re told that our reindeer each have two attributes:
- The speed they fly at, and the duration they are able to maintain this speed.
- The period they must rest, before flying again.
So our input data looks something like this:
Comet can fly 14 km/s for 10 seconds, but then must rest for 127 seconds.
Dancer can fly 16 km/s for 11 seconds, but then must rest for 162 seconds.
Part 1
After exactly 2503 seconds, what distance has the winning reindeer travelled?
This is easy enough to do.
Given a number of seconds, we just need to determine how many of these seconds were spent travelling. We can do this by:
- Determining the total time for a given reindeer’s travel + rest cycle.
- Determining how many full cycles are complete in the given time.
- Multiple the number of complete cycles by the duration of each cycle that is spent travelling.
- Add on any remaining travel time from the last incomplete cycle.
I’ve decided to encapsulate all of this in a Reindeer class:
@dataclass
class Reindeer():
""" A reindeer flies at *speed* (km/s) for a given *duration* (s), then must *rest* (s). """
name: str
speed: int
duration: int
rest: int
def cycle_time(self) -> int:
return self.duration + self.rest
def distance_at_t(self, t: int) -> int:
"""Computes the distance travelled by this reindeer in the time given """
total_cycles = t // self.cycle_time()
remainder = t % self.cycle_time()
remainder_travelling = min(remainder, self.duration)
return ((self.duration*total_cycles) + remainder_travelling) * self.speed
Here I’ve made use of a dataclass, since we don’t need to modify any variables, once our reindeer has been instantiated.
Note how this Reindeer class knows how to work out how far it has travelled, given any number of seconds.
Now let’s process the input data, using regex:
def process_reindeer_data(data) -> list[Reindeer]:
"""Process input lines, and return a dict of reindeer.
Each line is of the format:
"Vixen can fly 8 km/s for 8 seconds, but then must rest for 53 seconds."
Returns: [list]: Reindeers
"""
reindeer_pattern = re.compile(r"^(\w+) can fly (\d+) km/s for (\d+) seconds, but then must rest for (\d+) seconds.")
reindeer_list = []
for line in data:
reindeer_name, speed, duration, rest = reindeer_pattern.findall(line)[0]
reindeer_list.append(Reindeer(reindeer_name, int(speed), int(duration), int(rest)))
return reindeer_list
Finally, let’s pull it together with a main() method:
def main():
# input_file = os.path.join(SCRIPT_DIR, SAMPLE_INPUT_FILE)
input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
data = f.read().splitlines()
reindeer_list = process_reindeer_data(data)
print("Part 1")
winner = max(reindeer_list, key=lambda x: x.distance_at_t(TIME))
print(f"Winning reindeer: {winner.name} with distance of {winner.distance_at_t(TIME)}.")
This is pretty simple:
- It uses our
process_reindeer_data()function to retrieve all the reindeer as alistofReindeerobjects. - We use
max()to get the reindeer with the largestdistance_at_t(TIME), by passing in this method as a lambda function to themax()function.
Easy!
Part 2
Now we’re told that every second that passes, the reindeer that is in the lead at that second gets a point.
After exactly 2503 seconds, how many points does the winning reindeer have?
To solve this:
- Do exactly as we did before, but instead of just getting the reindeer that has travelled furthest at
t=2503, we get the reindeer that has travelled furthest for each second until (and including)t=2503. - We use a
defaultdictto store the running score for each reindeer. Recall that by using adefaultdictwith a value type ofint, we don’t have to initialise the reindeer scores to 0. This happens implicitly, the first time we reference a reindeer.
All I need to do is add this code:
print("\nPart 2")
reindeer_points = defaultdict(int)
# we need to determine the winner for each second that has elapsed,
# and allocate a point to that reindeer
for i in range(1, TIME+1):
current_winner = max(reindeer_list, key=lambda x: x.distance_at_t(i))
reindeer_points[current_winner.name] += 1
print("Points:")
for a_reindeer in reindeer_points:
print(f"{a_reindeer}: {reindeer_points[a_reindeer]}")
winner_on_points = max(reindeer_points.items(), key=lambda x: x[1])[0]
print(f"Winning reindeer: {winner_on_points} who has {reindeer_points[winner_on_points]} points.")
Results
Here’s the complete solution:
from dataclasses import dataclass
import os
import re
import time
from collections import defaultdict
SCRIPT_DIR = os.path.dirname(__file__)
INPUT_FILE = "input/input.txt"
SAMPLE_INPUT_FILE = "input/sample_input.txt"
TIME = 2503
@dataclass
class Reindeer():
""" A reindeer flies at *speed* (km/s) for a given *duration* (s), then must *rest* (s). """
name: str
speed: int
duration: int
rest: int
def cycle_time(self) -> int:
return self.duration + self.rest
def distance_at_t(self, t: int) -> int:
"""Computes the distance travelled by this reindeer in the time given """
total_cycles = t // self.cycle_time()
remainder = t % self.cycle_time()
remainder_travelling = min(remainder, self.duration)
return ((self.duration*total_cycles) + remainder_travelling) * self.speed
def main():
# input_file = os.path.join(SCRIPT_DIR, SAMPLE_INPUT_FILE)
input_file = os.path.join(SCRIPT_DIR, INPUT_FILE)
with open(input_file, mode="rt") as f:
data = f.read().splitlines()
reindeer_list = process_reindeer_data(data)
print("Part 1")
winner = max(reindeer_list, key=lambda x: x.distance_at_t(TIME))
print(f"Winning reindeer: {winner.name} with distance of {winner.distance_at_t(TIME)}.")
print("\nPart 2")
reindeer_points = defaultdict(int)
# we need to determine the winner for each second that has elapsed,
# and allocate a point to that reindeer
for i in range(1, TIME+1):
current_winner = max(reindeer_list, key=lambda x: x.distance_at_t(i))
reindeer_points[current_winner.name] += 1
print("Points:")
for a_reindeer in reindeer_points:
print(f"{a_reindeer}: {reindeer_points[a_reindeer]}")
winner_on_points = max(reindeer_points.items(), key=lambda x: x[1])[0]
print(f"Winning reindeer: {winner_on_points} who has {reindeer_points[winner_on_points]} points.")
def process_reindeer_data(data) -> list[Reindeer]:
"""Process input lines, and return a dict of reindeer.
Each line is of the format:
"Vixen can fly 8 km/s for 8 seconds, but then must rest for 53 seconds."
Returns: [list]: Reindeers
"""
reindeer_pattern = re.compile(r"^(\w+) can fly (\d+) km/s for (\d+) seconds, but then must rest for (\d+) seconds.")
reindeer_list = []
for line in data:
reindeer_name, speed, duration, rest = reindeer_pattern.findall(line)[0]
reindeer_list.append(Reindeer(reindeer_name, int(speed), int(duration), int(rest)))
return reindeer_list
if __name__ == "__main__":
t1 = time.perf_counter()
main()
t2 = time.perf_counter()
print(f"\nExecution time: {t2 - t1:0.4f} seconds")
The results look like this:
Part 1
Winning reindeer: Donner with distance of 2655.
Part 2
Points:
Dancer: 1
Rudolph: 863
Cupid: 13
Blitzen: 5
Prancer: 147
Comet: 21
Vixen: 1059
Donner: 394
Winning reindeer: Vixen who has 1059 points.
Execution time: 0.0125 seconds
That’s pretty fast. I’m happy with that code.