Advent of Code - Day 10

Day 10: Factory

In this challenge we need to turn some machines on and get them to use the correct joltage.

The manual describes one machine per line. Each line contains a single indicator light diagram in [square brackets], one or more button wiring schematics in (parentheses), and joltage requirements in {curly braces}.

[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}

Part 1

In this part we are asked, “What is the fewest button presses required to correctly configure the indicator lights on all of the machines?”

I do not like admitting that the first part of this one tripped me up. Parsing the text was easy enough but frankly I was not sure how to hnadle that information once it was read in and split apart.

I tried a few things but my solutions ended up overcounting and I could not track down why. For this reason I sought someone elses solution that I could learn from. On the subreddit there was a vanilla Python solution that used sets and bitwise operators.

First the lights are converted to be a decimal representation of the binary value where “.” is a 0 and “#” is a 1. This is done from left to right so the second light in the example of […#.] is read as 01000 = 8.

Next each of the button presses are translated to a decimal representation of the binary value communicated. For the buttons [‘(3)’, ‘(1,3)’, ‘(2)’, ‘(2,3)’, ‘(0,2)’, ‘(0,1)’] where the number is the index for the lights. As an example (3) = 1000 = 8 and (1,3) = 1010 = 10.

I’ve spent a bunch of time staring at this bit of code but I think I’ve got it now.

current_lights = set(lights ^ btn for lights in current_lights for btn in buttons)

This is contained in a for loop that iterates the number of button presses and followed up by an if statement that checks if the target (desired light combination) appears in the resulting set. A set is used to make sure each of the values added are unique. If there are multiple ways to get to the same number we don’t care since we’re counting presses and not button press combinations.

This creates a set of (lights XOR buttons) for all lights in the current set. Each successive loop of this operation applies all button presses to each possible light state. This works since the lights work like binary operators. If a light is off “.” and the button press would interact with it then it turns on “#”. If the light is on “#” and the button press would interact with it then it turns off “.”. This exactly how XOR works and since integers compared with “^” are compared as binary this setup generates light possibilities in the form of the decimal representation of binary interactions.

Part 2

This part asks, “What is the fewest button presses required to correctly configure the joltage level counters on all of the machines?” The light state is ignored and instead the button presses changes the joltage as communicated in the curly braces.

This is the first time I had to install another library to get this to work. I did not come up with this solution but am instead writing to make sure I have some understanding of what’s happening here.

The solution I found used SciPy and specifically LinearConstraint, milp, and Bounds. Once the variables for this function are set milp (Mixed-integer linear programming) function can return the desired value.

result = milp(c, constraints=constraints, bounds=bounds, integrality=integrality) 

This is run for each line and the sum is calculated. I need to dig into exactly how this one works as I’m not sure what is happening under the hood.