Communications of the ACM
Last byte
Puzzled: A Sort, of Sorts
Credit: deviantART
Sorting is one of the most fundamental, and most studied, computational tasks. The problem is typically to put n items in order, using the power of a Turing machine or equivalent. The objective is to minimize time, space, number of comparisons, or (in the parallel case) number of rounds of comparisons. But you do not need the full power of a Turing machine to do it. How meager can your computing resources be to be able to sort? Would you believe three LIFO stacks and no memory? Here, we raise the question by asking you to design algorithms to sort playing cards. But be wary. The three problems here, the first of which was communicated to me decades ago by the brilliant mathematician John H. Conway of Princeton University, are trickier than they look, and allegedly froze one victim in his chair for six hours.
- You wish to sort three cards: ace ("1"), deuce ("2"), and trey ("3"). There are three places on the table on which cards can be stacked, and your objective is to get them stacked in the left-most place, with 1 on top, then 2, then 3 on the bottom. The cards begin faceup in arbitrary positions; for example, they may be exposed as 1, 2, 3 in the left, center, and right places, respectively or 2 over 3 over 1 in the right-hand place, in which case you see only the 2 on top. At any time you may take a card from the top of a stack and place it, still face up, on top of another (possibly empty) stack. The difficulty is you see only the top card or cards and you have no memory; for example, if you started with 1 on top of 2 on the left and 3 in the center and moved 1 to the top of the 3, you are now looking at 2, 1, blank, and you no longer know the position of the 3. You thus need an algorithm whose moves depend only on what is seen. It will not know when to stop, but you may imagine when the cards are correctly sorted in the left place, a bell will ring and you will be showered with money. So, can you design an algorithm that eventually works, regardless of the cards' initial positions?
- Same problem but now with n cards, numbered 1 to n, you wish to sort in the left position, with 1 on top. There are still only three positions on the table.
- Same as the second problem, but now the middle position can hold only one card; if you try to put another on it, you lose.
Footnotes
Readers are encouraged to submit prospective puzzles for future columns to [email protected].
The Digital Library is published by the Association for Computing Machinery. Copyright © 2014 ACM, Inc.
Comments
Marc Auslander
My solution to 3 (and thus 1 and 2) is n**2 in complexity. I believe with an appropriate FSM and three stacks you can do an n*Log(n) sort/merge.
So - does any one either have an n*log(n) solution (which would be amazing) or an argument or proof that it's impossible?
Marc Auslander
My post above is based on a pretty algorithm that doesn't work!
I have no idea how to solve 2 or 3, or if they can be solved.
Sigh.
David Powers
statelessNDA: The simplest solution is to move cards randomly between the piles (e.g. with equal probability for each of the up to 6 possible moves for problems 1 & 2 or the 4 legal moves for problem 3). Eventually that bell will ring with its accompanying shower of money.
To clarify, for all problems, you are not allowed to move a card from an empty pile to another pile!-)
So the number of available moves may be less than the maximum possible in general for that problem.
For problem 3, if the middle is non-empty the two moves that would move a card on to it are excluded. Otherwise it is empty, and the two moves that would move a card from it are excluded as above.
Given there is no memory and we have a hardwired program (an FSA with a fixed number of states independent of n), we do not have the bits to store, check, decrement or increment n (except implicitly with the cards on the stacks). So no algorithm involving a for/do loop with a control variable is possible (no RAM or registers), nor is an unwound equivalent (fixed number of wires or states or bits of ROM).
In fact, the problem this random algorithm solves is the problem of n numbered cards that aren't required to be labelled 1 to n, just having an ordering defined (< with unique cards, <= with duplicates allowed). We can also remove the requirement that the cards be face up (unless required for that shower of money).
This requires 0 memory and 0 state.
As we can't keep track of the 3^n states of problem 2 or the 2*2^n states of problem 3 with 0 memory, the only way to encode position or information would be in the positions of the cardsWhile we can in general use the ordering of the cards in and across the stacks to encode arbitrary state information, this is not possible in a stateless way for these problems since they are explicitly allowed to start in arbitrary positions and can thus violate any encoding scheme for state (what ever positioning or sortedness information was putatively conveyed would be false much of the time).
This leaves the state-free non-deterministic solution I explained, and further explains why we need the bell, or an algorithm that works efficiently if the state information is valid, but still works when it is invalid.
Suppose we end up with everything in the left pile and supposedly sorted according the encoded state of our algorithm, but the bell doesn't ring and stop the game. Then we know that we are in an invalid state by seeing the two empty piles... The program/FSA can be in a part of the code/state space that indicates being in an invalid state. This doesn't seem to help use though as we still have the problem of the restricted middle stack for Problem 3, and even with state we can't deal with that deterministically.
DFA: So let's assume we are allowed to have a DFA with a fixed number of states but not O(n) or even O(logn). Maybe remembering state is excluded from the definition of memory (as Program Counter would have to be in a CPU and the Stack Counters implementing the Stacks).
In fact, we could start in an Init state and in this state move all cards to the left pile then shift to a LRmin state as it puts one card into the middle and then attempt a selection sort. One pass through in the LRmin state would allow us to accumulate the minimum (1) in the middle, stopping when the left pile was empty. In problem 3, we are then stuck, but in problem 2 we could then shift to a RLmin state as it puts another card on top of the middle pile. Viz. we repeat until both left and right piles are empty and the middle pile is either sorted or reverse sorted.
Since I described this using a min pass that would work for Problem 3, it had to use the middle pile to accumulate the minimum, but then it couldn't accumulate the second lowest because of the additional constraint. With use of this min subroutine I get a reverse-sorted middle pile which I can reverse trivially with a Final state, and we are done when middle as well as right are empty.
Alteratively I could interchange the roles of middle and left in the description and use max for min and accumulate directly in the left pile. This assumes we can have an n-bit comparator available in our memory-free system finite state system, or a single-bit pipeline comparator FSA scan two numbers from MSB of top of two stacks in parallel.
On the other hand, if we assume we can have O(3n) states then we can just remember not only
(a) whether we are in the Init state or not, but
(b) what the disposition of the cards is, once we have made a pass through
Hardly zero memory.
Mark Weisser
I was cleaning out my desk a few days ago and came across this article which I had saved to work on when I had the time. Three years later ...
I have a deterministic solution for puzzle 3 which as pointed out in the first comment solve puzzles 1 and 2 as well. The solution meets the constraints of puzzle 3. I wrote a program that I used to test the solution for all possible starting positions for n equals 3 through n equals 9.
I represent the display of the three stacks of cards as a permutation of n digits and 2 bars that mark the stack boundaries. For examples, "123||" represents the winning solution with 1 showing in the leftmost stack, "1|2|3" represents one card showing in each stack, and so on. I then used Knuth's algorithm "L" for generating all permutations to test the solution. There are (n + 2)! / 2! possible arrangements of the cards in the three stacks. Here are some statistics on the number of moves the solution required for n = 3 through 7. (I need to write another program to collect the statistics for larger values of n). Note that for puzzle three I did not exclude the starting positions with more than one card in the middle when testing. And so that statistics are accurate for puzzle 2.The solution never moves a card onto the middle stack if occupied.
Here's the statistics so far:
n 3 4 5 6 7
count 60 360 2520 20160 181440
mode 13 16 29 36 51
median 9.0 18.5 39.0 91.5 211.0
average 9.1 21.4 50.8 111.5 218.6
max 19 58 149 294 505
stdev 4.4 12.5 35.5 76.5 135.3
Displaying all 4 comments