Advent of Code 2020 - Day 16

Power BI / DAX / Power Query / Advent of Code 2020

Today’s puzzle is called ‘Ticket Translation’. We have a bunch of fields in a language we do not understand and we need to figure out which is which.

There’s a set of rules we collected in several ways to a document that will serve as the puzzle input.

If you want to follow along please download AdventOfCode2020.pbit and check Day 1 post for instructions.

Part 1

Our input file is divided into three sections separated by a blank line:

  • The field name and the valid interval
  • Our ticket
  • Nearby tickets

Seems obvious that the first step is to parse and separate this data. For that we will be using our fold like function like we did previously:

List.Accumulate(
            Source,
            [Ret={}, Acc={}],
            (s,c) => if c = ""
                        then [Ret= s[Ret] & {s[Acc]}, Acc={}]
                        else [Ret= s[Ret], Acc= s[Acc] & {c}]
        )

We create a list with three lists containing each of our parts. The break is made when an empty line ("") is found.

To achieve the solution for this part we don’t need to know if a specific ticket is valid or not. We are just after the numbers that don’t fit any of the rules.

Following this idea we are going to create a list with the union of all the rules intervals and check every field in the nearby tickets for the odd ones out. We take the first list, the one that contains the set of rules and we create a list with all the possible correct values by using list comprehension in Power Query.

//class: 1-3 or 5-7
//row: 6-11 or 33-44
//seat: 13-40 or 45-50

{1..3} & {5..7} &
{6..11} & {33..44} &
{13-40} & {45-50}

=>

{1,2,3,5,6,7,8,9,10,11,13, (...), 50}

In the code below we take each of the entries in the list of rules and we extract the numbers creating a list of all the valid values.

Now that we have a set rules list, we need to take the values in the nearby tickets and for each number check if it belongs in the rules set list.

Each ticket is a comma separated set of numbers. We need to break them apart by using some code like this:

List.Accumulate(
            tailNumbers,
            {},
            (seed,current) => seed &
                  List.Transform(
                      Text.SplitAny(current, ","), each Int64.From(_)))

After we apply this to the tickets we will have a list of all the numbers in the tickets.

The numbers that will be invalid are the one that don’t exist in the other list.

List.Difference(numbers,valLists)

Part 2

To begin we are asked to remove the invalid tickets. Using the same strategy but now applied for each ticket:

We then can simply filter out the invalid ones:

That was easy enough. Now for the fun part, we will have to determine what field can match the group of values.

To do that we will take the tickets, separate them on the commas and assign the values to columns:

Now we transpose the table so that each line will correspond to a field:

Now we can transform these values into lists, so that we can associate them with the rules.

Here’s our rule list, after some simple transformations, along with the lower and upper bands of each one:

Now to calculate the possible valid columns we add a new custom column with the code:

Table.AddColumn(ticketFields, "Possibilities", (y) =>
           List.Accumulate(
               {0..19},
               {},
               (s,c)=>
                   if List.MatchesAll(
                       ticketsColumns{c}, each
                       let x = Int64.From(_) in
                           (x >= y[LB1] and x <= y[UB1]) or (x >= y[LB2] and x <= y[UB2]))
                   then s & {c}
                   else s)),

The idea here is that a list of values will be a valid option for that column if all the values are contained in the bounds.

For ‘departure location’ we will have as possible columns the options \(\{2,3,6,9,10,11,17,18\}\):

Now we can remove the bounds columns and expand the list of possibilities to rows:

We are told there’s only one possibility for each field, so we can create a small function that will check for the rows that have only one possibility and exclude those values as options for the others.

Taking our example:

class: {2,3}
row  : {1,2,3}
seat : {3}      //unique option so we can remove '3' from the others

=>

class: {2}      //unique option so we can remove '2' from the others
row  : {1,2}
seat : {3}

=>

class: {2}
row  : {1}
seat : {3}

Our code:

(x as record) as record =>
    if Table.RowCount(x[tbl]) > 0
    then
        let
            s1 = Table.Group(x[tbl], {"Field"}, {"Count", each Table.RowCount(_)}),
            s2 = Table.SelectRows(s1, each [Count] = 1),
            s3 = Table.SelectRows(x[tbl], each [Field] = s2{0}[Field]),
            s4 = Table.SelectRows(x[tbl], each [Possibilities] <> s3{0}[Possibilities]),
            s5 = Table.InsertRows(x[ret], 0,
                 {[Field=s3{0}[Field], Possibilities=s3{0}[Possibilities]]})
        in
            @fnPossibilities([tbl=Table.Buffer(s4), ret=s5])
    else x

While we have rows in the original table we do, when that table is empty we return the accumulator:

  • ‘s1’ – We check how many options we have for each of the field in the table.
  • ‘s2’ – We pick the fields with only one possibility
  • ‘s3’ – We collect those in the original table by using ‘s2’
  • ‘s4’ – We remove the fields with the same values as the unique ones
  • ‘s5’ – We store the unique ones on an accumulator table

Now that we have determined which field is which we need to find all the values in our ticket that match the fields names starting with ‘departure’.

Transforming our ticket to a similar structure:

And merging it with the possibilities table we get:

The answer will be the product of the 'your ticket:' column:

List.Product(#"Merged Queries"[#"your ticket:"])

Conclusion

And here you have it, the day 16 solution. A great show case for many of the great data transformation tools we have in Power Query.

Hope you liked it and took something that will be useful in our own adventures with Power BI.

Have fun!!

 Share!