Advent of Code 2018 - Day 4

Day 4: Repose Record

Useful Links

‹›

• 2018 Main Page
• My solution code

Concepts and Packages Demonstrated

Regular ExpressionsClassesDefaultdictLambda Functionssorted

Problem Intro

We’ve sneaked into a supply closet near the prototype suit manufacturing lab. We find a record of guard shifts and their sleeping habits. We need to analyze these records to find the best time to sneak into the lab.

The input consists of timestamped log entries, which look like this:

[1518-11-01 00:00] Guard #10 begins shift
[1518-11-01 00:05] falls asleep
[1518-11-01 00:25] wakes up
[1518-11-01 00:30] falls asleep
[1518-11-01 00:55] wakes up
[1518-11-01 23:58] Guard #99 begins shift
[1518-11-02 00:40] falls asleep
[1518-11-02 00:50] wakes up

The records are not necessarily in chronological order, so we’ll need to sort them first. We need to track when each guard is on duty, when they fall asleep, and when they wake up.

Part 1

Find the guard that has the most minutes asleep. What minute does that guard spend asleep the most?

We need to identify which guard sleeps the most in total, and then for that specific guard, identify which minute (0-59) they are most frequently asleep during. The answer is the Guard ID multiplied by that minute.

Setup

import logging
import re
import sys
import textwrap
from collections import defaultdict

import dazbo_commons as dc 
import aoc_common.aoc_commons as ac 

YEAR = 2018
DAY = 4

We’re using re for parsing the input lines, and defaultdict to store our guards.

The Guard Class

To keep things organized, I’ve created a Guard class. This encapsulates the data and behavior for a single guard.

class Guard:
    def __init__(self, guard_id):
        self.guard_id = guard_id
        self.sleep_times = [0]*60

    def add_sleep_time(self, start, end):
        """ Add sleep time to the guard's sleep times """
        for i in range(start, end):
            self.sleep_times[i] += 1

    def get_total_sleep(self) -> int:
        """ Return total sleep time in minutes """
        return sum(self.sleep_times)

    def get_sleep_freq_for_minute(self, minute) -> int:
        """ Return the frequency of sleep for a given minute """
        return self.sleep_times[minute]
    
    def get_most_frequent_minute(self) -> int:
        """ Return the minute that the guard was most frequently asleep """
        return self.sleep_times.index(max(self.sleep_times))

• __init__: Initializes a guard with their ID. It also creates a list sleep_times of size 60, initialized to 0. This list represents the 60 minutes in the midnight hour (00:00 to 00:59). Index i stores the number of times the guard was asleep at minute i.
• add_sleep_time(start, end): Takes a start minute (inclusive) and end minute (exclusive). It iterates through this range and increments the counter in sleep_times for each minute.
• get_total_sleep(): Returns the total number of minutes the guard has slept, by summing up the sleep_times list.
• get_sleep_freq_for_minute(minute): Returns how many times the guard was asleep at a specific minute.
• get_most_frequent_minute(): Finds the minute (index) where the guard was asleep the most often. It does this by finding the maximum value in sleep_times and then finding the index of that value.

Processing the Data

Before we can analyze the guards, we need to parse the input data.

matcher = re.compile(r"Guard #(\d+)")

def process_data(data):
    sorted_data = sorted(data)
    guards = {}

    for line in sorted_data:
        if "Guard" in line:
            asleep_start = None
            guard_id = int(matcher.search(line).group(1))
            if guard_id not in guards:
                guards[guard_id] = Guard(guard_id)
        else:
            if "asleep" in line:
                asleep_start = int(line[15:17])
            else:
                assert asleep_start is not None
                asleep_end = int(line[15:17])
                guards[guard_id].add_sleep_time(asleep_start, asleep_end)
    
    return guards

1. Sorting: The input data is unsorted. Conveniently, the timestamp format [YYYY-MM-DD HH:MM] sorts correctly using a standard lexicographical string sort. So, sorted(data) puts everything in chronological order.
2. Parsing: We iterate through the sorted lines.
   • If the line contains “Guard”, it means a new shift is starting. We extract the guard_id using a regular expression. If we haven’t seen this guard before, we create a new Guard object and store it in our guards dictionary.
   • If the line contains “asleep”, we record the minute they fell asleep. The minute is always at characters 15-17 in the line (e.g., [1518-11-01 00:05]).
   • If the line contains “wakes up”, we take the minute they woke up. We then call add_sleep_time on the current guard_id to record the sleep duration from asleep_start to asleep_end.

Solving Part 1

Now we have our data processed, we can solve Part 1.

def part1(data):
    guards = process_data(data)
    
    sleepiest_guard = max(guards.values(), key=lambda x: x.get_total_sleep())
    return sleepiest_guard.guard_id * sleepiest_guard.get_most_frequent_minute()

Here, we use the max() function to find the guard who slept the most. But max() needs to know how to compare guards. We provide a key argument, which is a function that returns the value to compare.

I’m using a Lambda function here: lambda x: x.get_total_sleep(). A lambda function is a small, anonymous function. In this case, it takes an argument x (which will be a Guard object) and returns the result of x.get_total_sleep(). So max() will call this method on every guard and return the one with the highest total sleep.

Once we have the sleepiest_guard, we multiply their ID by their most frequent sleep minute.

Part 2

Of all guards, which guard is most frequently asleep on the same minute?

For Part 2, we need to look at every guard and every minute, and find the single guard-minute combination with the highest frequency.

def part2(data):
    guards = process_data(data)
    sleepiest_minute = max(guards.values(), 
                           key=lambda x: x.get_sleep_freq_for_minute(x.get_most_frequent_minute()))
    return sleepiest_minute.guard_id * sleepiest_minute.get_most_frequent_minute()

Again, we use max() with a lambda function. This time, the key is a bit more complex: lambda x: x.get_sleep_freq_for_minute(x.get_most_frequent_minute())

For each guard x:

1. x.get_most_frequent_minute() finds the minute they slept the most.
2. x.get_sleep_freq_for_minute(...) gets the count of how many times they slept on that specific minute.

So max() finds the guard who has the highest frequency of sleep on their most frequent minute.

Results

The output looks like this:

Part 1 soln=39698
Part 2 soln=14920
Execution time: 0.017 seconds

‹›