Day 10 was a real challenge, but mainly because I couldn't find a Haskell library that did what I wanted. (There was a side issue of work getting suddenly very busy, so I had to put AoC to one side for a week or so.)

The challenge sees us reading in a bunch of "machine specifications" that look like this (one per line):

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

The first part, [.##.], represents a pattern of lights, either on or off. The last part, {3,5,4,7} represents some joltage targets. The middle section is a set of button wiring specifications. For part 1, the buttons toggle the states of the lights. For part 2, the buttons increment some joltage counters. The button notation (1, 3) means this button activates items (lights or joltage counters) 1 and 3. The items are indexed from zero.

Parsing and data structures

The first step is to read the input into some convenient form. I went for simple, with a Machine being a record type.

type Button = [Int]

data Machine = 
  Machine { target :: [Bool]
          , buttons :: [Button]
          , joltages :: [Int]
          } deriving (Show, Eq)

Reading the input is made easy with the now-usual Attoparsec library.

machinesP = machineP `sepBy` endOfLine
machineP = Machine <$> targetP <* " " <*> buttonsP <* " " <*> joltagesP

targetP = "[" *> (many targetCharP) <* "]"
targetCharP = (True <$ "#") <|> (False <$ ".")

buttonsP = buttonP `sepBy` space
buttonP = "(" *> (decimal `sepBy` ",") <* ")"

joltagesP = "{" *> (decimal `sepBy` ",") <* "}"

Part 1

The first task is to find the minimum number of button presses to change the lights from all off (the starting state) to the given target state. Each button press will toggle the state of the specified lights.

I can use the fact that the lights are toggled to make some simplifications.

  1. Pressing a button twice is the same as not pressing it at all. That means I only need to track which buttons are pressed.
  2. Pressing button A then button B gives the same result as pressing B then A. That means I don't need to worry about the order in which buttons are pressed.

The first simplification gives me an easy way to record the state of a partial solution: I just track the pressed buttons as a set of button indices (actually I use a list, because that's a bit more convenient). The second simplification means I can generate partial solutions by pressing the largest button first (which means I don't generate duplicates of the same state to check).

I need a structure to hold the partial solution, another record.

data Solution = 
  Solution { machine :: Machine
           , current :: [Bool]
           , pressedButtons :: [Int] -- indexes of the buttons pressed
           } deriving (Show, Eq)

To find the solution, I do a breadth-first search through the trails of button presses, keeping track of an agenda of partial solutions. If the agenda is empty, return Nothing; if the first item in the agenda is the solution, return Just solution; otherwise, find the results of pressing an additional button and add them to the agenda.

solveMachine :: [Solution] -> Maybe Solution
solveMachine [] = Nothing
solveMachine (s:agenda) 
  | solvedMachine s = Just s
  | otherwise = solveMachine (agenda ++ (successors s))

Finding the successors of a partial state has two steps. First, I find the index of the highest button available to be pressed. Then I find all the button indices up to that and see what happens if I press them. Pressing a button (by index) involves finding all the lights and seeing if this button toggles their state.

successors :: Solution -> [Solution]
successors solution = fmap (pressButton solution) availableButtons
  where highestButton = if null solution.pressedButtons 
                        then length solution.machine.buttons
                        else minimum solution.pressedButtons
        availableButtons = take highestButton [0..]

pressButton :: Solution -> Int -> Solution
pressButton solution b = 
  solution { current = zipWith applyPress [0..] solution.current
           , pressedButtons = (b : solution.pressedButtons)
           }
  where button = solution.machine.buttons !! b
        applyPress i l = if i `elem` button then not l else l

That all needs a few functions to set things up and check a solution, and we're done!

part1 :: [Machine] -> Int
part1 machines = 
  sum $ fmap (length . pressedButtons . fromJust . solveMachineMain) machines

solveMachineMain :: Machine -> Maybe Solution
solveMachineMain machine = solveMachine [solution0]
  where solution0 = emptySolution machine

emptySolution :: Machine -> Solution
emptySolution machine = Solution machine offs []
  where offs = replicate (length machine.target) False

solvedMachine :: Solution -> Bool
solvedMachine solution = solution.machine.target == solution.current

Part 2

The problem changes from using the buttons to set a binary output to one where we set an integer-valued output. Restating the problem slightly, we have an objective (to minimise the number of button presses) subject to some constraints (the final values of the counters, affected by the button presses). This is a linear programming problem and the algorithms for finding solutions are well know, if a little laborious to code up.

Some people seem to have built their solution using a generic algebra solver like Z3. I thought I didn't need all that, so went hunting for a Haskell library that solved linear programming problems.

First I found the simplex-method library, which seemed to do the trick. Unfortunately, it didn't work for the sample problems. I think it got confused because one of them has multiple feasible solutions, only one of which is optimal.

Then I found the hmatrix-glpk library, that calls the GLPK linear programming tool from Haskell. That didn't work because I couldn't persuade it to specify the number of button presses to be integers. The library, working with real numbers, found some non-integer solutions that didn't fit the problem specification.

At this point, I decided the easiest way forward was to call GLPK directly. I could write out each problem specification to a file, call GLPK to solve the problem and write the solution to another file, then read that output file and extract the answer.

That's what I did.

Laying out the button wiring as a table, the first example machine looks like this:

counter 0 counter 1 counter 2 counter 3
button 0 x
button 1 x x
button 2 x
button 3 x x
button 4 x x
button 5 x x
total 3 5 4 7

Each row is the wiring for one button. Each column is the counters. The formulation of the linear programming task is to write a constraint for each column, defining the number of button presses needed for each counter.

This turns into the following input file for GLPK. The Subject to section has one line (constraint) for each counter. The rest of the file gives the objective and says that each button must be pressed a natural number of times.

Minimize
presses: b0 + b1 + b2 + b3 + b4 + b5
Subject to
l0: b4 + b5 = 3
l1: b1 + b5 = 5
l2: b2 + b3 + b4 = 4
l3: b0 + b1 + b3 = 7
Bounds
b0 >= 0
b1 >= 0
b2 >= 0
b3 >= 0
b4 >= 0
b5 >= 0
Integer
b0
b1
b2
b3
b4
b5

GLPK will read that input file and generate an output file, like this:

Problem:    
Rows:       4
Columns:    6 (6 integer, 0 binary)
Non-zeros:  10
Status:     INTEGER OPTIMAL
Objective:  presses = 10 (MINimum)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 l0                          3             3             = 
     2 l1                          5             5             = 
     3 l2                          4             4             = 
     4 l3                          7             7             = 

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 b0           *              1             0               
     2 b1           *              5             0               
     3 b2           *              0             0               
     4 b3           *              1             0               
     5 b4           *              3             0               
     6 b5           *              0             0               

Integer feasibility conditions:

KKT.PE: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

KKT.PB: max.abs.err = 0.00e+00 on row 0
        max.rel.err = 0.00e+00 on row 0
        High quality

End of output

The only part of this I need is the number on the Objective line.

Now I know the inputs and outputs, time to write something to handle them.

Writing the GLPK file

For writing the file, showProblem turns the machine specification into a String that can be written to the file, and tellProblem does the work. I decided to use a Writer monad to keep things a bit tidier. Each line of the file is one element of the Writer log, added with tell. Most of the sections of the file are pretty simple to implement, just involving writing something for each button.

type MachineWriter = Writer [String] ()

showProblem :: Machine -> String
showProblem machine = unlines $ execWriter (tellProblem machine)

tellProblem, tellConstraints, tellBounds :: Machine -> MachineWriter
tellOneBound, tellOneInteger :: Int -> MachineWriter

tellProblem machine =
  do tellObjective machine
     tellConstraints machine
     tellBounds machine

tellObjective machine =
  do tell ["Minimize"]
     let shownButtons = fmap (\n -> "b" ++ (show n)) $ take (length machine.buttons) [0..]
     let minTerm = intercalate " + " shownButtons
     tell ["presses: " ++ minTerm]

tellBounds machine =
  do tell ["Bounds"]
     let indices = take (length machine.buttons) [0..]
     forM_ indices tellOneBound 
     tell ["Integer"]
     forM_ indices tellOneInteger

tellOneBound n =
  do tell [("b" ++ (show n) ++ " >= 0")]
tellOneInteger n =
  do tell [("b" ++ (show n))]

Writing the constraints is the more complex part, but follows a similar logic to pressing a button in part 1.

In tellConstraints, I pair up the required joltages with the indices of the counters, and pass each pair to tellOneConstraint to fill out one constraint line. tellOneConstraint pairs up the buttons with indices, then removes the buttons that don't affect this counter. The button indices turn into the left hand side of the constraint, and the required joltage turns into the right hand side.

tellConstraints machine =
  do tell ["Subject to"]
     mapM_ (tellOneConstraint machine) $ zip [0..] machine.joltages

tellOneConstraint machine (nTarget, j) =
  do let presentButtonNs = fmap fst $ filter (\(_, b) -> nTarget `elem` b) $ zip [0..] machine.buttons
     let shownButtons = fmap (\n -> "b" ++ (show n)) presentButtonNs
     let lhs = intercalate " + " shownButtons
     tell ["l" ++ (show nTarget) ++ ": " ++ lhs ++ " = " ++ (show j)]

Reading the GLPK output

Reading the GLPK output isn't exactly clever. I read each line in turn, converting each one into a Maybe Int. If the line starts with Objective, I extract the number of presses; everything else gets turned into Nothing. The composition of (head . catMaybes) pulls out the first just objective line.

solutionP = (head . catMaybes) <$> solutionLineP `sepBy` endOfLine
solutionLineP = objectiveP <|> junkP
objectiveP = Just <$> ("Objective:  presses = " *> decimal)  <* " (MINimum)" 
junkP = Nothing <$ AP.takeWhile (not . isEndOfLine)

Putting it all together

Solving the joltage-related presses for one machine has to sit in the IO monad, as it calls an external process. The logic, though, is a straightforward series of steps to create the input file, write it out, all GLPK, then read and parse the input. 

solveJoltage :: Machine -> IO Int
solveJoltage machine = 
  do let problem = showProblem machine
     writeFile "machine.lp" problem
     (_, _, _) <- readProcessWithExitCode "glpsol" ["--lp", "-o", "machine.out", "machine.lp"] ""
     text <- TIO.readFile "machine.out"
     let soln = successfulParseOut text
     return soln

Finally, it's all done!

Code

You can get the code from Codeberg.