This challenge is inspired by the same task I read some time ago in CACM.
There are many ways to sort stuff. Most attempt to sort in as few operations as possible (= as fast as possible). However, it is also possible to consider how few resources you might require to sort stuff, which seems more fitting for a codegolf challenge.
You have a stack of cards, numbered from 1
to N
(or 0
to N-1
or a
to zzz
if you prefer). You do not know N
. All you have available are two additional stacks, where one of them has capacity for just a single card. At any point, you see just the top of those stacks and you have no memory what was there even a single step before.
Your task is to write a function (or whatever) that would take top of those 3 stacks as input in some convenient form and return operation that has to be performed - eg 2,3
meaning card has to move from stack 2 to stack 3. Please note that one stack has capacity for a single card. Input given when stack is empty is arbitrary.
Initial state of sorting is one stack with all the cards in arbitrary mixed order and two empty stacks, one of the two with capacity for a single card (and the other is unlimited). After executing your function (and performing the operation returned) finitely many times on arbitrarily mixed initial cards, cards have to be guaranteed to be sorted on any of the stacks. Saving previous state or checking non-top numbers in any way is prohibited. As are all other loopholes.