Advent of Code 2020: Day 16

Part 1

As you’re walking to yet another connecting flight, you realize that one of the legs of your re-routed trip coming up is on a high-speed train. However, the train ticket you were given is in a language you don’t understand. You should probably figure out what it says before you get to the train station after the next flight.

Unfortunately, you can’t actually read the words on the ticket. You can, however, read the numbers, and so you figure out the fields these tickets must have and the valid ranges for values in those fields.

You collect the rules for ticket fields, the numbers on your ticket, and the numbers on other nearby tickets for the same train service (via the airport security cameras) together into a single document you can reference (your puzzle input).

The rules for ticket fields specify a list of fields that exist somewhere on the ticket and the valid ranges of values for each field. For example, a rule like class: 1-3 or 5-7 means that one of the fields in every ticket is named class and can be any value in the ranges 1-3 or 5-7 (inclusive, such that 3 and 5 are both valid in this field, but 4 is not).

For example, consider this ticket:

1
2
3
4
5
6

.--------------------------------------------------------.
| ????: 101    ?????: 102   ??????????: 103     ???: 104 |
|                                                        |
| ??: 301  ??: 302             ???????: 303      ??????? |
| ??: 401  ??: 402           ???? ????: 403    ????????? |
'--------------------------------------------------------'

Here, ? represents text in a language you don’t understand. This ticket might be represented as 101,102,103,104,301,302,303,401,402,403; of course, the actual train tickets you’re looking at are much more complicated. In any case, you’ve extracted just the numbers in such a way that the first number is always the same specific field, the second number is always a different specific field, and so on - you just don’t know what each position actually means!

Start by determining which tickets are completely invalid; these are tickets that contain values which aren’t valid for any field. Ignore your ticket for now.

Consider the validity of the nearby tickets you scanned. What is your ticket scanning error rate?

You can read the full text here. For those of you who have been reading my blogs, or taking part in puzzles yourself, this problem should feel very familiar to day 4. The first part of today’s is entirely data parsing and data validation. We need to read in all of the ticket field rules and store them. After that, we can read in each ticket and validate all of the numbers on the ticket.

We’re going to start by setting up a class called Field which stores the rules for a given field on the ticket. We can then write a validator method, valid which we can call to check if a number is valid for the given Field. In C++, this could be implemented as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Field {
  public:
    std::string name;
    std::pair<int, int> range1;
    std::pair<int, int> range2;
    std::list<int> column;
    Field(std::string n, std::pair<int, int> r1, std::pair<int, int> r2)
        : name(n), range1(r1), range2(r2) {
    }
    int valid(int val) {
        if ((val >= range1.first) && (val <= range1.second)) {
            return 1;
        }
        if ((val >= range2.first) && (val <= range2.second)) {
            return 1;
        }
        return 0;
    }
};

This class contains the name of the field, the two ranges that the number on the ticket must lay within, and the column (which we are ignoring for part 1). We have also defined a constructor and the validator which are fairly straightforward. The validator returns 1 if the number is within one of the two ranges, and it returns 0 otherwise. Thus, we can now loop through the rules of the form,

1
2

departure location: 31-221 or 241-952
departure station: 27-780 or 787-957

and generate Fields. To achieve this we are going to use regex to process the line,

1

std::regex pieces_regex("([a-z\\s]+): (\\d+)-(\\d+) or (\\d+)-(\\d+)");

The line above will match the initial words, along with their spaces before moving on to match the 4 numbers included in the range. We can then loop through every one of these rules, applying regex and creating the corresponding Field object and storing them in a vector.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Load in the fields
std::vector<Field> fields;
while (std::getline(myfile, line)) {
    if (line == "") break;
    std::regex_search(line, pieces_match, pieces_regex);
    std::pair<int, int> r1 = {std::stoi(pieces_match[2]),
                              std::stoi(pieces_match[3])};
    std::pair<int, int> r2 = {std::stoi(pieces_match[4]),
                              std::stoi(pieces_match[5])};
    fields.push_back(Field(pieces_match[1], r1, r2));
}

Excellent! Now we have a vector of fields, each of which has it’s own validator method which we can call on any value.

Now we need to read in the tickets which are stored like this,

1
2
3
4

854,509,243,913,926,411,308,322,69,875,779,371,51,514,367,873,524,645,934,322
358,885,814,800,197,363,388,50,138,820,854,793,89,738,733,306,796,334,387,8
...
312,334,928,657,776,276,319,893,163,162,244,206,446,719,568,856,391,831,722,931

We have many lines each of which contains 20 comma-separated numbers, representing a ticket. To parse these we are going to use a new regex pattern which just identifies numbers,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

// Now load in the tickets
std::vector<std::vector<int>> tickets;
std::regex number("(\\d+)");
while (std::getline(myfile, line)) {
    std::sregex_token_iterator it = {line.begin(), line.end(), number};
    std::vector<int> ticket;
    while (it != std::sregex_token_iterator()) {
        int n1 = std::stoi(*it);
        ticket.push_back(n1);
        it = std::next(it);
    }
}

Perfect, we now have a vector of vectors which store integers for the value on each ticket.

We now loop through each value, on each ticket and ensure that it is valid for at least one of the rules that we stored. We can do this with the following code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// Loop through finding and marking invalid tickets
std::vector<int> invalid(tickets.size());
for (size_t i = 1; i < tickets.size(); i++) {
    std::vector<int> &t = tickets[i];
    for (auto v : t) {
        int valid = 0;
        // Check this number is valid for atleast 1 field
        for (auto &f : fields) {
            valid = std::max(valid, f.valid(v));
            if (valid == 1)
                break;
        }
        // Add value and mark ticket as invalid, if invalid
        if (valid == 0) {
            ans1 += v;
            invalid[i] = 1;
        }
    }
}

As soon we find a field that the value is valid for we move on to checking the next value. Suppose the value is not valid for any field. We add it to our answer and mark the ticket as invalid in our invalid vector, which is something we need in part 2. But, for now, all we need to do is sum the invalid numbers, and we have the first ⭐!

Part 2

Now that you’ve identified which tickets contain invalid values, discard those tickets entirely. Use the remaining valid tickets to determine which field is which.

Using the valid ranges for each field, determine what order the fields appear on the tickets. The order is consistent between all tickets: if the seat is the third field, it is the third field on every ticket, including your ticket.

Once you work out which field is which, look for the six fields on your ticket that start with the word departure. What do you get if you multiply those six values together?

You can read the full text here. Well, part 2 is a little tricker, as expected. We now need to work out which column corresponds to which field on the ticket.

We are going to solve part 2 in two steps. For the first step we will loop through every field, and every column of numbers of the tickets. We can then check if every value in that column is valid for the given field, if so, we will store this as a possible column for that field. If any value is not valid, then that column cannot be represent that field. Our C++ code for this is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// For each field we loop through and find every column for which the valid
// tickets work
for (size_t i = 0; i < fields.size(); i++) {
    // Try each column
    for (size_t j = 0; j < fields.size(); j++) {
        int valid = 1;
        // Try every valid ticket
        for (size_t k = 1; k < tickets.size(); k++) {
            if (invalid[k] == 1)
                continue;
            valid *= fields[i].valid(tickets[k][j]);
            if (valid == 0)
                break;
        }
        // Is this column a valid solution for this field?
        if (valid == 1)
            fields[i].column.push_back(j);
    }
}

where for each field, we loop over every column in every ticket to see if that column is a possible candidate for the outer field. If the column is a possibility, then we store it as a possibility in a list in the Field class. This process will return results similar to those shown below:

1
2
3

a: 1
b: 1, 3
c: 2, 3

Which says field “a” could be column 1, and field “b” could be column 1 or 3, and so on. We now repeatedly iterate over the output and eliminate redundant options. As field “a” can only be column 1, we can remove column 1 from all of the other fields,

1
2
3

a: 1
b: 3
c: 2, 3

Now we know that field “b” is column 3; thus, field “c” cannot be column 3,

1
2
3

a: 1
b: 3
c: 2

and by completing the logic puzzle and eliminating solved columns we can reach a determinant answer. We can do this in code with the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// Each field knows it possibilities; now we need to work out every fields
// column by a process of elimination. If one field has only 1 valid column
// then its solved and that column cannot solve another field
bool solved = false;
while (!solved) {
    solved = true;
    for (auto &f : fields) {
        // Only one possibility, thus this field has its column and this
        // column cannot solve other fields so we remove it from their
        // possibilities
        if (f.column.size() == 1)
            for (auto &f2 : fields) {
                if (f.name == f2.name)
                    continue;
                f2.column.remove(f.column.front());
            }
        else
            solved = false;
    }
}

After a few iterations, we have deduced which column corresponds to each field. Then we just have to find the “departure” fields in our own ticket, ticket 0, and return the product.

1
2
3
4
5
6
7

// Great, now every field knows which column it corresponds to! So we can
// loop through our own ticket and multiply the values in columns with names
// starting with departure
ans2 = 1;
for (auto &f : fields)
    if (f.name.substr(0, 9) == "departure")
        ans2 *= tickets[0][f.column.front()];

There we go, ⭐⭐!

Reflections

I think my code for today’s puzzle was reasonably readable. In particular, making a class to store each field with a validator helped make the code slightly less imperative, and thus more readable. However, I probably could, and should have factored out a little more code into smaller functions.

Today’s puzzle was not so much an exercise in algorithms for part 1, but more data parsing. Nonetheless, we did make some algorithmic decisions. Namely, we chose to read in every rule, and then subsequently read in and store every ticket. We then do a single pass over each value, in each ticket and check it against every field. Thus the complexity of part 1 scales, at worst, as O(N * M * M) in time and O(N * M) in space where N is the number of tickets, and M is the number of fields.

For part 2, we end up checking every column of every ticket for every field. Thus, as before this initially scales the same as part 1, O(N * M * M)-time and O(N * M)-space. Then later in part 2, we must also perform our process of elimination which scales in time as O(M * M). Thus, overall, the entire solution scaled the same as part 1.

I hope you enjoyed today’s puzzle, even if data parsing and validation is not your thing. See you tomorrow!

I have no affiliation with AoC. I’m just a fan of the programming puzzles. If you enjoy them too, please feel free to join in and support the creators

Comments