Advent of Code 2015 - Day 14

Day 14: Reindeer Olympics

Useful Links

‹›

Concepts and Packages Demonstrated

regex Dataclass Lambda Function Defaultdict

Problem Intro
Part 1
Part 2
Results

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 a list of Reindeer objects.
We use max() to get the reindeer with the largest distance_at_t(TIME), by passing in this method as a lambda function to the max() 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 defaultdict to store the running score for each reindeer. Recall that by using a defaultdict with a value type of int, 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.

‹›

Learning Python with Advent of Code Walkthroughs