DEV Community

Cover image for Ticket Translation
Robert Mion
Robert Mion

Posted on

Ticket Translation

Advent of Code 2020 Day 16

Try the simulator!

Simulator of Part 2 algorithm

Task: Solve for X where...

X = the sum/product of all ticket numbers of a particular type
Enter fullscreen mode Exit fullscreen mode
  1. Sum of invalid numbers among nearby tickets
  2. Product of numbers in each of the six departure field 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
Enter fullscreen mode Exit fullscreen mode

It represents:

  1. The rules for ticket fields
  2. The numbers on your ticket
  3. The numbers on other nearby tickets

Part 1

  1. Confirming understanding of how to get the solution
  2. Writing an algorithm to create a range of numbers from a min and max
  3. Writing a regular expression that captures each min and max
  4. 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

These are the nearby tickets:

7,3,47
40,4,50
55,2,20
38,6,12
Enter fullscreen mode Exit fullscreen mode

We need to check each number for whether it is among the unique valid numbers:

Valid numbers marked with .
. . ..
.. 4 ..
55 . ..
.. . 12
Enter fullscreen mode Exit fullscreen mode

Adding them together = 71

Writing an algorithm to create a range of numbers from a min and max

  • How do we turn 1-3 into [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
Enter fullscreen mode Exit fullscreen mode

Here's my algorithm in JavaScript:

Array(upper - lower + 1).fill(null).map((_,i) => i + lower)
Enter fullscreen mode Exit fullscreen mode

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-44 such that the first group contains 6 and 11 and the second group contains 33 and 44?

Thankfully, the regular expression is simple

/(\d+)-(\d+)/g
Enter fullscreen mode Exit fullscreen mode
  • (\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
Enter fullscreen mode Exit fullscreen mode

Here's a visualization of that algorithm:
Part 1 algorithm visualization

Part 2

  1. Reading the instructions
  2. Analyzing the example for edge cases
  3. Writing a working algorithm
  4. 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
Enter fullscreen mode Exit fullscreen mode

The author claims that it can be determined that numbers, in order, belong to the following respective fields:

row,class,seat
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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 departure field
  • 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!

Simulator of Part 2 algorithm

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)