Advent of Code day 10

In today's puzzle we are daisy chaining multiple adaptors to charge our devices (don't try this at home!)

Part 1 seems incredibly easy. Just sort the adaptors and add up the 1 volt differences and 3 volt differences and multiply them?

Okay, a slight complexity-- we need to include the original power supply (0) and the phone itself (highest + 3). That’s easily dealt with by appending 0 and max+3 to my list of adaptors.

And it really was that easy. ominous voice Too easy.

Okay, part 2 Now we get to the hard part -- how to count all possible combinations. They have a clue

You glance back down at your bag and try to remember why you brought so many adapters; there must be more than a trillion valid ways to arrange them! Surely, there must be an efficient way to count the arrangements.

So we need to do this efficiently. We shouldn't try all arrangements. The voltages have to go up, so first we sort them. Then it’s really just a matter of removing adaptors that can be removed leaving a voltage difference of 3 or less.

I’m thinking about only keeping track of the differences between adaptors rather than the adaptors themselves. If we do that, we can start to eliminate redundancies.

Any difference of 3 is not going to change our answer, so we can just remove those.

In the first example we have: [16, 10, 15, 5, 1, 11, 7, 19, 6, 12, 4, 0, 22]

Sorting that we get: [0, 1, 4, 5, 6, 7, 10, 11, 12, 15, 16, 19, 22]

Looking at only the difference between each voltage we get: [1, 3, 1, 1, 1, 3, 1, 1, 3, 1, 3, 3]

So on second thought we can’t remove the 3s but we can treat them barriers to combining. A 3 can’t be removed, and neither can anything in a 3, 1, 3 series.

In a [3, 1, 1, 3] series you can remove the first 1. (Checking above that’s [10, 11, 12, 15] -- so we can remove the 11, but not the 12. -- so that makes 2 possibilities (with the 11 or without)

In a [3, 1, 1, 1, 3] series we can remove either or both of the first two 1s. [again, above that’s the [1, 4, 5, 6, 7, 10] -- we can remove the 5, the 6 or both. So that makes 4 possibilities [1, 4, 5, 6, 7, 10], [1, 4, 6, 7, 10], [1, 4, 5, 7, 10], and [1, 4, 7, 10]

Let’s check the longer example to see how this pattern shakes out.

[28, 33, 18, 42, 31, 14, 46, 20, 48, 47, 24, 23, 49, 45, 19, 38, 39, 11, 1, 32, 25, 35, 8, 17, 7, 9, 4, 2, 34, 10, 3, 0, 52] [0, 1, 2, 3, 4, 7, 8, 9, 10, 11, 14, 17, 18, 19, 20, 23, 24, 25, 28, 31, 32, 33, 34, 35, 38, 39, 42, 45, 46, 47, 48, 49, 52] [1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 3, 1, 1, 1, 3, 1, 1, 3, 3, 1, 1, 1, 1, 3, 1, 3, 3, 1, 1, 1, 1, 3]

If we have [3, 1, 1, 1, 1, 3] -- that’s the [4, 7, 8, 9, 10, 11, 14] we can remove the just the 8, just the 9, just the 10. We could also remove the 8 and the 9, the 9 and the 10 or the 8 and the 10. That’s 7 combinations .

I’m going to make up some larger sets of 1s, but starting at 0.
0, 1, 2, 3, 4, 5, 8 1, 1, 1, 1, 1, 3

Okay, we can

1. keep it as is
2. remove the 1
3. remove the 2
4. remove the 3
5. remove the 4
6. remove the 1&2
7. remove the 2&3
8. remove the 3&4
9. remove the 1&3
10. remove 1&4
11. remove 2&4
12. remove 1, 2, & 4
13. remove 1, 3, & 4

This is giving me a headache -- let’s code it using itertools. Since you have to provide the length of the subset for itertools to get all combinations we will need to loop through all possible lengths.

So I created a “figure_out_combos” function that returns a dictionary for 1-15 ones in a row and how many combinations that represents. (I made the mistake of printing all the combinations got a new achievement -- first time crashing Visual Studio! It only crashes the active window though -- VS remains working and will even reopen the window you crashed. A step up from Spyder and nano!)

def figure_out_combos():
    comb_dict={}
    from itertools import combinations
    for i in range(15):  #let's start with 15 1s in a row -- we can increase this later if we need to.  
        my_list = list(range(1, i+2))  #set up our list
        my_combs = []                   #have an empty list for the combinations
        for x in range(1, i+1):         #step through the length and find combionations of length 1, 2, ... i+1
            my_combs += list(combinations(my_list, x))  #add all these combiations to a list of lists
        good_combs=[]
        for comb in my_combs:               #now we step through our list of lists
            full_comb = [0] + list(comb) + [my_list[-1]+3]          #add on the initial and final adaptors
            diff = [full_comb[x]-full_comb[x-1] for x in range(1, len(full_comb))]      #find the differences in voltages between each consequetive adaptor
            if all(x<=3 for x in diff):  # only add the ones that have no jumps that are more than 3
                good_combs.append(comb)
        comb_dict[i+1]=len(good_combs)+1  #take the length of the good combinations and add that to my lookup table
    return(comb_dict)

I then went through the list of voltage differences in the puzzle input kept track of consecutive 1s, used the dictionary to find the associated number of combinations and multiplied all those combinations together. AND IT WORKED!

Okay, Advent of Code is starting to test my brain. Excellent. Now to check out reddit and see how someone else solved the same problem in 2 lines.

I also want to go through and clean up this code, so stay tuned for that. For now, sorry -- it's a bit convoluted. Questions/comments are welcome.

Full solution as always at Github.

Today marks a first -- I haven't completed the day 11 problem at the time I'm writing this. I don't think it's so hard, just life gets in the way. We'll see what tomorrow brings.