Machine
Solvers

Part 1 — BFS toggle solver
Part 2 — ILP joltage solver
Reference — problem formulation

Part 1

Toggle solver via BFS

Lights start in some on/off state. Each button press flips the lights at specified positions. Goal: turn all lights off. BFS finds the minimum number of button presses. The {curly braces} are ignored here.

Part 2

Joltage solver via ILP

The {curly braces} are now integer targets. Each button press adds 1 to the values at specified positions. Goal: reach all zeros from the target vector. Solved as an Integer Linear Program via GLPK.js.

Reference

Problem formulation

The ILP that GLPK solves for each machine line in Part 2.

Variables $x_j \in \mathbb{Z}_{\geq 0}$ for each button $j = 1, \dots, k$ — the number of times button $j$ is pressed.

Objective — minimise total presses $$\min \sum_{j=1}^{k} x_j$$

Constraints — each joltage position must reach zero For each position $i = 1, \dots, n$, the presses of buttons that cover position $i$ must exactly equal the target $b_i$: $$\sum_{j \,:\, i \in S_j} x_j = b_i \qquad \forall\, i$$ where $S_j \subseteq \{0, \dots, n-1\}$ is the set of positions affected by button $j$.

Matrix form $$\min\; \mathbf{1}^\top \mathbf{x} \quad \text{s.t.} \quad A\mathbf{x} = \mathbf{b},\quad \mathbf{x} \geq \mathbf{0},\quad \mathbf{x} \in \mathbb{Z}^k$$ where $A \in \{0,1\}^{n \times k}$ with $A_{ij} = 1$ iff position $i \in S_j$, and $\mathbf{b} \in \mathbb{Z}^n$ is the joltage vector.

Example

For [.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) with $\mathbf{b} = [10,11,11,5,10,5]^\top$:

Constraint matrix A $$A = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$

Optimal solution: $\mathbf{x} = [5,\, 0,\, 5,\, 1]^\top$, giving a minimum of $\mathbf{1}^\top\mathbf{x} = \mathbf{11}$ total presses.