Day 10 puzzle brings us an array of adapters. In the first part we will need to find the number of differences of 1 and 3 jolts. Part two asks us to find the total number of distinct ways in which we can arranje the adapters to connect the device to the charging outlet.
If you want to follow along please download AdventOfCode2020.pbit and check Day 1 post for instructions.
Part 1
After reading that long text, we can see in the example given that all we have to do is:
- add 0 and the maximum of the array plus 3
- sort the adapters
- count the number of gaps of size 1 or 3
After reading the file we get to this state:
To add the new rows we can create a table using the Table.FromRecords function with a row for 0 and another for the maximum plus 3.
Table.FromRecords({[Adapter=0], [Adapter=List.Max(#"Renamed Columns"[Adapter])+3]})
Then we just append the two queries and after sorting we will have something like this:
To calculate the differences between the current row and the previous one we need to use the same strategy of Day 4 - Part 1. We add an index column and a new column that calculates the difference between the current and the previous row.
Table.AddColumn(#"Reordered Columns", "Custom", each try [Adapter] - #"Reordered Columns"[Adapter]{[Index]-1} otherwise null)
We access the previous row using the [Adapter]{[Index]-1}. We also
need to use try ... otherwise pattern to eliminate the errors when
the formula tries to reach for positions below 0.
Finally we get to:
And with some simple DAX we get to our solution:
PRODUCTX ( SUMMARIZE ( 'Day 10', 'Day 10'[Diff To Previous Row], "_x", COUNTROWS ( 'Day 10' ) ), [_x] )
Part 2
This second part is much more interesting. We need to find all possible combinations of our adapters.
The puzzle warns us that a brute force is not the way here. The sample data with just a few adapters returns 19208 possible combinations.
Looking at the small sample until node 10:
And with a closer look at our numbers and the differences:
(0), 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, (22)
1 3 1 1 1 3 1 1 3 1 3 3 <- Differences
We only have a possibility from paths where the difference between current and previous is equal to three. The places we will have multiple choices are the sequences of one or more ones, e.g., to jump from nodes 4 to 7 we have four different possibilities:
4, 5, 6, 7
4, 5, 7
4, 6, 7
4, 7
On position 10, 11, 12 we only have two possibilities:
10, 11, 12
10, 12
If we multiply these two numbers together we will get exactly 8, which is the solution for the sample data.
Our final data has another possibility which are group of four ones. Repeating the same exercise we have 7 possible arrangements:
0, 1, 2, 3, 4
0, 1, 2, 4
0, 1, 4
0, 2, 4
0, 3, 4
0, 1, 3, 4
0, 2, 3, 4
Now we can build this table:
| # of Ones | # of Combinations |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 7 |
Instead of brute forcing and count all the possible combinations we can find the length of each group of ones and multiply everything together:
Testing the hypothesis:
And the result:
\(7*7*4*2*7*1*7=19208\)
Here’s a small function that implements this logic:
(lst as list) => let sepOn3 = List.RemoveItems(Text.Split(Text.Combine(lst),"3"), {""}), lengths = List.Transform(sepOn3, each Text.Length(_)), combs = { null, 1, 2, 4, 7 }, getCombs = List.Transform(lengths, each combs{_}), result = List.Accumulate(getCombs, 1, (seed, current) => seed * current) in result
We start by creating a list of ones by separating on each three. Then
we the group by its length and fetch from the combs list the number of
possible combinations and all that’s left it’s to multiply the values.
Conclusion
A nice problem that got me thinking, even tried some brute force. After the warning in the text I had to do it.
Hope you are enjoying this series as much as I am to write it. Until
now Power BI is showing that it can keep up. Let’s see what’s ahead.
Have fun!!