Advent of Code 2020 - Day 9

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

This puzzle looks a lot like day 1. We have a list of numbers and need to do some operations that will return some big numbers.

Let’s try to DAX out them.

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

Part 1

We have a list of numbers of each the first 25 are a preamble. After this, any number can be calculated as a sum of any pair of numbers in that interval.

We need to find the only number where this property is not true.

Loaded the file and just added an index column to help with the intervals:

Starting with setting the preamble parameter and our working list:

Day 9 - Part 1 =
VAR preamble = 25
VAR _number =
    FILTER (
        SELECTCOLUMNS ( 'Day 09', "_n", 'Day 09'[XMAS], "N_Index", 'Day 09'[Index] ),
        [N_Index] > ( preamble - 1 )
    )

Using the same strategy from day 1 we build two helpers tables which we will use as a cartesian product.

VAR _table1 =
    SELECTCOLUMNS ( 'Day 09', "_a", 'Day 09'[XMAS], "A_Index", 'Day 09'[Index] )
VAR _table2 =
    SELECTCOLUMNS ( 'Day 09', "_b", 'Day 09'[XMAS], "B_Index", 'Day 09'[Index] )

And now the cartesian product. The crossjoin with those constraints in the filter will give us all the combinations of values 2 by 2 on the length of the preamble. Then we just sum them.

VAR _sumTable =
    ADDCOLUMNS (
        SELECTCOLUMNS (
            FILTER (
                CROSSJOIN ( _table1, _table2 ),
                            [A_Index] > [B_Index]
                            && [A_Index] - preamble <= [B_Index] ),
            "Index", [A_Index],
            "a", [_a],
            "b", [_b]
        ),
        "a+b", [a] + [b]
    )

To find our answer we just need to do an except between the two sets.

RETURN
    EXCEPT (
        SELECTCOLUMNS ( _number, "XMAS", [_n] ),
        SELECTCOLUMNS ( _sumTable, "XMAS", [_n] )
        )
    )

Part 2

Now we need to find the range of contiguous numbers that add up to the solution we found in part 1. After we find that range the answer will be the sum of the smallest and largest number in those values.

This solution will aim generate all possible combinations and return the range. Having the range returning the answer will be trivial.

Breaking down the measure we have the value to found as invalidNumber and two generated tables to help us create all the possible combinations between the indexes.

VAR invalidNumber = [Day 9 - Part 1]
VAR _x =
    SELECTCOLUMNS ( GENERATESERIES ( 0, 999 ), "_x", [Value] )
VAR _y =
    SELECTCOLUMNS ( GENERATESERIES ( 1, 1000 ), "_y", [Value] )

Now the meaty part. We do a cartesian product between the two tables, constraining the results by forcing one of the indexes to be smaller than the other and their difference to be less than 20. Then we use those indexes to sum up the values in rangeand checking if the value is the one we need.

The constraint that filter out ranges bigger than 20 is not needed, and I’ve questioned it’s presence here. It helps with performance, reducing the time to get the solution, but in case your interval happens to be bigger than that, you will need to adjust the value for a bigger number. With this constraint the measures takes about a second in my computer with it and about a minute without it to calculate.

VAR _combine =
        FILTER (
            CROSSJOIN ( _x, _y ),
                [_x] < [_y]
                && ABS ( [_y] - [_x] ) < 20
                && CALCULATE (
                    SUMX ( 'Day 09', 'Day 09'[XMAS] ),
                    TREATAS ( GENERATESERIES ( [_x], [_y] ), 'Day 09'[Index] )
                ) = invalidNumber
            )

Picking the final range values and returning the sum of the smallest with the largest:

VAR _values =
    FILTER (
        'Day 09',
        [Index] >= MINX ( _combine, [_x] )
            && [Index] <= MINX ( _combine, [_y] )
    )
RETURN
    MINX ( _values, [XMAS] ) + MAXX ( _values, [XMAS] )

Conclusion

I’m not really happy with the solution for part two and I will revisit this using Power Query, or if I manage to came up with a better approach with DAX. Something like this pseudo-code:

int a = 0
int b = 1
bool continue = true

While (continue)
{
    x = SUM(FromRange(a,b))
    if x == [Day 9 - Part 1]
    then return x
         continue = false;
    else
         if x < [Day 9 - Part 1]
         then b += 1
         else a += 1
}

If you know of a better way please discuss it with me.

Have fun!!

 Share!