The day 10 problem description is a thinly veiled graph problem: we find the sortest path from an initial stated to a desired end state.
I initially approached this problem using a breadth-first search (BFS)
NOTE: One notable implementation choice was how to represent and store button pushes. I wanted to record the results primarily for troubleshooting and debugging purposes. Although Python lists have an amortized time complexity of $O(1)$ for appends, they are relatively heavy in terms of memory usage and less efficient than linked structures for this use case. The Node class below provides a more time and memory-efficient data structure for representing lists incrementally.
import sys
from functools import reduce
from collections import Counter
from collections import deque
from queue import PriorityQueue
import copy
import math
import itertools
import re
import z3
with open("10.input") as f:
data = f.read().splitlines()
class Node:
__slots__ = ("value", "next")
def __init__(self, value, next_node=None):
self.value = value
self.next = next_node
def __len__(self):
if self.next == None:
return 1
else:
return 1+self.next.__len__()
def __repr__(self):
if self.next == None:
return str(self.value)
else:
return "Node("+str(self.value)+ " -> "+self.next.__repr__()+")"
def __iter__(self):
current = self
while current:
yield current
current = current.next
lights=[]
for l in data:
goal = l.split("] (")[0][1:]
buttons = l.split("] (")[1][:-1].split(") {")[0].split(") (")
buttons = [ [int(stry) for stry in but.split(",") ] for but in buttons]
volts = [int(v) for v in l.split("] (")[1][:-1].split(") {")[1].split(",")]
lights.append((goal, buttons,volts))
def getNext(s, buttons)-> str:
char_arr = [c for c in s]
for but in buttons:
char_arr[but] = "#" if char_arr[but] == "." else "."
return "".join(char_arr)
def process1(goal, buttons) -> int:
start_state = ("."*len(goal), None)
start_n= Node(start_state, None)
q = deque(start_n)
visited=set()
while q:
n = q.popleft()
state, move = n.value
if state not in visited:
if goal == state:
return len(n)-1
for but in buttons:
new_state = getNext(state, but)
nn = Node((new_state,but), n)
q.append(nn)
visited.add(state)
return 0
print(f"The answer to part1 is {sum([ process1(fixture, buttons) for fixture, buttons, volts in lights])}")
The answer to part1 is 449
In classic Advent of Code fashion, early design decisions made in Part 1 can render Part 2 intractable if care is not taken. As expected, a naïve extension of the Part 1 approach fails due to prohibitive runtime. I briefly experimented with A* in the hope that the existing code could be adapted, but it quickly became clear that this was the wrong tool for the problem.
After further investigation, Part 2 is best modeled as an integer linear programming (ILP) problem.
The solution below was authored by HyperNeutrino, who provides an excellent walkthrough of using Z3 here.
total = 0
for line in data:
match = re.match(r"^\[([.#]+)\] ([()\d, ]+) \{([\d,]+)\}$", line.strip())
_, buttons, joltages = match.groups()
buttons = [set(map(int, button[1:-1].split(","))) for button in buttons.split()]
joltages = list(map(int, joltages.split(",")))
o = z3.Optimize()
vars = z3.Ints(f"n{i}" for i in range(len(buttons)))
for var in vars:
o.add(var >= 0)
for i, joltage in enumerate(joltages):
equation = 0
for b, button in enumerate(buttons):
if i in button:
equation += vars[b]
o.add(equation == joltage)
o.minimize(sum(vars))
o.check()
total += o.model().eval(sum(vars)).as_long()
print(f"The answer for part 2 is {total}")
The answer for part 2 is 17848
Please comment!