Day 16. Ticket Translation

Problem statement

https://adventofcode.com/2020/day/16 (mirror)

My solution

For me, the hardest part of this problem was understanding what exactly we are expected to do. Part A states explicitly:

tickets that contain values which aren't valid for any field

which turns out to be a pretty simple thing to do. Note that this is only a necessary condition for validity! Consider example (which does really follow the same pattern as actual input):

class: 1-9
row: 10-99
seat: 100-999

nearby tickets:
7,3,47
40,4,50
555,2,20
38,6,12

Logically, only the third ticket can be valid – while every value from any ticket can be matched to some range, only the third ticket has a value that can be matched to seat number! While it’s never said straight, the problem statement implies that we do not have to handle this specific scenario! My solution makes uses that silent assumption.

Each range from the input is described by its name, and four numbers. An obvious approach to range validation is then to create a Range class, with a self-describing method IsValueInRange. (Name property is only required to calculate the final answer for Part B).

Then we parse all ranges from the input, create a variable List<Range> rangeList, and with a few nested for loops we check if a ticket maybe has a value that can’t be matched to any range.

In Part B, we are encouraged to assume that all tickets that passed the inspection in Part A are valid.

To create a ticket column ↔ range match, we will use the following algorithm:

If a ticket column i includes even one value that does not fit inside range j, then they cannot be a match. So for each range j we create a hashset of possible column numbers, and remove add those that pass the initial test (i.e. every value is in range).
While it is not guaranteed in general, in this particular case there will at least one range that can be matched to only one column. We memorize that match, and remove that column from possible matches for other ranges (after all, we search for a one-to-one relationship!).
We repeat previous step until every range is matched with a corresponding column.

Once again, this is not a general solution! But the problem inputs are structured in such a way that it works.

If it didn’t work, we would need to check in each step not only if there si a range that can be matched with only one column, but the other way around as well – there may be a column that can be matched to only one range. (In such case, instead of a list of hashsets, we would probably create a 2D bool array).