5
$\begingroup$

Suppose that you have N labeled coins pinched in one stack in your fingertips (your palm is above your fingers and your palm is facing down, so that you can drop as many coins as needed from the bottom of the stack) and you have a table which only allows for two other stacks (call these L for left and R for right). You can freely choose L or R for each coin, but the coin dropping order is fixed. You can also freely pick up coins from either stack (the reverse of a drop).

For general N, what is the minimum pickups needed to reverse the stack order? I'm curious about the total number of coins picked up and about the total number of pickup events, but am officially asking only for the latter.

As an example, I believe the minimum for N=7 is 5. We start holding 1234567. Drop 247 in L and 1356 in R; pick up 1356 from R. Drop 16 in L and 35 in R; pick up 24716 from L. Drop 76 in L and 241 in R; pick up 35241 from R. Drop 54 in L and 321 in R; pick up 321 from R. Drop 321 in L; pick up 7654321 from L.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ It would be really good to reword this so that it does not appear at first glance like the answer might depend on your manual dexterity. $\endgroup$
    – Steven Landsburg
    Commented Apr 9, 2014 at 1:35
  • 1
    $\begingroup$ It sounds like you're asking for the best algorithm to reverse a queue using two other FIFO queues. It might be better to ask on stack exchange - a cursory glance at a "reverse queue" search there makes it look popular. $\endgroup$
    – Zack Wolske
    Commented Apr 9, 2014 at 3:20
  • 1
    $\begingroup$ If you can solve it for a few small values of $N$, you might be able to look it up at the Online Encyclopedia of Integer Sequences. $\endgroup$
    – Gerry Myerson
    Commented Apr 9, 2014 at 3:31
  • 1
    $\begingroup$ @Zack In similar words, I want to reverse one LIFO queue (i.e., a stack) using two other LIFO queues, but the reversed data needs to be in the original LIFO queue and the other two queues cannot feed each other directly. I'll give mathematicians a chance first because I think this is quite difficult and perhaps no algorithm is even known. $\endgroup$
    – bobuhito
    Commented Apr 9, 2014 at 3:50
  • $\begingroup$ I also think it would be great if you could give some more examples. If N=2, is the answer 1 or 2? The operations and what we count are not clear to me. $\endgroup$
    – domotorp
    Commented May 8, 2014 at 10:16

1 Answer 1

Reset to default
1
$\begingroup$

I think the asymptotics is $\log$ N, but this might have a constant multiplier depending on what you count exactly. The solution is basically known as Radix sort.

Imagine that you get any sequence of N unsorted numbers. Represent each with $\log$ N digits. We sort first with respect to the least important digit, then the second least and so on, finally with respect to the leading digit. This is done by dropping smaller numbers to L and larger numbers to R.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .