An archive of algorithmic curiosities
Given an array of integers representing the heights of pancakes in a stack, determine the minimum number of prefix reversals needed to sort the stack in ascending order. Each reversal flips the top k pancakes of the stack.
Navigate a grid where certain cells contain mirrors at 45° angles. A beam of light enters from a given edge — trace its path through reflections and determine which edge cell it exits from, or whether it enters an infinite loop.
Decode a message encrypted using a scheme where each letter maps to a consecutive prime number. Given only the encoded string of concatenated primes (without separators), reconstruct the original message. Multiple valid decodings may exist.
Given a connected multigraph G = (V, E), prove that an Eulerian circuit exists if and only if every vertex has even degree. Then, construct an algorithm to find such a circuit when one exists.
Assume G has an Eulerian circuit C. Each time C passes through a vertex v, it uses one edge to enter and one to leave — contributing 2 to deg(v). Thus all degrees are even.
Conversely, suppose all vertices have even degree. Start a walk from any vertex. Since every vertex has even degree, the walk can always continue until returning to the start.
If the closed walk W does not include all edges, find a vertex v in W incident to an unused edge. Start a new walk from v using only unused edges — this also closes.
Splice the new walk into W at vertex v. Repeat until all edges are included. By connectivity and the even-degree condition, this always terminates. ∎
Curated and maintained by the ppuzzle collective
Built with patience and peculiar devotion, MMXXVI
Every puzzle herein was once unsolved. Every solution, once unimaginable.
Finis