Expand description
§Ticket Translation
Part one is optimized by first merging as many of the rules as possible. The trick to merge ranges efficiently is to first sort them by start, then combine any that start before the end of the previous range. For my input this cut down the checks for each number from 40 to 1. The invalid rows are saved and passed to part two.
Part two is a constraint satisfaction problem. First we transpose the ticket rows to columns, grouping each number in the same position in the ticket. For each column we check every number, eliminating rules that don’t fit, since we know that potential rules must be valid for every field in same position.
To solve there must be at least one column with only one rule remaining. As this rule can only belong to this column, we eliminate it from other columns. This causes a chain reaction where a second column will reduce to only one rule, continuing until all columns have been resolved.
Structs§
- Rule 🔒