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
- Parse the notes
- Generate the list of parsed notes with timestamps
- Sort the notes by date
- Analyzing my input for constraints and edge cases
- A data structure to store the span of time spent asleep
- Building and debugging the algorithm that generates it
- Finding the guard that has the most minutes asleep
- 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
orwakes 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 capturesID
fromGuard #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:
- Month and Day
- Seconds
- Full datetime as a number
- 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
- 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.
Top comments (0)