The holidays are a time for festive activities and time with family. However, thanks to advent of code, you can now get in the spirit whilst still sitting at home on your laptop! This website reveals a new coding challenge each day from the 1st to the 25th of December, and so far it is much more enjoyable than the small chocolates in the typical advent calendar. When I found out about this on hackernews, I decided I’d give it a shot since it seemed fun and I stopped doing my usual interview practice since I started working. I don’t know if I’ll quite keep pace, but I’ll consider myself satisfied if I complete it before the end of the year. If you are curious, I am hosting my solutions in a gitlab repository and am writing them all in JavaScript.

The most interesting challenge that I’ve found so far is on Day 4. According to the provided description, you are trapped in a supply closet and are wanting to enter a lab across the hall. The only issue, however, is that there is always a guard on duty. Fortunately, someone previously trapped in the same closet made notes each night for an hour after midnight with valuable data, including when a new guard takes over and when the current guard falls asleep or wakes up. For reference, take a look at some example input:

[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

Given this input, which is not necessarily in order, you must find the guard that spends the most total minutes asleep and what time they are asleep the most.

The first step to solving this is to simply retrieve the input from the file. I kept things simple by copying the given input on the site into a local text file and then loading it into a variable.

const fs = require('fs')
const path = require('path')
const file = fs.readFileSync(path.resolve(__dirname, 'input', 'day4.txt'))

const lines = file.toString().split('\n')

Now, it is important to sort the data. Although it may be doable without sorting first, the logic would be much more complex. I accomplished this in JavaScript by using the built in sort function on arrays and using a regular expression to extract the date data.

const timePattern = /^\[(\d{4})-(\d{2})-(\d{2})\s(\d{2}):(\d{2})\]/
const sortedLines = lines.slice().sort((a, b) => {
    const resultsA = timePattern.exec(a)
    const resultsB = timePattern.exec(b)

    const dateA = new Date(
        resultsA[1],
        resultsA[2] - 1,
        resultsA[3],
        resultsA[4],
        resultsA[5]
    )
    const dateB = new Date(
        resultsB[1],
        resultsB[2] - 1,
        resultsB[3],
        resultsB[4],
        resultsB[5]
    )

    return dateA - dateB
})

Once onto the actual processing, it starts to get hairy. For my approach, I used an object to track the data throughout iterations. The structure of this object is a map, where a guard id points to an object containing the total minutes spent asleep for that guard and an array containing the number of total minutes they spent asleep at each minute.

To process the data, simply iterate through each timestamped event. If it contains a # followed by digits, then a new guard is on duty and is awake. If there is no new guard, then the guard is either waking up or falling asleep, whichever is opposite of their last known entry. When a guard is waking up, increment the previous period of time since they must have been asleep. Also, when incrementing the time asleep, keep track of what guard has the most total time asleep in a variable.

Once all the data is collected, loop through the array containing the minutes spent asleep at each minute for the guard with the most total time asleep to find at which minute they are most vulnerable. For your final answer, multiply the id of the chosen guard and the minute that they are asleep the most.

const part1 = (lines) => {
    const idPattern = /#(\d+)/

    const idToMinuteCount = {}
    let id = null
    let awake = true
    let lastAwakeMinute = 0
    let sleepiestGuard = null

    const incrementRange = (id, start, end) => {
        if (!id) return

        if (!idToMinuteCount[id]) {
            idToMinuteCount[id] = {
                sum: 0,
                counts: new Array()
            }
        }

        for (let i = start; i < end; i++) {
            idToMinuteCount[id].sum = idToMinuteCount[id].sum + 1
            
            if (idToMinuteCount[id].counts[i]) {
                idToMinuteCount[id].counts[i] = idToMinuteCount[id].counts[i] + 1
            }
            else {
                idToMinuteCount[id].counts[i] = 1
            }
        }

        if (sleepiestGuard === null) sleepiestGuard = id
        if (idToMinuteCount[id].sum > idToMinuteCount[sleepiestGuard].sum) sleepiestGuard = id
    }

    for (const i in lines) {
        const line = lines[i]
        const idResults = idPattern.exec(line)
        const timeResults = timePattern.exec(line)
        const minute = parseInt(timeResults[5])

        if (idResults) {
            // end of previous guard duty
            id = parseInt(idResults[1])
            awake = true
        }
        else if (awake) {
            // falling asleep
            lastAwakeMinute = minute
            awake = false
        }
        else {
            // waking up
            incrementRange(id, lastAwakeMinute, minute)
            awake = true
        }
    }

    let sleepiestMinute = null
    for (const i in idToMinuteCount[sleepiestGuard].counts) {
        const count = idToMinuteCount[sleepiestGuard].counts[i]

        if (sleepiestMinute === null) sleepiestMinute = i
        if (count > idToMinuteCount[sleepiestGuard].counts[sleepiestMinute]) {
            sleepiestMinute = i
        }
    }

    return sleepiestMinute * sleepiestGuard
}

This solution is O(nlog(n)) time, where the sorting is the bottleneck. Since the actual processing is done in one iteration over all the data, any significant optimizations would involve simply processing it out of order.

That’s enough writing for now, time to catch up! Currently got another four days worth to work on today.