Search Results

Documents authored by Williams, Aaron

Document
DOI: 10.4230/LIPIcs.FUN.2026.22
The Quaternary Gray Code and Ziggu Puzzles

Authors: Madeleine Goertz and Aaron Williams

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
We investigate solutions to the new "Ziggu" family of sequential puzzles including Ziggurat, Zigguflat, Zigguhooked and so on. These puzzles have p pieces that form m mazes. We encode the state of each puzzle as a quaternary number (i.e., base 4) with n = m+1 digits, where each digit gives the horizontal or vertical position in one maze. For example, the commercial version of Zigguflat has p = 6 pieces connected into m = 4 mazes and its state requires n = 5 digits to describe. We show that the number of states on a shortest solution is 6 ⋅ 2ⁿ - 3n - 5 (Oeis A101946). There is only one solution of this length, and it is generated from the start configuration by a simple algorithm: make the leftmost modification that doesn't undo the previous modification. Replacing "leftmost" with "rightmost" instead generates the unique longest solution that visits all (3^{n+1} - 1)/2 states (Oeis A003462). In this way, Ziggu puzzles can be viewed as 4-ary, 3-ary, or 2-ary puzzles based on how the number of state encodings, valid states, or minimum states grow with each additional maze. Classic Gray code puzzles (e.g., Spin-Out) provide natural and illuminating comparisons. These puzzles with p pieces typically have 2^p (Oeis A000079) or ⌊ 2/3 ⋅ 2^p ⌋ (Oeis A000975 [Stockmeyer, 2017]) states on their unique (shortest) solution, and at most one modification doesn't undo the previous modification. The states visited in a Gray code puzzle solution follow the well-known binary reflected Gray code. We show that Ziggu puzzles instead follow the quaternary reflected Gray code. More specifically, the shortest and longest solutions are both sublists of this order, meaning that some quaternary words are skipped over but the relative order of the remaining words does not change. These results show how to solve Ziggu puzzles from the start configuration. To help solve the puzzle from an arbitrary configuration we provide O(n)-time comparison, and successor algorithms, which give the relative order of two states and the next state, respectively. While Gray code puzzles have simpler recursive descriptions and successor rules, a Ziggu puzzle has a much simpler loopless algorithm to generate its shortest solution than the Gray code puzzles do. The two families are also intimately related as they have the same comparison function.
Cite as

Madeleine Goertz and Aaron Williams. The Quaternary Gray Code and Ziggu Puzzles. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{goertz_et_al:LIPIcs.FUN.2026.22,
  author =	{Goertz, Madeleine and Williams, Aaron},
  title =	{{The Quaternary Gray Code and Ziggu Puzzles}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{22:1--22:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.22},
  URN =		{urn:nbn:de:0030-drops-257413},
  doi =		{10.4230/LIPIcs.FUN.2026.22},
  annote =	{Keywords: Puzzle, Ziggu, Ziggurat, Zigguflat, Gray Code, Loopless Algorithm}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.23
Pyramid Schemes for Eating M&Ms: Enumeration, Generation, and Gray Codes

Authors: Elizabeth Hartung, Brett Stevens, and Aaron Williams

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
Consider the following problem. You have a rainbow pyramid of M&Ms with n rows. For example, when n = 4 you may have one red, two orange, three yellow, and four green {inline.pdf}. You want to eat n of the M&Ms in such a way that the remaining M&Ms can be rearranged into a rainbow pyramid with n-1 rows. Two approaches are distinct if a different number from a particular row are eaten. In other words, we only care about the multiset of row frequencies (or colours) that are eaten and not the order in which they are eaten. One solution eats one M&M per row (e.g., 1234 → {inline.pdf}). Another eats the entire bottom row (e.g., 4444 → {inline.pdf}). How many different solutions are there? We show that the answer is 2^{n-1}. Furthermore, each solution can be naturally encoded with combinatorial objects enumerated by 2^{n-1} including binary words of length n-1, compositions of n, and subsets of [n-1]. Less obviously they are encoded by M&M permutations where each value in [n] is at most one position to the right of its position in the identity (e.g., 123, 132, 213, 312 for n = 3). What if at most m from each row can be eaten? When m = 1 the only solution is to eat one of each colour. Otherwise, the solutions are counted by Fibonacci (m = 2), Tribonacci (m = 3), Tetranacci (m = 4), and so on, up to 2^{n-1} (m = n). Furthermore, solutions can be naturally encoded by limited versions of the aforementioned objects including binary strings avoiding the substring 0^{m} and M&M permutations where values are limited by moving at most 𝓁 = m-1 positions to the left. Motivated by the works of Samuel Beckett, we consider minimal-change orders of the solutions. We obtain a satisfying result by filtering the binary reflected Gray code to words avoiding 0^{m}. For example, when n = 4 we have BRGC(n) = 000, 100, 110, 010, 011, 111, 101, 001 and the words avoiding 00 are BRGC_𝓁(3) = 110, 010, 011, 111, 101 where 𝓁 = 1 is the limit on the run-lengths of 0s. Our bijection then creates solutions that differ in by a single M&M 1244, 2244, 2234,1234, 1334. Thus, Beckett’s character Murphy can imagine every experience by changing one M&M at a time. The generalized Gray code BRGC_𝓁(n) was previously defined recursively [Bernini et. al Acta Informatica 2015] with its change sequence supporting amortized 𝒪(1)-time generation [Arndt Matters Computational 2010]. We uncover a simple greedy definition - flip the leftmost bit that creates a new binary word avoiding 0^m starting from w = ⋯ 110^{𝓁}110^{𝓁} - and a successor rule that supports loopless worst-case 𝒪(1)-time generation. Furthermore, the corresponding limited M&M permutations are greedily generated by swapping the smallest value (or the leftmost pair of adjacent values) that gives a valid new permutation (e.g., ̅{12}43, 21 ̅{43}, ̅{21}34, 1 ̅{23}4, 1324 for n = 4 and 𝓁 = 1). We also consider a relaxed version of the problem in which the initial pyramid’s n rows have respective widths r, r+1, r+2, …, n, n, …, n. Here the answer is an n-term product ⟨n,r⟩! = 1 ⋅ 2 ⋅ 3 ⋯ r ⋅ (r+1) ⋅ (r+1) ⋯ (r+1) that we refer to as a flatorial number. Furthermore, the solutions are represented by a generalization of M&M permutations in which each symbol can appear at most r positions to the right of its position in the identity. We complete our investigation by showing that eight distinct classes of permutations are enumerated by flatorial numbers.
Cite as

Elizabeth Hartung, Brett Stevens, and Aaron Williams. Pyramid Schemes for Eating M&Ms: Enumeration, Generation, and Gray Codes. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hartung_et_al:LIPIcs.FUN.2026.23,
  author =	{Hartung, Elizabeth and Stevens, Brett and Williams, Aaron},
  title =	{{Pyramid Schemes for Eating M\&Ms: Enumeration, Generation, and Gray Codes}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{23:1--23:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.23},
  URN =		{urn:nbn:de:0030-drops-257420},
  doi =		{10.4230/LIPIcs.FUN.2026.23},
  annote =	{Keywords: combinatorial enumeration, generation, Gray code, loopless algorithm}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.46
Skipping Ropes: An Efficient Gray Code Algorithm for Generating Wiggly Permutations

Authors: Vincent Pilaud and Aaron Williams

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Wiggly permutations were introduced by Bapat and Pilaud (Wigglyhedron Mathematische Zeitschrift 2025). We positively answer one of their conjectures by finding a Hamilton path in the wiggly flip graph that is isomorphic to the wigglyhedron. Our path provides a Gray code in which successive wiggly permutations are obtained by a single jump or hop, meaning that one or two consecutive symbols move past some number of smaller symbols. The Gray code has a simple greedy description that produces a recursive zig-zag pattern reminiscent of plain changes for permutations. More broadly, our results extend Algorithm J and the series of papers on zig-zag languages initiated by Hartung, Hoang, Mütze and Williams (Combinatorial Generation via Permutation Languages SODA 2020). Finally, we use wiggly changes as the basis for an 𝒪(n)-time delay generation algorithm.
Cite as

Vincent Pilaud and Aaron Williams. Skipping Ropes: An Efficient Gray Code Algorithm for Generating Wiggly Permutations. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pilaud_et_al:LIPIcs.WADS.2025.46,
  author =	{Pilaud, Vincent and Williams, Aaron},
  title =	{{Skipping Ropes: An Efficient Gray Code Algorithm for Generating Wiggly Permutations}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.46},
  URN =		{urn:nbn:de:0030-drops-242778},
  doi =		{10.4230/LIPIcs.WADS.2025.46},
  annote =	{Keywords: permutations, wiggly permutations, pattern avoidance, permutahedron, wigglyhedron, Hamilton path, flip graph, Gray code, combinatorial generation, generation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.53
Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time

Authors: Paul Lapey and Aaron Williams

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
The number of ordered trees (also known as plane trees) with n nodes is the (n-1)st Catalan number C_{n-1}. An ordered tree can be stored directly using nodes and pointers, or represented indirectly by a Dyck word. This paper presents a loopless algorithm for generating ordered trees with n nodes using pointer-based representations. In other words, we spend 𝒪(C_{n-1})-time to generate all of the trees, and moreover, the delay between consecutive trees is worst-case 𝒪(1)-time. To achieve this run-time, each tree must differ from the previous by a constant amount. In other words, the algorithm must create a type of Gray code order. Our algorithm operates on the children of a node like a stack, by popping the first child off of one node’s stack and pushing the result onto another node’s stack. We refer to this pop-push operation as a pull, and consecutive trees in our order differ by one or two pulls. There is a simple two-case successor rule that determines the pulls to apply directly from the current tree. When converted to Dyck words, our rule corresponds to a left-shift, and these shift generate a cool-lex variant of lexicographic order. Our results represent the first pull Gray code for ordered trees, and the first fully published loopless algorithm for ordered trees using pointer representations. More importantly, our algorithm is incredibly simple: A full implementation in C, including initialization and output, uses only three loops and three if-else blocks. Our work also establishes a simultaneous Gray code for Dyck words, ordered trees, and also binary trees, using cool-lex order.
Cite as

Paul Lapey and Aaron Williams. Pop & Push: Ordered Tree Iteration in 𝒪(1)-Time. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{lapey_et_al:LIPIcs.ISAAC.2022.53,
  author =	{Lapey, Paul and Williams, Aaron},
  title =	{{Pop \& Push: Ordered Tree Iteration in 𝒪(1)-Time}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{53:1--53:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.53},
  URN =		{urn:nbn:de:0030-drops-173380},
  doi =		{10.4230/LIPIcs.ISAAC.2022.53},
  annote =	{Keywords: combinatorial generation, Gray code, simultaneous Gray code, ordered trees, plane trees, Dyck words, binary trees, Catalan objects, loopless algorithm, cool-lex order}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.6
Rolling Polyhedra on Tessellations

Authors: Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
We study the space reachable by rolling a 3D convex polyhedron on a 2D periodic tessellation in the xy-plane, where at every step a face of the polyhedron must coincide exactly with a tile of the tessellation it rests upon, and the polyhedron rotates around one of the incident edges of that face until the neighboring face hits the xy plane. If the whole plane can be reached by a sequence of such rolls, we call the polyhedron a plane roller for the given tessellation. We further classify polyhedra that reach a constant fraction of the plane, an infinite area but vanishing fraction of the plane, or a bounded area as hollow-plane rollers, band rollers, and bounded rollers respectively. We present a polynomial-time algorithm to determine the set of tiles in a given periodic tessellation reachable by a given polyhedron from a given starting position, which in particular determines the roller type of the polyhedron and tessellation. Using this algorithm, we compute the reachability for every regular-faced convex polyhedron on every regular-tiled (≤ 4)-uniform tessellation.
Cite as

Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams. Rolling Polyhedra on Tessellations. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{baes_et_al:LIPIcs.FUN.2022.6,
  author =	{Baes, Akira and Demaine, Erik D. and Demaine, Martin L. and Hartung, Elizabeth and Langerman, Stefan and O'Rourke, Joseph and Uehara, Ryuhei and Uno, Yushi and Williams, Aaron},
  title =	{{Rolling Polyhedra on Tessellations}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.6},
  URN =		{urn:nbn:de:0030-drops-159761},
  doi =		{10.4230/LIPIcs.FUN.2022.6},
  annote =	{Keywords: polyhedra, tilings}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.22
All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges

Authors: Arturo Merino, Torsten Mütze, and Aaron Williams

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
You provide us with a matroid and an initial base. We say that a subset of the bases "belongs to us" if we can visit each one via a sequence of base exchanges starting from the initial base. It is well-known that "All your base are belong to us". We refine this classic result by showing that it can be done by a simple greedy algorithm. For example, the spanning trees of a graph can be generated by edge exchanges using the following greedy rule: Minimize the larger label of an edge that enters or exits the current spanning tree and which creates a spanning tree that is new (i.e., hasn't been visited already). Amazingly, this works for any graph, for any labeling of its edges, for any initial spanning tree, and regardless of how you choose the edge with the smaller label in each exchange. Furthermore, by maintaining a small amount of information, we can generate each successive spanning tree without storing the previous trees. In general, for any matroid, we can greedily compute a listing of all its bases matroid such that consecutive bases differ by a base exchange. Our base exchange Gray codes apply a prefix-exchange on a prefix-minor of the matroid, and we can generate these orders using "history-free" iterative algorithms. More specifically, we store O(m) bits of data, and use O(m) time per base assuming O(1) time independence and coindependence oracles. Our work generalizes and extends a number of previous results. For example, the bases of the uniform matroid are combinations, and they belong to us using homogeneous transpositions via an Eades-McKay style order. Similarly, the spanning trees of fan graphs belong to us via face pivot Gray codes, which extends recent results of Cameron, Grubb, and Sawada [Pivot Gray Codes for the Spanning Trees of a Graph ft. the Fan, COCOON 2021].
Cite as

Arturo Merino, Torsten Mütze, and Aaron Williams. All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 22:1-22:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{merino_et_al:LIPIcs.FUN.2022.22,
  author =	{Merino, Arturo and M\"{u}tze, Torsten and Williams, Aaron},
  title =	{{All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{22:1--22:28},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.22},
  URN =		{urn:nbn:de:0030-drops-159928},
  doi =		{10.4230/LIPIcs.FUN.2022.22},
  annote =	{Keywords: Matroids, base exchange, Gray codes, combinatorial generation, greedy algorithms, spanning trees}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.13
Super Mario Bros. is Harder/Easier Than We Thought

Authors: Erik D. Demaine, Giovanni Viglietta, and Aaron Williams

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
Mario is back! In this sequel, we prove that solving a generalized level of Super Mario Bros. is PSPACE-complete, strengthening the previous NP-hardness result (FUN 2014). Both our PSPACE-hardness and the previous NP-hardness use levels of arbitrary dimensions and require either arbitrarily large screens or a game engine that remembers the state of off-screen sprites. We also analyze the complexity of the less general case where the screen size is constant, the number of on-screen sprites is constant, and the game engine forgets the state of everything substantially off-screen, as in most, if not all, Super Mario Bros. video games. In this case we prove that the game is solvable in polynomial time, assuming levels are explicitly encoded; on the other hand, if levels can be represented using run-length encoding, then the problem is weakly NP-hard (even if levels have only constant height, as in the video games). All of our hardness proofs are also resilient to known glitches in Super Mario Bros., unlike the previous NP-hardness proof.
Cite as

Erik D. Demaine, Giovanni Viglietta, and Aaron Williams. Super Mario Bros. is Harder/Easier Than We Thought. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.FUN.2016.13,
  author =	{Demaine, Erik D. and Viglietta, Giovanni and Williams, Aaron},
  title =	{{Super Mario Bros. is Harder/Easier Than We Thought}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.13},
  URN =		{urn:nbn:de:0030-drops-58802},
  doi =		{10.4230/LIPIcs.FUN.2016.13},
  annote =	{Keywords: video games, computational complexity, PSPACE}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact