Advent of Code 2020 Day 16
Try the simulator!
Task: Solve for X where...
X = the sum/product of all ticket numbers of a particular type
- Sum of invalid numbers among nearby tickets
- Product of numbers in each of the six
departurefield slots
Example input:
class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50
your ticket:
7,1,14
nearby tickets:
7,3,47
40,4,50
55,2,20
38,6,12
It represents:
- The rules for ticket fields
- The numbers on your ticket
- The numbers on other nearby tickets
Part 1
- Confirming understanding of how to get the solution
- Writing an algorithm to create a range of numbers from a min and max
- Writing a regular expression that captures each min and max
- Writing the full algorithm
Confirming understanding of how to get the solution
These are the rules for valid numbers:
class: 1-3 or 5-7
row: 6-11 or 33-44
seat: 13-40 or 45-50
Regardless of field, a valid number is one that is within any of these ranges:
1,2,3 or 5,6,7
6,7,8,9,10,11 or 33,34,35,36,37,38,39,40,41,42,43,44
13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40 or 45,46,47,48,49,50
Considering only unique values:
1,2,3,5,6,7,8,9,10,11,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50
These are the nearby tickets:
7,3,47
40,4,50
55,2,20
38,6,12
We need to check each number for whether it is among the unique valid numbers:
Valid numbers marked with .
. . ..
.. 4 ..
55 . ..
.. . 12
Adding them together = 71
Writing an algorithm to create a range of numbers from a min and max
- How do we turn
1-3into[1,2,3]?
Create an array whose length is one greater than the upper number minus the lower number
Fill the array with integers whose value is the index plus the lower number
Here's my algorithm in JavaScript:
Array(upper - lower + 1).fill(null).map((_,i) => i + lower)
Writing a regular expression that captures each min and max
- How do we extract two sets of capture groups from
row: 6-11 or 33-44such that the first group contains6and11and the second group contains33and44?
Thankfully, the regular expression is simple
/(\d+)-(\d+)/g
-
(\d+): Match 1 or more digits and save as capture group 1 -
-: Match one hyphen character -
(\d+): Match 1 or more digits and save as capture group 2 -
g: Find all instances within a larger string
Writing a working algorithm
Split the input at each pair of new line characters, creating an array with three elements
Create an empty set of unique values
For each match of upper and lower bounds captured by a regular expression applied to the first element from the processed input
Create an array whose length is one greater than the upper number minus the lower number
Fill the array with integers whose value is the index plus the lower number
For each number
Add it to the set of unique values if not already found
Split the third element from the processed input at each new line character
Remove the first element from the new list of strings
Replace each string with the result of the following operations:
Split the string at each comma
Coerce each string in the new list to a number
Replace each list of numbers with the result of the following operations:
Accumulate an array - starting as empty - for each number in the list
If the number is NOT among the unique list of numbers generated earlier
Insert it at the end of the accumulating array
Flatten the array of arrays of numbers one level so it is an array of numbers
Accumulate a sum - starting at 0 - for each number in the list
Return the sum
Here's a visualization of that algorithm:
Part 2
- Reading the instructions
- Analyzing the example for edge cases
- Writing a working algorithm
- Building the simulator
Reading the instructions
- This reminds me of 2020 Day 21 - Allergen Assessment - Part 2: creating and comparing progressively smaller lists of values assuming they each will eventually become unique lists with 1 possibility.
- In Part 1, I mutated each nearby ticket array to include 0 or more invalid numbers. This time, I need to generate an un-mutated - but filtered - list of nearby tickets that only contain valid numbers.
- In Part 1, I combined all ranges into one set of valid numbers. This time, I need to store separate sets - one for each field comprised of numbers from both ranges. I can still perform the invalid ticket check on a combined set of numbers.
Analyzing the example for edge cases
The new example input is:
class: 0-1 or 4-19
row: 0-5 or 8-19
seat: 0-13 or 16-19
your ticket:
11,12,13
nearby tickets:
3,9,18
15,1,5
5,14,9
The author claims that it can be determined that numbers, in order, belong to the following respective fields:
row,class,seat
I wanted to presume that each field's range of numbers presented a scenario where - when comparing all numbers in any given slot with each range of numbers for each field - only one field's range would enable all numbers to be valid.
Sadly, it won't be that easy.
The outlier is row:
class: 0-1 or 4-19
row: 0-5 or 8-19
seat: 0-13 or 16-19
class: 0,1,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19
row: 0,1,2,3,4,5,8,9,10,11,12,13,14,15,16,17,18,19
seat: 0,1,2,3,4,5,6,7,8,9,10,11,12,13,16,17,18,19
nearby tickets slot 1:
3,15,5
class: FAIL
row: PASS
seat: FAIL
Slot 1 must be row
nearby tickets slot 2:
9,1,14
class: PASS
row: PASS
seat: FAIL
Could be class or row
Can't be row, since that can only be slot 1
Must be class
nearby tickets slot 3:
18,5,9
class: PASS
row: PASS
seat: PASS
Could be any
Can't be row, since that can only be slot 1
Can't be class, since that can only be slot 2
Must be seat
Thus, my algorithm must perform several extra iterations to whittle down the possible fields that can be assigned to any given slot...assuming that each iteration will eliminate at least one more option.
Writing a working algorithm
Setup:
Split the input at each pair of new line characters, creating an array with three elements
Create an object mapping field names to a set of unique values and an eventual known position among ticket numbers
Mapping fields to ranges:
For each match of field name and upper and lower bounds captured by a regular expression applied to the first element from the processed input
Add a key to the object using the field name, with an empty set of eventual unique values
Create an array whose length is one greater than the upper number minus the lower number
Fill the array with integers whose value is the index plus the lower number
For each number
Add it to the set of unique values if not already found
Filtering valid nearby tickets:
Split the third element from the processed input at each new line character
Remove the first element from the new list of strings
Replace each string with the result of the following operations:
Split the string at each comma
Coerce each string in the new list to a number
Filter the list so it only includes nearby tickets that pass the following test:
Accumulate an array - starting as empty - for each number in the list
If the number is NOT among the unique list of numbers generated earlier
Fail the test
Generate and fill each slot with the pool of ticket numbers:
Create an array with as many elements as there are fields, and each element is an empty set of unique values
For each nearby ticket
For each number in the ticket
Add the number - if it doesn't already exist - to the set at the location in that array equal to the location of this number in the ticket
Determine which field corresponds to each slot:
Create a list of all fields
Create an object that will eventually map each field to the identified slot location
Do as many times as there are fields
For each field
Change the string into the array resulting from the following operations:
For each pool of ticket numbers in each slot
Return whether all numbers in the pool exist in the field's range of numbers
Find the index of the only array whose count of elements that are 'true' is equal to one greater than the current iteration number: 1-20
For each field name and its identified slot location newly stored from a previous iteration
Update the values at the slot location in the matching array to 'false'
By now, the matching array should have only one value that is 'true'
Add a new key and value to the object where the key is the field name at the same location in the list of all fields that mimics the index of the matched array, and its value is the location of the only 'true' value in that matched array
Identify and multiply together the six 'departure' field ticket numbers in my ticket:
Process the second element of the input array into an array of numbers
For each newly discovered field name and slot location
Accumulate an array - starting as empty - that contains the numbers from my ticket who's locations match the slot location of all field names that include the word 'departure'
For each number in the array of 6 numbers
Accumulate the product of all 6 numbers
Return the product of all 6 numbers
Building the simulator
- I opted not to simulate Part 1, especially since the GIF included here demonstrates that algorithm well enough
- Instead, I chose to simulate the part of the algorithm that identifies each field's slot and highlights which of the six ticket numbers pertain to a
departurefield - Thankfully, most of the process was copy-paste from an earlier simulator and from my solution code
- I just had to break out the 20-iteration loop into a separate click event, and update the two sections on the right after each new field is identified
- The result is a self-paced, quick sprint to the answer
Try the simulator!
Summary
- Part 1 went by fast
- Part 2 was more difficult than I initially imagined
- I'm glad I put my newfound Regex knowledge into practice
- I recognize that this algorithm - like most of mine - is very naive (a.k.a. brute force-y)
- My mission is still to solve the puzzle and write as clean of code as possible using newly gained computer science skills
Top comments (0)