Here's a puzzle game. I call it Reverse the List of Integers

Original Article ↗ Hacker News Discussion ↗

A small math puzzle about reversing a list of integers using only “split” and “combine” operations, under tight constraints on duplicates and maximum values, turns out to have surprisingly rich structure. Commenters explore which starting lists are solvable, identify whole families of impossible cases, and share brute-force, dynamic programming, SAT/SMT, Prolog, and graph-search approaches to find minimal move sequences. The problem also inspires several browser implementations and prompts debate over its suitability as a coding interview question, given that many seemingly simple inputs are unsolvable or require long solution paths.

Rule Clarifications and Constraints

  • Start from a list of positive, distinct integers; goal is to reach its reverse using:
    • Split: replace one integer by two smaller positive integers that sum to it.
    • Combine: replace two adjacent integers by their sum.
  • Additional constraints:
    • No integer may exceed the original maximum.
    • No move may create a duplicate value anywhere in the list.
  • Later clarification: only positive integers (no zero, no negatives) and combining is on adjacent elements only.
  • Some ambiguity noted early (e.g., whether negatives or non-adjacent operations are allowed), but consensus converges on the stricter, positive/adjacent interpretation.

Solvable vs Unsolvable Configurations

  • Some lists are provably unsolvable:
    • Examples: [3,2,1], [2,1], [3,2]; also any list containing all integers in a consecutive range [1..n] (in any order).
    • Intuition: with a full consecutive set, any split or merge either creates a duplicate or exceeds the max.
  • Certain patterns like [n, n+1] are unsolvable for small n, but for larger n variants like [n, n-1] are shown solvable with constructive sequences.
  • More complex classes of unsolvable lists are discussed, including those with “no gaps” or too little “wiggle room” between values.

Example Solutions and Difficulty

  • For the canonical example [7,5,3], multiple minimal 6‑step solutions are found (and confirmed via SAT/SMT / search).
  • Exhaustive search up to certain maxima reveals “hardest” instances:
    • For max value 6: [1,6,3] needs 14 moves.
    • For 7: [5,4,1,2,7] needs 26 moves.
    • Reported worst cases grow quickly with the maximum value (e.g., over 100 moves for higher maxima).

Algorithmic Approaches

  • Modeled as a graph search problem where states are lists and edges are valid moves.
  • Approaches mentioned:
    • Breadth-first search (including bidirectional) to guarantee minimal solutions.
    • Dynamic programming / memoization to avoid recomputing visited states.
    • SAT/SMT encodings and Prolog programs for automated solving and verifying minimality.
    • Heuristic search ideas (A* with length or subsequence-based heuristics).
  • Debate over what “dynamic programming” precisely means versus simple memoization.

Tools, Visualizations, and Meta Discussion

  • Several browser-based games and visualizers were built, some initially with bugs around duplicate detection, later fixed.
  • Alternative physical/visual analogies (e.g., Towers of Hanoi–like pegs, gutters with rods) are proposed but criticized as imperfect.
  • Many note this would appear in coding interviews; reactions are mixed:
    • Some enjoy it as a neat benchmark.
    • Others dislike context-free puzzles for interviews and argue for more realistic, collaborative problem-solving formats.