Bug Byte

Jane Street’s Bug Byte is a weighted-graph labelling puzzle with an embedded word-search payoff. The setting is a connected graph on eighteen nodes and twenty-four edges; the goal is to assign to each edge a distinct integer weight from $\{1, 2, \ldots, 24\}$ subject to sum-at-node and path-weight constraints, after which the shortest-weight path between two distinguished nodes spells out a secret word under the mapping $1 \mapsto A$, $2 \mapsto B$, $\ldots$, $24 \mapsto X$.

Two kinds of nodes carry constraints. The first kind (white with a green border, labelled with an integer $M$) asserts that the sum of all edges directly incident to the node equals $M$. The second (solid green, labelled with one or more integers $N_1, N_2, \ldots$) asserts that for each $N_i$ there exists a simple (non-self-intersecting) path starting from the node whose edge-weight sum equals $N_i$. The puzzle also supplies four edge weights fixed in advance ($7, 12, 20, 24$), which removes those four values from the pool of twenty remaining unknowns.

The puzzle was distributed by Jane Street’s recruiting site in $2024$; it illustrates the now-common genre of “graph puzzles” whose constraint structure is almost designed to be fed into CP-SAT. The unknowns number $20$, the direct-sum constraints number $10$, the path constraints involve seven starting nodes with a total of ten path-sum conditions, and the feasibility problem is decided in about $20$ milliseconds on a standard laptop.

The puzzle graph

The graph is displayed in Figure 11.1. The two stars (above and below) mark the endpoints between which the shortest path will be read. Nodes carrying a single number in green indicate a sum-at-node constraint; nodes in green with multiple numbers stacked indicate multiple path-sum conditions from that node.

The programming model

Variables

Let $w_0, w_1, \ldots, w_{19}$ be the integer unknowns ranging over $\{1, \ldots, 24\} \setminus \{7, 12, 20, 24\}$, all-different. Each edge of the graph is either labelled by a $w_i$ (twenty such edges) or by a fixed literal (four such edges: the weights $7$, $12$, $20$, $24$).

Direct-sum constraints

For each labelled white-green-bordered node, equate the sum of incident edge weights to the prescribed total. In the classical Bug Byte instance there are ten such equalities, e.g. $$\begin{align*} w_0 + w_1 & = 17, \\ w_0 + w_2 & = 3, \\ w_3 + w_4 + w_6 + w_7 & = 54, \\ \vdots \end{align*}$$ (One obtains the full list by reading off each labelled node’s neighbours and summing.)

Path-sum constraints

For each green node with labels $N_1, \ldots, N_k$, enumerate all simple paths starting from that node. Each $N_i$ must equal the edge-weight sum of some such path. Since there is no a priori bound on path length, the enumeration is finite only because simple paths in a graph of $18$ nodes have length at most $17$; typical Bug Byte instances have low-hundreds of simple paths per starting node, well within CP-SAT’s reach.

To encode “$N_i$ equals some path’s sum” in CP-SAT, introduce a Boolean $b_p$ per candidate path $p$, set $b_p \Leftrightarrow \sum_{e \in p} w_e = N_i$ via an $\texttt{OnlyEnforceIf}$ pair, then require $\bigvee_p b_p$.

A solver in fifty lines

from ortools.sat.python import cp_model
import networkx as nx

def solve(edges, sum_nodes, path_nodes):
    m = cp_model.CpModel()
    w = [m.NewIntVar(1, 24, "") for _ in range(20)]
    m.AddAllDifferent(w)
    for v in (7, 12, 20, 24):
        for i in range(20):
            m.Add(w[i] != v)

    def weight(lbl):
        return lbl[1] if lbl[0] == "fix" else w[lbl[1]]

    for refs, total in sum_nodes:
        m.Add(sum(weight(r) for r in refs) == total)

    G = nx.Graph()
    for u, v, lbl in edges:
        G.add_edge(u, v, lbl=lbl)

    for start, target in path_nodes:
        bools = []
        for node in set(G.nodes) - {start}:
            for p in nx.all_simple_paths(G, start, node):
                exprs = [weight(G[a][b]["lbl"])
                         for a, b in zip(p, p[1:])]
                b = m.NewBoolVar("")
                m.Add(sum(exprs) == target).OnlyEnforceIf(b)
                bools.append(b)
        m.AddBoolOr(bools)

    s = cp_model.CpSolver()
    s.Solve(m)
    return [s.Value(x) for x in w]

Reading the answer

With the edge weights filled in, the shortest weighted path from one star to the other is computed by any standard routine (Dijkstra’s algorithm, for instance). The path in Figure 11.1 has six edges with weights $12, 9, 14, 11, 5, 4$. Mapping $1 \mapsto \mathrm{A}$ onwards gives $\mathrm{LINKED}$ — appropriate for a puzzle distributed by a recruiting site that lives on the network.

Sources. Bug Byte was released by Jane Street as part of their public puzzle series in $2024$; the original graph and its constraints appear on janestreet.com/bug-byte. The puzzle is a cleanly packaged exercise in graph labelling by constraint programming, and a gentle example of the pattern “enumerate simple paths, then disjunctive equality on sums” that recurs in Jane Street’s later Hall of Mirrors and Altered States puzzles. The ingredient that makes Bug Byte distinct among edge-weight puzzles is the path-sum disjunction — a constraint form that is awkward for straight mixed-integer programming but natural in CP-SAT with reified equality and Boolean disjunction.