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

Original Article ↗ Hacker News Discussion ↗

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.