McNugget Graph
by marimo team
Step through a breadth-first search of the McNugget problem and watch the reachable totals fan out.
About this notebook
This notebook explores McNugget sums. These are the totals you can reach by adding boxes of fixed sizes. The default box sizes are 6, 9, and 20. The notebook uses marimo, the wigglystuff library, and a deque from the Python standard library. A breadth-first search finds every total up to a limit. The wigglystuff GraphWidget draws the totals as nodes and the box additions as arcs.
You set the box sizes in a text field and the upper limit with a slider. A PlaySlider from wigglystuff steps through the search one move at a time. At each step you read the current action, the count of reachable totals, and the remaining queue. The notebook also lists the totals it cannot reach yet. When you hover a node, the notebook shows the shortest path from 0 to that total.
Two checkboxes change the graph colors. One checkbox colors the arcs by box size. The other checkbox colors the nodes by their number of inbound arcs. The search itself runs with a queue and a visited set, so each total enters the queue once. The graph updates its nodes and edges together inside a hold_sync block on each step.
