ChipChip: A new sort of sorting

A uniquely French way to express contempt for someone is to call them an “espèce d’espèce” (see Endnote #1); literally, “a sort of a sort”.  This month I’m going to tell you about a sort of a sort (or rather, a sort of sorting) that, from a practical standpoint, merits this degree of contempt: the procedure is ambiguous, is annoyingly slow, and doesn’t always sort things correctly. Yet there’s an unresolved mathematical mystery arising from the way that the procedure works better than it has any right to.

But first, a puzzle:

You see nine numbered bubbles strewn amid nine columns. Your mission is to arrange the bubbles in order, with 1 at the far left, 2 next to it, and so on. But you’re only allowed eleven moves to complete your mission, and your moves are of an unusual kind: given two bubbles that are in the same column, you may send one bubble to the next column to the left and the other bubble to the next column to the right. This is called an “exploding” move. For instance, in the eighth column you see two bubbles, marked 7 and 8, so on your first move one option is to move bubble 7 one column leftward and bubble 8 one column rightward, or vice versa (with similar possibilities for explosion in the third and sixth columns).

Actually, maybe you shouldn’t start with that puzzle; it’s one of the trickier ones. Better to warm up with examples involving 5 bubbles in 5 columns, or 7 bubbles in 7 columns, before tackling 9 bubbles in 9 columns. Click on the graphic below, and then click again, to get started:

CHIPCHIP

I call these brainteasers “ChipChip puzzles” because the sorts of moves you’re allowed to make were first studied in the chip-firing game, and because I like to imagine that the bubbles make a swooshy/chirpy “ch’p ch’p!” sound when one bubble moves to the left and the other moves to the right. The moves are called “explosions” because … well, because Exploding Dots. In fact, in keeping with the whole Exploding Dots vibe, I also allow “unexploding” moves, where two bubbles that are two columns apart from each other are allowed to move into the intervening column.

I came up with ChipChip a couple of years ago; it was first implemented as a computer game by freelance programmer Valerie Samn, and has now been beautifully redone by Evgeny Milyutin of Happy Numbers, with support and encouragement from James Tanton of the Global Math Project. It’s being unveiled this week in conjunction with Global Math Week, and I posted a teaser-trailer for it a few days ago.

 

The nine-column ChipChip puzzle I showed you earlier doesn’t require any unexploding moves in its solution; it just requires eleven moves in which a lower-numbered bubble goes left and a higher-numbered bubble goes right. But if you start making moves of this kind at random, you’re unlikely to hit on the solution. In fact, the way I found this particular puzzle was by having a computer try thousands of possible initial states and then report to me which one was doable but least likely to be solved randomly! Try to solve it using fewer and fewer unexploding moves until you manage to solve it using none at all. Then the program will report that you solved the puzzle in “0 over par” moves, where “par” is a bit of a misnomer; in this context, it means “perfection”.

TOO EASY?

At the opposite extreme, here’s a ChipChip puzzle that’s rather easy to solve, though in a certain sense, proving that it’s easy to solve isn’t so easy.

If you explode at random over and over, the probability that you’ll succeed in getting the bubbles sorted is very close to 1/3.

This is the contemptible “espèce d’espèce” sort of sorting that I mentioned in the opening paragraph. Given n bubbles in a column, numbered 1 through n, we repeatedly perform exploding moves until it becomes impossible to continue. The algorithm is ambiguous (when more than one exploding move is possible, we’re not told which one to do next), it’s annoyingly slow (we’ll see that the number of moves is on the order of n cubed, while the best sorting algorithms have running time on the order of n times the logarithm of n), and it doesn’t always give the right answer.

The algorithm seems espèce-ially stupid when you consider that a slight variant, described in Endnote #3, infallibly sorts the bubbles perfectly, namely, the variant in which you always make sure that the two bubbles you explode are the lowest-numbered and highest-numbered bubbles in their shared column. Choosing a column at random might seem defensible, since it’s unclear that one column is better than another; but choosing two bubbles in a column at random, instead of choosing the intuitively best two bubbles? Quelle espèce de stupidité!

But something spooky is going on with the simple-minded algorithm:

1. When n is even, the algorithm always sorts the bubbles correctly (with a hole in the middle).

2. When n is odd, the algorithm sorts the bubbles correctly with probability going to 1/3 as n gets large.

Those last two sentences require comment. The first claim (when n is even, the algorithm always sorts the bubbles correctly) has been proved by Hopkins, McConville, and me, but the proof is unsatisfyingly complicated, and doesn’t resolve other questions of a similar kind (see for instance page 20 of my slide presentation, given in the References); I suspect that we’re missing some key insight that will give us a deeper understanding of what’s going on. The second claim (when n is odd, the probability of success goes to 1/3) is merely empirical, and seems outlandish when you consider that on the very last move, the probability of failure is at least 2/3, so the probability of success is at most 1/3!  We have no idea how to prove the claim.

Part of what intrigues me about this sort of sorting is the way it clashes with my expectations. My experience has been that when an algorithm I’ve devised doesn’t always give the right answer, it gets worse and worse as the problems it’s applied to get larger and larger. So I would’ve predicted that the probability of success of this sort of sorting would go to 0 as n gets large. Then again, given how long the algorithm runs, maybe n-cubed steps is such a long time that the algorithm achieves a kind of dimwitted thoroughness that leads it to the right answer, much as blind evolution leads to marvelous things like brains; so if you told me that my guess was wrong, and that the probability of success doesn’t go to 0, my second guess would be that the probability of success goes to 1. But if you’d told me that that guess was wrong too, I’m not sure what my third guess would’ve been (though see Endnote #7). Why should the probability be exactly 1 when n is even, and converge to 1/3 for large n when n is odd? There’s no way I would’ve guessed that without doing experiments.

Amusingly, while it’s easy to turn − − − − 123456789 − − − − into 1 2 3 4 5 6 7 8 9 with explosions, it’s tricky to go in the other direction with unexplosions. Try it! Of course you could make a video of yourself doing the former and then play it backwards, or write down all the moves you do and then perform them in reverse, but that’s cheating.

HOW MANY MOVES?

If you try sorting 9 bubbles with random explosions, and then try again, and again, and so on, to test my claim about the magic number 1/3, you may notice that, whether you win or lose, you always run out of moves after 30 explosions. There’s a slick way to see that there’s no way to win in fewer than 30 moves even if you allow some unexplosions. You can measure the spread of the distribution of bubbles by looking at the sum of the squares of the distances between each bubble and the middle column. (If this reminds you of the statistical concept of variance, it’s no coincidence!) When all the bubbles are in the middle, that sum is 0. When the bubbles are spread out, one per column, that sum is (−4)²+(−3)²+(−2)²+(−1)²+(0)²+(1)²+(2)²+(3)²+(4)² = 60. On the other hand, when you make an exploding move, the spread always increases by exactly 2. (Before an exploding move in column i occurs, the spread is (i)² plus (i)² plus other terms associated with the other bubbles; after the move, when one bubble has moved from column i to column i−1 and another has moved from column i to column i+1, the spread is (i−1)² plus (i+1)² plus the exact same extra terms; so, subtracting one sum from the other and cancelling the common terms, we get [(i−1)² + (i+1)²] − [(i)² + (i)²], which simplifies to just 2.) Likewise, an unexploding move decreases the spread by exactly 2. So the number of explosions minus the number of unexplosions must be exactly 60/2=30, implying that at least 30 moves are required to increase the spread from 0 up to 60.

What if we prohibit unexplosions? Then it can be shown that until we’ve done 30 explosions, there must be a column that contains two or more bubbles. So if we do random exploding moves, starting with 9 bubbles in the middle column, then the game (win or lose!) will last exactly 30 moves.

Generalizing, we see that if we start with 2k+1 bubbles in the middle column and start doing explosions, then, win or lose, the number of explosions we will perform will be exactly 1²+2²+3²+…+k², which turns out to equal k(k+1)(2k+1)/6.

REVERSAL VERSUS DISPERSAL

For many sorting procedures, the worst-case behavior occurs when the list to be sorted starts out in reverse order. That’s certainly the case for nearest-neighbor-swap sorting, where a move consists of swapping two adjacent entries if they’re in the wrong order. But for ChipChip, sorting a list that starts out reversed is easier than sorting a list that starts out as one big pile.

More specifically, you can apply ChipChip sorting with the initial condition

9   8   7   6   5   4   3   2   1

(where each bubble starts out in the opposite column from where it’s supposed to end up) and finish in fewer steps than with the initial condition in which all nine bubbles start in the middle. That’s surprising. You’d think that moving each bubble halfway to its final destination (that is, moving it to the middle column) constitutes progress! But not for ChipChip.

Can you find a way to get the nine chips arranged in order in just 26 moves? The solution given in Endnote #4 was found by Tom Rokicki; he showed by exhaustive search that his solution is the most efficient possible.

I conjecture, based on Tom’s experiments, that it takes exactly k²+3k−2 moves to reverse a row of 2k+1 bubbles. The formula holds true for k up through 5. I can show that 2k² moves suffice; see Endnote #6.

In contrast, we saw in the last section that it takes k(k+1)(2k+1)/6 ChipChip moves to sort 2k+1 bubbles that all start in the middle. This function of k grows faster than k²+3k−2; it’s cubic rather than quadratic. What’s going on here is that exploding and unexploding moves, intelligently applied, aren’t really so bad at scrambling bubbles arranged in a row, but are really bad at breaking up a big clump of bubbles all sharing the same column.

WHAT’S THE POINT?

If you’ve read my earlier essays, ChipChip will feel familiar. For instance, replace the bubbles by pigs and the columns by pens and you’ve got the set-up for Swine in a Line. But the pigs were all the same, reflecting the fact that traditional chip-firing uses chips that are indistinguishable. My article with Hopkins and McConville is about using chip-firing to sort chips that are all different.

I came up with sorting via chip-firing as a way of mashing together two topics I like: chip-firing and “swap-sorting”. In swap-sorting, you have n numbers arranged in a row, and the goal is to get them in increasing order, using only operations that swap neighboring numbers that were incorrectly ordered before the swap. A basic fact about swap-sorting is that the end-result doesn’t depend on which swaps you choose to do at any time (choosing randomly is fine), and that the procedure takes no more than n(n−1)/2 swaps (and in fact this is the exact number of swaps required when the n numbers start out in decreasing order); see Endnote #5 and Endnote #8.

Swap-sorting is an example of a confluent process (the end result doesn’t depend on the choices you make along the way), and so is chip-firing with indistinguishable chips. But when you mash them together and come up with sorting-via-chip-firing, you get a process that is not quite confluent but comes awfully close. I’d like to understand processes like this.

Part of my motivation for developing and promulgating ChipChip was the dream that if enough people get enough experience with exploding and unexploding moves, maybe the missing theoretical insights will arise from the skill-sets of experienced players.

With the exception of the puzzles that require you to reverse the order of the bubbles, none of the puzzles in the current version of the program require any unexploding moves at all. That’s because it was easier for me to study puzzles that only involve explosions, and I never had the time to study puzzles that require moves of both kinds. But I suspect that this unexplored part of the ChipChip realm is where the really challenging puzzles live. If any of you come up with good ChipChip puzzles, please share them in the Comments, and Evgeny might add them to the program!

Next month (November 17): The meanings of the Mathematical Enchantments logo  Between the world and the mind.

 

Thanks to Sandi Gubin, Sam Hopkins, Michael Kleber, Stephen Lucas, Evgeny Milyutin, Dave Perkinson, Tom Rokicki, Leila Schneps, James Tanton, and Glen Whitney.

ENDNOTES

#1. According to anthropologist Gregory Bateson’s book Steps to an Ecology of Mind (1972): “In French the phrase espèce de (literally “sort of”) carries a special sort of punch. If one man calls another “a camel” the insult may be a friendly one. But if he calls him an espèce de chameau − a sort of camel − that’s bad. It’s still worse to call a man an espèce d’espèce − a sort of a sort.” My French informants tell me that this insult is falling into disuse in the 21st century. Still, see Claude Duneton’s 2016 article “Mais d’où vient cette espèce d’insulte?”

#2. The Hopkins-McConville-Propp result has an amusing consequence about blue and red bubbles with no numbers on them. Suppose we have an even number of bubbles in a column (and no bubbles anywhere else), with some of the bubbles blue and others red. On any turn, you can explode any two bubbles that are in the same column, subject to the constraint that if the two bubbles are of opposite colors, you must send the bLue one to the Left and the Red one to the Right. Then no matter what you do, the blue bubbles will end up to the left of the red bubbles. To see why, just number the bubbles consecutively, with all the blue bubbles having lower labels than all the red bubbles, and then apply the result about numbered bubbles.

#3. We’ve seen that, in the case where all bubbles start in the middle, making random explosions does surprisingly well (in fact, it works perfectly when n is even). If you want a sure-fire way to win when n is odd, either of two simple variants of the pure random approach work:

Method A: Make sure that the two bubbles that you explode are always the lowest-numbered bubble and the highest-numbered bubble in the column they share. Then you can’t lose. (Why? Call an arrangement of bubbles weakly sorted if for all i < j, bubble i is either to the left of, or in the same column as, bubble j. The initial configuration of the bubbles is weakly sorted, and you can check that when you have a weakly sorted configuration and you explode the lowest- and highest-numbered bubbles in some column, the configuration stays weakly sorted. That implies that when the game ends, the bubbles are weakly sorted. But when the game ends, every bubble is in a column by itself, so “weakly sorted” means the same as “sorted”.)

Method B: Make sure that you never explode the bubble that’s in the correct column from the start (for our n=9 example, that would be bubble 5). Then you can’t lose. (Why? Ignore the bubble that never moves; then you’re just doing a sorting operation on the remaining bubbles, and since there are an even number of them, the McConville-Hopkins-Propp result applies.)

You might think that winning the game calls for being intelligent from beginning to end, but in a sense it’s only the endgame (in fact, only the very last move) that usually matters. It’s not hard to show that if you apply Method A throughout, but then make a random choice on your last move, your probability of winning is exactly 1/3. On the other hand, we believe that if you make random choices throughout, but then apply Method A on just the last move, your probability of winning converges to 1 as n gets large! Equivalently, we believe that if you play randomly, then with probability converging to 1 as n gets large, the bubbles will be weakly sorted immediately before your final move.

#4. Here’s Tom Rokicki’s (highly symmetrical) 26-move solution.

9 8 7 6 5 4 3 2 1
9 8 7 6 5 4 − 123 −
− 789 − 6 5 4 − 123 −
− 789 − 6 5 − 14 23 −
− 789 − 6 5 1 − 234 −
− 78 69 − 5 1 − 234 −
− 678 − 9 5 1 − 234 −
− 678 − − 159 − − 234 −
− 678 − 1 5 9 − 234 −
− 678 − 1 5 − 29 34 −
− 678 − 1 5 2 − 349 −
− 67 18 − 5 2 − 349 −
− 167 − 8 5 2 − 349 −
− 167 − − 258 − − 349 −
− 167 − − 258 − 3 4 9
1 6 7 − 258 − 3 4 9
1 6 7 − 25 38 − 4 9
1 6 − 27 5 38 − 4 9
1 6 − 27 5 3 48 − 9
1 − 26 7 5 3 48 − 9
1 − 26 − 357 − 48 − 9
1 − 26 3 5 7 48 − 9
1 − 26 3 5 47 − 8 9
1 2 − 36 5 47 − 8 9
1 2 − 36 45 − 7 8 9
1 2 3 − 456 − 7 8 9
1 2 3 4 5 6 7 8 9

Note that the 5 never gets moved.

#5. A helpful way to think about a permutation of n numbers is to look at inversions. An inversion is just a pair of numbers in a list that appear in the wrong order. At the beginning, when the numbers are in decreasing order, every pair is an inversion, so the number of inversions is the total number of pairs: 1+2+3+…+(n−1) = n(n−1)/2. Every time we swap two adjacent numbers that were out of order and put them in the correct order, we reduce the number of inversions by 1. That’s why, no matter what choices we make, it always takes n(n−1)/2 swaps to take a decreasing sequence of length n and turn it into an increasing sequence of length n.

One unproved conjecture from Hopkins-et-al. is that when you apply sorting-by-explosion to 2k+1 bubbles that all start in the same column, the resulting permutation of the numbers 1 through 2k+1 has at most k inversions.

#6. We can swap the bubbles at i−1 and i+1 by unexploding and then exploding them. Taking this two-move swap as a primitive operation, we can first sort the k+1 odd-numbered bubbles and then sort the k even-numbered bubbles, using (k+1)(k) + (k)(k−1) = 2k² moves.

#7. My third guess would probably have been 1/e ≈ .37, where e is Napier’s constant, but that’s just because it often turns up in probability problems where there are reasons to think that some limit is either 0 or 1 but the true answer turns out to be something in between.

#8. It was a bit unfair of me to compare the efficiency of sorting-with-chip-firing with the efficiency of classic sorting algorithms like Quicksort, because the latter have a huge advantage: list-items can be moved from one location to another without regard to proximity, whereas chip-firing is a strongly local operation. A better comparison would be with sorting networks, which allow only adjacent swaps. Yet here again chip-firing shows itself to be a loser: a good sorting network for sorting n items involves only quadratically many swaps, while sorting-with-chip-firing involves cubically many explosions.

#9. A year ago, mathematician Christian Lawson-Perfect recorded a transatlantic Skype interview in which I told him about ChipChip. Instead of having him numerically sort virtual numbered bubbles, I had him alphabetically sort Banagram tiles. Christian never got around to editing the audio file and turning it into a podcast (perhaps in part because the sound quality on my end wasn’t so good), but I offer it here for anyone who’s interested.

REFERENCES

Sam Hopkins, Thomas McConville, and James Propp, Sorting via Chip-Firing. Available at https://arxiv.org/abs/1612.06816.

Richard Anderson, László Lovász, Peter Shor, Joel Spencer, Eva Tardos & Shmuel Winograd, Disks, Balls, and Walls: Analysis of a Combinatorial Game. American Mathematical Monthly, volume 96 issue 6, June–July 1989, pp. 481-493. The original analysis of chip-firing in a line (with indistinguishable chips).

James Propp, Confluence and Near-Confluence (slides). Available at http://faculty.uml.edu/jpropp/mit17a.pdf