Repose Record

Advent of Code 2018 Day 4

Task: Solve for X where...

Part 1

X = the ID of the guard I chose multiplied by the minute I chose

Part 2

X = the ID of the guard I chose multiplied by the minute I chose

Example input snippet

[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

It represents:

• Wall-written notes from a prior supply closet occupant
• ID and timestamp marking each guard's time spent asleep and awake each day for an hour at midnight

Part 1

1. Parse the notes
2. Generate the list of parsed notes with timestamps
3. Sort the notes by date
4. Analyzing my input for constraints and edge cases
5. A data structure to store the span of time spent asleep
6. Building and debugging the algorithm that generates it
7. Finding the guard that has the most minutes asleep
8. Find the minute the winning guard spent asleep the most often

Parse the notes

I need to extract from this:

[1518-11-01 23:58] Guard #99 begins shift

• 1518-11-01 23:58
• 99

And from these:

[1518-11-01 00:05] falls asleep
[1518-11-01 00:25] wakes up

• The time, again
• falls asleep or wakes up

Time to use regexr.com

My pieced-together regular expression:

/\[(.+)\]\s(?:Guard\s#)?(\d+)?\s?(\w+\s\w+)/g

• \[(.+)\] captures [1518-11-01 00:05]
• (?:Guard\s#)?(\d+)? optionally captures ID from Guard #ID
• (\w+\s\w+) captures any words after either the ID or the timestamp

Generate the list of parsed notes with timestamps

My regular expression extracts three values:

• Timestamp
• ID or nothing
• Status

I need an array that includes:

1. Month and Day
2. Seconds
3. Full datetime as a number
4. Either ID or Status

My mini-algorithm for getting the info above:

Use `matchAll()` on a string
  Pass my regular expression as argument
Grab the first item in the resulting iterable object
Grab the second thru fourth items from that array
Further split() the timestamp string to extract the month, day and seconds
Use `new Date().getTime()`, passing the timestamp as argument to get a number - for later sorting
Return the list of extracted values

Sort the notes by date

• After confirming I extracted and generated the proper data
• I manually re-ordered the example input
• Then I sorted the list by the generated number in ascending order

This was the easiest part.

Altogether, the last few steps looks like this:

Analyzing my input for constraints and edge cases

• There's one guard per day
• The guard may start their shift prior to or after midnight
• Therefore, I can't rely on the date referenced when the guard starts their shift as the date corresponding to that guard's sleep/wake times
• After every guard is one or more pair of sleep/wake note

It seems like a safe bet if my algorithm:

• Uses the date of the next item whenever it encounters a new guard, as the date of that guard's shift

A data structure to store the span of time spent asleep

The instructions feature this illustration:

Date   ID   Minute
            000000000011111111112222222222333333333344444
            012345678901234567890123456789012345678901234
11-01  #10  .....####################.....###############
11-02  #99  ........................................#####
11-03  #10  ........................#####................
11-04  #99  ....................................#########
11-05  #99  .............................................

For each day:

• The guard's ID
• The range of minutes within the midnight hour spent asleep

Since the prompt for Part 1 is:

Find the guard that has the most minutes asleep

It seems smart to:

• Use a dictionary where the keys are guard IDs and the values are...
• Dictionaries where the keys are each day and the values are
• 2-element arrays where the first element is the time falling asleep and the second element is the time woken up

For the example input, it would look like:

{
  '10': {
    '11-01': [
       [5,25],
       [30,54]
    ],
    '11-03': [
       [24,28]
    ]
  },
  '99': {
    '11-02': [
       [40,49]
    ],
    '11-04': [
       [36,45]
    ],
    '11-05': [
       [45,54]
    ]
  }
}

I'm excited to build this object using my list of parsed notes!

Building and debugging the algorithm that generates it

Ingredients:

• A dictionary, guards
• A way to track the ID of the current guard
• A loop to check each note in chronological order

My algorithm - Draft 1:

If the note references a guard ID
  Update current to this ID
  If this ID isn't a key in guards
    Make it
    Set as its value an empty dictionary
  Set as a new key in the dictionary the stringified 'MM-DD' from the next note
    And as its value an empty list
Else, if the note references a sleep/wake action
  If the action is 'falls asleep'
    Insert an empty list at the end of the list associated with the note's 'MM-DD'
  Insert the seconds referenced in the note at the end of the list that is the last-most list in the list associated with the note's 'MM-DD'

This generated the expected data structure for the example input.

But I noticed some odd data for my puzzle input:

{
  ID: {
    'MM-DD': []
  }
}

A few IDs has empty arrays associated with one or more days.

How could that be?

Well, I wrongly assumed:

• Every guard had at least one pair of sleep/wake action

However, my puzzle input features a few adjacent notes like this:

[...] Guard #ID begins shift
[...] Guard #ID begins shift

Meaning, that guard never fell asleep!

My algorithm - Draft 2:

If the note references a guard ID
  Update current to this ID
  If this ID isn't a key in guards
    Make it
    Set as its value an empty dictionary
  If the next note references a sleep/wake action
    Set as a new key in the dictionary the stringified 'MM-DD' from the next note
    And as its value an empty list
Else, if the note references a sleep/wake action
  If the action is 'falls asleep'
    Insert an empty list at the end of the list associated with the note's 'MM-DD'
  Insert the seconds referenced in the note at the end of the list that is the last-most list in the list associated with the note's 'MM-DD'

To be clear:

• I added a condition in the first if clause that checks whether the next note is a sleep/wake action
• Only if it is do I create a MM-DD key and associate with it an empty list

Phew! Now I see what I expected:

'239': {
  '06-18': [ [Array], [Array], [Array] ],
  ...
},
'271': {},
'317': {
  '08-18': [ [Array], [Array], [Array] ],
  ...
},

Finding the guard that has the most minutes asleep

Track the winning guard using a two-element array:
  1. ID of the guard, starting as null
  2. Number of minutes asleep, starting as 0

For each key in the guards object
  Set count at 0
  For each recorded day associated with the current guard
    Increment the count by the resulting number from the following operations:
      For each pair of numbers in the list of pairs
        Accumulate a sum, starting at 0
          Increment the sum by the difference of the second value and the first value
  If count is greater than the second value in the tracking two-element array
    Update the array to reflect the ID and count of the current guard

Find the minute the winning guard spent asleep the most often

Create an array with 60 elements - one for each minute
  Initialize all 60 elements as 0

For each day associated with the winning guard
  For each pair of numbers in the list of pairs
    Generate a list of numbers that span the first and second number
    For each number
      Increment the corresponding location in the 60-element array by 1

Return the product of two numbers:
  1. The ID of the winning guard
  2. The location of the largest number in the 60-element list

Testing the results:

• It worked on the example input!
• It worked on my puzzle input!

Part 2

1. Part 1, but for all guards this time!

Part 1, but for all guards this time!

• Part 1 had a process of elimination to find the sleepiest guard...and then identify the most common minute across days
• Part 2 shifts the elimination process to the second part: among all the guards, who has the largest count of the same minute across days?

Thankfully, this only required a few small tweaks to my code from Part 1:

• Enclose the iteration through one guard's days in an iteration for each guard
• Add a 3rd element to my tracker: 1) ID, 2) count, 3) minute with the highest count

That was it!

Testing the results:

• It worked on the example input!
• It worked on my puzzle input!

I did it!!

• I solved both parts!
• I used a bunch of techniques, including regular expressions, date generation and manipulation, string manipulation, array creation and sorting, type detection, object property iteration, higher-order array methods
• I successfully debugged my algorithm to work on the various patterns inherent to the puzzle input

Missed opportunity...?

• I was tempted to make a simulator for this puzzle.
• I wanted to generate illustrations like the one in the instructions...for each guard.
• Sadly, I'm more excited to finish the year strong rather than spend time building an un-interactive - and likely un-interesting - simulator

Nearing the finish line

Three more days!

Six more stars, I hope?

I sure would love to match or beat my current low star score of 34.

I need to get all six!

Luckily, the first three days are usually relatively easy.