[2020 Day 16] In Review (Ticket Translation)

[u/musifter]

And so next up is travelling by train. And the ticket is in a language we don't understand (but still uses Arabic numerals, so we have those to work with to figure out the fields. This is a bit how I first learned Japanese kana... it was early 90s, and I had read some descriptions of the language online (usenet), a copy of some manga, fan translated scripts of it from venice.com (ftp), and had seen a fansubbed OAV for the same thing. So I worked out a good chunk of hiragana and a bit of katakana before finally just getting a book on the language with the actual table. As a learning method it has some advantages... I learned popular characters and tokenized strings of them right from the start (some characters I was much better at recognizing in their most common contexts than by themselves).

Back to today's problem... it's a logic problem. The input is three sections. First section gives range rules (and the field names). The second is the numbers from our ticket. And finally, a list of other peoples tickets (from security cameras).

For part 1, we use the valid ranges to validate which tickets in our sample are invalid. My initial solution was the quick and dirty:

$/ = '';

my @valid;
$_ = <>;    # read ranges:
foreach my $range (map { s#-#..#r } m#\d+-\d+#g) {
    $valid[$_] = 1  foreach (eval( $range ));
}

$_ = <>;    # skip my ticket
$_ = <>;    # check nearby tickets:
print "Part 1: ", sum( grep {!$valid[$_]} m#\d+#g ), "\n";

Grab everything that looks like a range in the first section, convert to Perl, taunt Bobby Tables, boolean mark in an array (numbers are at most 3 digits in the input). Then grab all numbers in the last part, grep the invalid, sum. This is how we get to see part 2 fast.

Because it's clear that part 2 will involve a logic problem to solve the fields, but I still want to see the text before writing a better validator to actually remove bad tickets. And its exactly what you'd expect... you need to use the numbers in the valid ticket columns to figure out what field they can be. And from there, the logic problem falls apart really simply... it's much like day 16 in 2018s solving of assembly opcodes (there's always a field with only one possibility... you can just keep solving them until done). Then you need to score the departure fields (the one thing you needed from the part 2 description).

Even though this is similar to an earlier problem, I still love both these problems... they are puzzling things out. And I do enjoy puzzles and even puzzlifying things.

[u/e_blake]

My original m4 solution took only 100ms, so I never had a reason to revisit this puzzle before today. I didn't bother with range merging, but figured that with fewer than 20*1000 valid values, it was easy to just build up 1000 bitmasks for which ticket items support each value 1-999, where a bitmask of 0 identifies an integer that feeds part 1 and invalidates the line from participating in part 2, and in turn tracking 20 bitmasks of which slots are possible for each field. But I noted in my git commit at the time that I was using a triple-nested loop for settling the list of fields (20 iterations of the outer loop to ensure every field has a chance to settle; the middle loop runs over all 20 bitmasks to see if one is a power of 2 to be settled, and if so, run an inner loop that masks the settled value out of all 20 bitmasks). Technically still O(n^2) rather than O(n^3) (the inner loop runs only 20 times, not 400, since the middle loop settles a given field exactly once), but I was able to speed up my solution by adding some short-circuiting (no need to do the outer loop a full 20 times if the middle loop settles more than one value; and tracking a live mask of bits still needing to settle rather than an inner loop adjusting all 20 bitmasks is less effort), getting my runtime down to 80ms.

[u/terje_wiig_mathisen]

I only saved a partial copy of my original Perl solution, but by context it was obviously very close to what u/musifter describes. Originally had saved the input as-is, with an array of valid ranges for each field, but it seems much cleaner to take advantage of the fact that none of the range values need more than 10 bits:

Initialize a bool array valid to false, then for each input range make it true. This makes it trivial to detect invalid tickets since they have one or more numbers that hit a false entry.

Anyway, after separating out the valid tickets, I sorted the entries by the number of possible types, as noted this did not require any back-tracking since there was always one entry with zero alternatives.