# Algorithm Arena — core problem workbench

Reviewed 18 October 2026. This app teaches 14 algorithms across six problem families. It is a bounded, deterministic learning tool, not an exhaustive catalog of computer science problems or a CPU benchmark.

## Research and design decisions

Primary references:

- [Princeton Algorithms: elementary sorts](https://algs4.cs.princeton.edu/21elementary/) and [the authors' BFS implementation](https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/BreadthFirstPaths.java): compare/exchange accounting and queue-based shortest paths inform the operation counters and route lessons.
- NIST Dictionary of Algorithms and Data Structures: [bubble sort](https://xlinux.nist.gov/dads/HTML/bubblesort.html), [merge sort](https://xlinux.nist.gov/dads/HTML/mergesort.html), [quicksort](https://xlinux.nist.gov/dads/HTML/quicksort.html), [binary search](https://xlinux.nist.gov/dads/HTML/binarySearch.html), [linear search](https://xlinux.nist.gov/dads/HTML/linearSearch.html). These support the core strategies, binary-search sorted-input precondition and deterministic quicksort worst case.
- [Princeton shortest-path material](https://algs4.cs.princeton.edu/44sp/index.php) and [A* assignment FAQ](https://coursera.cs.princeton.edu/algs4/assignments/8puzzle/faq.php): nonnegative route costs, consistent/admissible estimates and ending when the goal is removed from the frontier support the pathfinding implementation.
- [MIT 6.046 coin-change recitation](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/d187472426117c2ebec700a22c209b3f_MIT6_046JS15_Recitation5.pdf): unlimited supply, zero base case and the minimum-over-last-coin recurrence inform the coin table.
- [MIT 6.006 knapsack lecture](https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/48d1e783bd1a50c1851bbb45887c0821_wFP5VHGHFdk.pdf): taking versus skipping an item informs the 0/1 DP table. Reading the previous row prevents item reuse.
- [MIT 6.046 interval scheduling](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/ff2a7015ff913fc01f0381d8f5126a9a_MIT6_046JS15_lec01.pdf): earliest-finish selection maximizes compatible activity count. This is not weighted scheduling.
- [Google OR-Tools N-Queens](https://developers.google.com/optimization/cp/queens): row, column and diagonal constraints support the puzzle. Our solver uses simple first-solution backtracking, not OR-Tools propagation.

The interface and visual encodings are our design choices. Orange identifies the current decision and primary controls. New experiments start in actual 3D: cards for arrays, a miniature town for routes, coins and a backpack for dynamic programming, chess pieces for queens, and activity blocks for scheduling. Every family retains its 2D bars, map, table or diagram for detailed reading. Both views use the same input and recorded algorithm state; the camera and animation do not change the solution.

## Predictions to test

- Early-exit bubble sort needs three value comparisons for [1,2,3,4], but descending input requires more work. Last-pivot quicksort has a quadratic case on sorted/equal inputs.
- Binary search halves a sorted candidate range. It cannot safely discard half an unsorted list; validation rejects such input without silently rearranging it.
- A route with fewer moves can cost more. BFS ignores terrain prices; Dijkstra and A* minimize cost. With four-way moves costing at least 1, Manhattan distance is a consistent lower bound for A*.
- Coins [1,3,4] making 6 need two coins (3+3); largest-first would choose three. Coins [4,6] cannot make 7; zero needs no coins.
- A backpack can favor a combination over the individually highest-value item. Zero capacity selects nothing.
- A safe queen placement can still lead to a later dead end. Undoing a choice is necessary to explore another branch.
- For equally valued activities on one resource, earliest finish leaves room for a maximal number of later activities. Activities with touching endpoints are compatible; different rewards require another model.

## Implemented models and bounds

| Family | Strategies | Editable bounds |
| --- | --- | --- |
| Sorting | Bubble, adjacent-swap insertion, selection, merge, last-pivot quicksort | 1–24 integers, 0–99 |
| Searching | Linear, binary | Same array bounds; target 0–99; binary requires ascending order |
| Pathfinding | BFS, Dijkstra, A* | Default 7×5 learning board; larger 17×11 presets and named experiments; walls or cost 1–9, four-way moves; bounded trace boards up to 25×17 |
| Dynamic programming | Minimum coin change, 0/1 knapsack | ≤6 denominations 1–20, amount ≤30; ≤6 items with weights 1–12, values 0–30, capacity ≤20 |
| Backtracking | First-solution N-Queens | Board size 4–8 |
| Greedy | Earliest-finish interval scheduling | ≤10 activities, integer endpoints 0–24 |

Sorting comparisons count value-to-value tests, not loop checks. Swaps exclude self-exchanges; main-array writes count two per swap or the complete merged range. Temporary merge-buffer writes are excluded. Merge copy-back is displayed as one complete range update so each visible array remains a permutation. Search probes count inspected positions; binary precondition validation is excluded from that counter and noted separately in its complexity label. Duplicate linear matches return the first index; binary returns any matching index.

BFS uses a FIFO queue with a head cursor. Dijkstra/A* use a binary minimum heap and deterministic insertion-order tie breaks. Stale priority entries are skipped. The start cell is free; completed route costs add entry prices. A* uses g+h with Manhattan h, so it needs no reopening under this grid's assumptions. Queue/heap work and rendering are not presented as elapsed performance. Visited counts settled cells; frontier counts cells still awaiting exploration, which may remain when a goal is reached.

DP displays all subproblem values, with uncomputed cells blank and unreachable values as infinity. Coin reconstruction returns a denomination list; knapsack reconstruction returns original item IDs. Queens stops at the first valid board. Scheduling sorts by finish time while retaining original activity labels. Complexity labels describe algorithm work/space, excluding retained replay snapshots; numeric-capacity DP is pseudo-polynomial.

## Persistence, access and verification

The last explicitly saved problem uses `cm-algorithm-arena-v2`. Completed-lesson IDs and the explicitly captured result baseline have separate keys. Input validation precedes a committed setup change. Baselines survive input edits. Playback pauses when hidden. No external accounts or uploads are required.

The accessible state table exposes all values, including columns that the mobile DP drawing windows out. The CSV includes both strategies' complete frames, messages and counts when comparing. A playback beat is one recorded decision per strategy, not necessarily the same number of primitive operations.

Tests independently verify sorted permutations and exhaustive small arrays, counters and boundaries, heap route results and optimality against an independent solver, coin DP against BFS, knapsack and schedules against exhaustive subsets, and queen constraints for every supported size. Browser checks cover editable inputs, rejected binary inputs, comparison, reverse/seek, predictions, persistence, 2D/3D editing and camera controls, desktop/phone/tablet layouts and both themes.

## Plain-language learning layer — 2026-10-16

The University of Canterbury's [CS Unplugged sorting activities](https://classic.csunplugged.org/activities/sorting-algorithms/) and [searching cards](https://www.csunplugged.org/en/resources/searching-cards/) use familiar physical objects for algorithm activities. This supports using cards and numbered everyday objects as a bridge to the existing visual states. The stories and explanations in this app are original; no worksheets or media were copied.

Design prediction (not a measured learning outcome): a concrete mission, a small starting input, and one action explained before advancing should make the first run easier to follow than a technical trace alone. Learner testing is still needed to assess understanding. The first screen starts with six small values; every lesson has a Start small preset, and route lessons begin on a 7×5 map. Manual Next step remains available; automatic playback defaults to four seconds per decision.

Every one of the fourteen strategies now has a distinct familiar example, an explicit mapping from the drawing to that example, a mission, an experiment to try, and a small glossary. Each replay frame receives a pure, state-derived explanation of what happens, why, and the next action. Upcoming hints describe actions without presenting future results as already true. Array stories count positions from one and explicitly map them to the chart's zero-based index labels.

Simple recipes track the same line as the original pseudocode. Full code, assumptions and complexity remain in Go deeper. When comparing, the explanation selector follows either lane's clamped frame without changing the shared replay. Quiz answer positions vary deterministically. CSV exports retain the original columns and append simple title, action, reason and next action. Models, saved setups, baseline keys and progress keys are unchanged.

Verification: 70 automated tests pass, including every emitted guide branch, value-dependent descriptions, unchanged input/frame state, valid recipe links, unreachable goals and missing values. Browser checks exercised all fourteen stories and small presets, both comparison guides, expanded technical detail, backward/forward replay, a no-solution coin case, 3D routes, and 320px phone / 820px tablet / desktop layouts. Themes and page overflow were checked. This verifies implementation behavior, not educational effectiveness with children.

## Animated 3D cards and experiment library — 2026-10-16

Design prediction (not a measured learning outcome): showing individual cards lift, exchange places and settle should help learners connect a comparison with the resulting movement. Keeping each card's identity visible should make repeated numbers and stable versus unstable sorting easier to follow. This extends the physical-card teaching approach above; the perspective scene, artwork and animation choices are original interface design decisions.

Sorting and searching start with a true 3D card table. Each card has depth, a numbered face, a permanent original card ID and a shadow. The camera supports orbit, pan, zoom and reset using pointer, touch or keyboard controls. Number cards, ticket cards and robot badges provide three procedural art styles; rows and a fanned arrangement change presentation without changing the algorithm. The existing 2D bars remain available and use the same replay frame.

Every array frame includes a frozen `ids` list aligned with `values`. IDs start at the input positions and travel with their values through swaps and merge buffers, including equal-valued cards. A merge moves the displayed cards only when the completed range is copied back. Stable algorithms retain equal-card order; selection sort and last-pivot quicksort reveal their actual exchanges instead of reconstructing identity from matching numbers. Each rebuild receives a separate run ID so new inputs appear immediately rather than animating from unrelated old cards.

Cards can be selected in the scene or through a labelled HTML selector. The inspector reports the card's original ID, current number, one-based spot, zero-based index and current status. Changing a selected number edits that original input card and restarts both comparison strategies with the same validated values. Edits that violate binary search's sorted-input requirement leave the prior experiment intact and explain the problem. The selector and number input remain usable in 2D and when 3D is unavailable.

Animation is optional, with gentle, quick and slow-motion choices. Motion follows the recorded steps; it does not alter decisions, counters or results. Fast playback shortens transitions to fit the playback beat. Scrubbing, restarting, changing inputs and returning from a hidden 3D view snap to the current frame. Reduced-motion preference disables movement. Hidden scenes and hidden documents stop animation, and a settled scene does not keep an idle animation loop. If WebGL cannot start, the same state remains available as 2D bars with a clear explanation. Saved setups now also retain card style, layout and motion settings while preserving the existing setup version, progress and baseline keys.

The experiment library contains **41 distinct named packs**: 8 sorting, 8 searching, 5 route, 5 coin, 5 backpack, 5 queen and 5 scheduling challenges. Strategies within a family share the relevant packs, making comparisons repeatable. Each pack includes a familiar situation, a prediction question and editable input. Cases include duplicate and zero cards, missing search targets, costly shortcuts and blocked routes, impossible coin totals, limited backpacks, larger queen boards and overlapping activities. All search packs start sorted so either search strategy can use the same input. This is a curated set of examples, not a claim to cover every educational problem.

Automated verification for this expansion: **97 tests pass** across the complete Algorithm Arena suite. Added checks cover identity permutations and value correspondence, stable and unstable duplicate order, merge copy-back and rewind, animated positions and retargeting, fast playback, no idle animation loop, 24-card mobile geometry, reduced motion, hidden-scene behavior, all art styles, inspector edits in either comparison lane, invalid binary edits, saved card settings and every supported algorithm/pack pairing. The shared catalog check also passes: **11 unique app routes, 149 local resource/link references and unique IDs on all 8 new pages**. These checks validate implementation behavior; they do not measure learning outcomes or GPU performance on every device.

## Animated worlds for every problem family — 2026-10-18

Design prediction, not a measured learning outcome: recognisable objects and visible try/keep/undo movements should help learners connect an algorithm's decision to the state it changes. The object worlds extend the physical-object teaching approach described above. The existing Princeton, MIT and OR-Tools references support the algorithm rules; they do not establish the effectiveness of these particular 3D designs. Learner testing is still needed. The 2D views remain available for checking dense tables and precise relationships.

All scene builders read the current model frame and validated inputs. They produce stable object identities, positions, numeric labels and an accessible description for the shared 3D renderer. They do not infer an answer from animation progress or parse explanatory prose to decide what happened. Moving to another step, rewinding or choosing a comparison lane therefore shows the actual corresponding state. Decorative scenery and object proportions do not introduce extra model quantities.

- **Routes:** endpoint symbols follow the story: school/playground for BFS, depot/delivery point for Dijkstra, and character/home for A*. Red barriers are walls; taller tiles have higher entry costs. Cyan rings mark the frontier and checked marks identify settled cells. The moving orange spotlight shows the cell being checked, **not a traveller following a route**: consecutive search expansions need not be adjacent. Only the recorded predecessor path is connected as the final route. Its move count and entry-cost sum exclude the start's price, as in the underlying model. A blocked route remains an explicit no-route result. Height does not add climbing, diagonal movement or a third movement dimension.
- **Backpacks:** labelled objects retain their original item IDs, weights and values. During table-building, take/skip displays describe the current subproblem: its available item prefix and smaller capacity. Those hypothetical choices are distinct from the final pack. Items enter the backpack only when their IDs appear in the model's reconstruction state. The packed-weight meter and value total count only those recovered items, including the valid empty pack at zero capacity. Box size is decorative; the numeric weight and value labels are authoritative.
- **Coins:** numbered stones represent amounts, with separate not-yet-solved, current-best, solved-minimum and unreachable states. Supply coins indicate unlimited denomination copies. The recovery tray remains empty while the DP table is built, then shows exactly the recorded recovered coins and their running total. The final minimum is not replaced by a greedy guess. Zero needs no coins; an unreachable target produces no invented combination.
- **Queens:** one stable chess-queen object belongs to each row. It moves between a numbered board square and the bench. A lifted translucent candidate is a try, a solid placed queen is an accepted local choice, and an undo returns that row's queen to the bench. The unsafe square is crossed; beams connect only the attacking squares listed in the frame's conflicts to the candidate. A placement is not presented as a complete solution until all rows are safely filled. The view retains the solver's first-solution, left-to-right search order.
- **Schedules:** activity letters retain their original identities on fixed lanes. A common numeric time ruler controls block start, end and duration; finish-order numbers show the order of inspection. The current choice rises, while labels and crossing marks distinguish accepted and overlapping activities. The availability marker comes from the recorded finish time of the last accepted activity. Touching endpoints remain compatible. Time units describe the input schedule, not real-time playback, and the objective remains maximum activity count rather than total duration or reward.

New experiments use 3D by default while explicitly saved view choices remain available. Orbit, pan, zoom and reset work with pointer, touch and keyboard controls. Camera fitting uses scene bounds and adapts when the viewport changes. Numeric captions, the HTML state table, simple explanations and CSV export remain available independently of the 3D canvas. Route painting and its row/column controls edit the same board in either view.

The motion controls now apply to all animated worlds. Stable IDs let objects move to their next recorded positions or return during undo; motion can be disabled or slowed without changing any decisions. Transitions fit the playback beat, and explicit seeking, restarting or replacing inputs snaps to the requested state. Reduced-motion preferences disable transitions. Hidden scenes and hidden documents stop animation work, and finished transitions do not run a perpetual drawing loop. If WebGL cannot initialise, the existing 2D visualization, inputs, explanations and numerical data remain usable with a clear fallback message. Both light and dark themes retain the orange interface accent and labelled state distinctions.

Verification for this expansion includes model-to-scene checks for exact route paths and costs, frontier/checked state, DP take/skip values and recovered items, coin recovery totals, every supported queen size, and scheduling endpoint/overlap cases. Scene tests also cover finite bounded geometry, stable identities, transition lifecycle, camera fitting, reduced motion and hidden-scene behavior. Browser acceptance includes forward/back/seek, both views, camera and route editing, light/dark themes, and phone/tablet/desktop layouts. These checks concern implementation and presentation; they do not establish learning gains or performance on every GPU.

Final local validation on 2026-10-18: all 146 Algorithm Arena tests and the shared catalog checks passed. Browser checks covered desktop, 820px tablet and 390px phone layouts, both themes, live route editing, comparison paths, queen conflicts/undo, backpack recovery and synchronized 2D/3D steps. No browser warnings or errors were reported during this session.

## Choosing a route goal — 2026-10-18

Route lessons now put two explicit goals beside the map controls: **Fewer moves** selects breadth-first search; **Lower cost** selects Dijkstra, or retains A* when it is already selected. The explanation separates a move from the effort of entering a tile. A tile marked 4 and a tile marked 9 each count as one move for BFS. Dijkstra and A* minimise the sum over the whole route, not the price of the next tile alone. Equal-length BFS routes keep the first discovered path; it need not be the cheapest. Explanations do not promise that switching goals will always produce a different route or save effort.

Switching goals pauses and restarts the search on the same painted board, retaining the 2D/3D view. Compare both goals runs the two objectives on identical inputs. Each lane repeats its goal above the drawing and, when a path exists, shows a state-derived entry-cost addition below its results. The start remains free. The terrain selector explains that it changes the painting value; existing tiles change only when painted or edited with Apply to cell. The controls stay hidden outside route lessons and derive their state from the current or loaded strategy.

Verification: **155 automated tests pass**, including goal switching during playback, retained painted terrain and views, opposite-goal comparison, A* selection, saved setup loading, and painting-value changes without changing the map. Regression examples cover equal-length routes with different costs, uniform costs with no savings, and a painted muddy shortcut where BFS takes 6 moves at cost 42 while Dijkstra/A* take 8 moves at cost 8. Browser checks cover both goals, the completed per-lane effort breakdown, 2D view retention, comparison and the 390px phone layout. These checks verify behavior and presentation, not measured learning outcomes.

## Example selection and custom mazes — 2026-10-19

Example buttons now reflect the active choice with an orange fill, checkmark and `aria-pressed`. Experiment-library cards also identify the loaded challenge. A changed manual input clears an unrelated preset selection; painting a route makes it a custom maze. Source selection follows route-goal and view changes and is retained in saved setups.

Only **Custom maze** shows the maze-number field and **Generate maze** action. Its number is independent of the number-card shuffle seed. Fixed route examples load immediately and ignore pending custom-number edits. Generating applies the validated number to both comparison lanes; invalid numbers leave the current board intact. Edited mazes explain that generation will replace their painted changes. Route saving stores the displayed board without generating from a pending number, while older saved boards remain loadable as custom mazes.

Verification: all **30 interaction integration tests** and the shared catalog checks pass. Eight added regressions cover source highlights, deterministic generation, invalid drafts, independent seeds, painting, goal/view changes, library choices and saved/legacy boards. Browser review confirmed the selected controls and generation at desktop and 390px phone size, no horizontal page overflow on the phone, both themes and no reported browser warnings or errors. These are interface-behavior checks, not learning-outcome measurements.

## Correctness and explanation review — 2026-10-21

The model did not change. An independent fuzz check compared every strategy with textbook results and brute-force solvers: 3,000 random arrays (including many duplicates) for the five sorts and two searches; 1,500 random boards with walls and costs for BFS, Dijkstra and A*; 800 coin, 800 knapsack and 800 schedule inputs; and every queen size. All results agreed. Selection sort always made n(n − 1)/2 comparisons. Bubble and insertion sort made one swap per inversion. Bubble, insertion and merge kept equal values in order. Binary search never used more than ⌊log₂ n⌋ + 1 probes. Dijkstra and A* found the optimal cost, and BFS found the fewest moves.

Explanation fixes:
- **Dijkstra wording was wrong for this map.** Every route into a square pays the same entry price for that square, and Dijkstra settles squares in cost order. The first total a waiting square receives is therefore already its best. The earlier text said that a nearby square could later get a better total, which never happens here. A* orders squares by g + h, so it can improve a waiting square. Its steps now report how many waiting squares got a cheaper total.
- Queen clashes now name the attacking line for each queen (same column or same diagonal).
- The first reachable coin answer is called "A first way to pay", not "A better way".
- Binary search mentions two middle spots only when the range has an even length. A one-book range says it is the last possible spot.
- Plurals were fixed ("among 1 number", "1 number comparison"). A single-item sort now says no comparison was needed. The merge step no longer mentions "bars" when cards are shown.

Interface fixes: number lists accept trailing or leading separators and semicolons. The specific error messages for empty, negative, decimal and non-numeric entries keep the previous experiment. On desktop, the keyboard shortcuts ← / → (or , / .) step and P plays or pauses. They do not take over keys from form fields or the 3D scenes. The light-theme heading accent now uses a darker orange (#C85A00) to meet large-text contrast. Storage keys and saved formats are unchanged.

Verification: **172 automated tests pass**, including new regressions for textbook counts on exhaustive small inputs, edge cases, wording, A* improvements, the Dijkstra no-improvement property, input parsing and keyboard shortcuts. Browser checks at 390×844 and 1440×900 in both themes found no horizontal overflow, axe WCAG A/AA violations or console errors, apart from the offline font request.