You have a French deck of cards that sorted like this: 2 - 10, Princes, Queens, Kings, Aces.

The deck represented with array of numbers from 1 to 52(included)

Now the dealer is shuffling the deck 3 times and inserting a Joker in a random position of the deck.

The joker represented with the number 0

The idea of shuffling is slicing the array in random position and moving it to the front like in the next examples:

  • 1,2,3,4,5,6,7,8,9,10 -> 6,7,8,9,10,1,2,3,4,5 // Sliced at 6
  • 1,2,3,4,5,6,7,8,9,10 -> 8,9,10,1,2,3,4,5,6,7 // Sliced at 8

Find the joker position in the array. The challenge is doing this without iterating over the entire deck.

Winning priority:

  • Best time performance
  • Shortest code

closed as unclear what you're asking by Peter Taylor, Timtech, Darren Stone, John Dvorak, luser droog Jan 3 '14 at 6:12

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 6
    \$\begingroup\$ Considering your recent question history (and associated reputation gains), I strongly suggest you made use of the sandbox in meta before asking in main. \$\endgroup\$ – J B Nov 12 '13 at 14:42
  • 1
    \$\begingroup\$ @Babibu you were told about it already several times, IIRC. \$\endgroup\$ – John Dvorak Nov 12 '13 at 14:52
  • 1
    \$\begingroup\$ IIRC = If I Remember Correctly. Urban Dictionary knows that. Google knows Urban Dictionary knows that. \$\endgroup\$ – John Dvorak Nov 12 '13 at 14:57
  • 4
    \$\begingroup\$ You should really use the sandbox next time. Maybe you should post a new question, this time through the sandbox? If only to learn the ropes. \$\endgroup\$ – John Dvorak Nov 12 '13 at 15:19
  • 3
    \$\begingroup\$ This question appears to be off-topic because it is a chameleon question. You can't just change the criteria like that. \$\endgroup\$ – John Dvorak Jan 3 '14 at 5:37

polyglot, constant time, 8 characters


The trick is to realise what actually happens when you shuffle the array. Imagine the array as circular. Let us render the array starting at zero with the actual start/end signified with a bar:

0 1 2 3 4 5 6 7 8 9 |

Now, what actually happens when you shuffle the top three cards to the bottom and re-render:

7 8 9 0 1 2 3 4 5 6 |
0 1 2 3 4 5 6 | 7 8 9

Let's shuffle three more cards:

0 1 2 3 | 4 5 6 7 8 9

The only thing shuffles do is that they rotate the whole array, but don't change the ordering up to rotation.

So, if the array ends with a zero, we want to output the last index. The array has 53 elements, so the last index is 52.

If the array starts with a zero, it ends with its largest value. We want to output zero in this case.

Similarly, if the zero is n positions from the end, the last element of the array is n. Thus, the position of zero is the last position in the array, minus the value at the last position.

  • \$\begingroup\$ This is an example to 3 shuffles starting from no shuffles to 3. 0123456789 -> slice at 5 = 5678901234 -> slice at 8 = 8901234567. The solution is 2 in this case \$\endgroup\$ – Ilya Gazman Nov 12 '13 at 14:49
  • \$\begingroup\$ @Babibu the algorithm works correctly. 9-7=2 \$\endgroup\$ – John Dvorak Nov 12 '13 at 14:52
  • \$\begingroup\$ Oh sorry, just now understand it. Cool \$\endgroup\$ – Ilya Gazman Nov 12 '13 at 14:54
  • \$\begingroup\$ This is really the only possible answer. Though shorter code may be possible. \$\endgroup\$ – Cruncher Nov 12 '13 at 19:21

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