7
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
6
  • 1
    \$\begingroup\$ What is the input if a stack is empty? \$\endgroup\$ – Jo King♦ Dec 20 '19 at 11:08
  • \$\begingroup\$ What are we told for the "top card" if a stack is empty? When you say that one stack has capacity for one card, does that mean we have the input stack where things stack, an initially empty stack that can hold any number of cards, and also an initially empty stack that can hold only one card? \$\endgroup\$ – xnor Dec 20 '19 at 11:31
  • 3
    \$\begingroup\$ I think this question is more of a puzzle than a code golf challenge, as the challenge here is to figure out the algorithm, and the implementation itself is trivial. Of course, after the first answer appears, the optimal algorithm to figure out the algorithm is to copy it from someone else. \$\endgroup\$ – the default. Dec 20 '19 at 12:23
  • \$\begingroup\$ @JoKing whatever you want. It can be an empty array, a number not in bounds or something else. \$\endgroup\$ – Zizy Archer Dec 20 '19 at 13:09
  • \$\begingroup\$ @xnor 1. Whatever you want. 2. Yes. One stack that is initially full of mixed cards. One stack that can hold whatever number of cards and is initially empty. And one stack that can hold a single card. \$\endgroup\$ – Zizy Archer Dec 20 '19 at 13:13
2
\$\begingroup\$

Jelly, 9 8 bytes

ṖM⁸aḢ;‘$

Try it online!

A monadic link taking a list of three integers representing the top of the three stacks, or zero for an empty stack. The three stacks are [single card, destination, source]. Returns a pair of integers indicating which stack to move from and to. In keeping with Jelly’s indexing of lists, the third stack can be referred to either as 3 or 0.

Inspiration taken from @Arnauld’s JavaScript answer so be sure to upvote that one!

Explanation

Ṗ         | Remove last list item
 M        | Indices of maximum
  ⁸a      | Original argument and with this
    Ḣ     | Head
     ;‘$  | Concatenate to itself plus 1
Improve this answer
\$\endgroup\$
6
\$\begingroup\$

JavaScript (ES6), 23 bytes

Uses 1-indexed cards and stacks. The initial stack is the 1st one. The single-card stack is the 3rd one. Expects \$0\$ for an empty stack.

Returns a 2-digit number, where the 1st digit is the source stack and the 2nd digit is the destination stack.

(a,b,c)=>c?b>c?21:32:13

Try it online!

Commented

(            // input:
  a,         //   a = top card in the primary stack
  b,         //   b = top card in the secondary stack
  c          //   c = card in the temporary stack
) =>         //
  c ?        // if there's already a card in the temporary stack:
    b > c ?  //   if there's a card in the secondary stack and it's
             //   greater than the temporary card:
      21     //     move from secondary to primary
    :        //   else:
      32     //     move from temporary to secondary
  :          // else:
    13       //   move from primary to temporary
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.