17
$\begingroup$

Let me start with a formulation of the problem for people who aren't familiar with Magic: the Gathering.


You have a stack of distinct cards face-down. You can apply the following actions arbitrarily many times:

  1. Look at the top two cards of the stack.
  2. Return them to the stack
    1. both cards on top of the stack in arbitrary order
    2. or one card on the bottom of the stack, the other on top
    3. or both cards on the bottom of the stack in arbitrary order.

Can you arrange the cards into any order, even if it takes a long time? If so, how?


Version for Magic: the Gathering players including context:

You have Preston, the Vanisher and Charming Prince on the board. Now you play Felidar Guardian.

This creates an infinite loop:

  1. Felidar Guardian enters the battlefield
  2. You can choose to exile and return back to the battlefield (= flicker) Charming Prince. This causes his ability to trigger, and you choose to flicker Felidar Guardian.
  3. Felidar Guardian enters the battlefield without being cast.
  4. You flicker Charming Prince, which lets you choose (amongst others) to scry 2.
  5. Preston, the Vanisher's ability is triggered, creating a $0/1$ token copy of Felidar Guardian (and of Charming Prince, but let's ignore that for now).
  6. The $0/1$ token copy of Felidar Guardian enters the battlefield.
  7. You can choose to flicker the non-token Felidar Guardian.
  8. Back to step 3.
So, effectively you have an infinite supply of the enter-the-battlefield effects of Charming Prince. Assuming you will use some of the tokens generated this way for the  ability of Preston, the Vanisher to exile all1 nonland permanents of your opponents, you now want to make sure your next card draws facilitate winning the game. Therefore, the question is: Can you arrange the cards in your entire deck into any order you wish? If so, how?

1: With a slightly different arrangement of the enter-the-battlefield abilities you can also flicker your lands, effectively untapping them. You therefore also have unlimited mana.

$\endgroup$
14
  • $\begingroup$ this doesn’t answer your question but why is a token of felidar guardian created the first time through the loop? I’m guessing the first time through, instead of scry 2 you use charming prince’s ability to flicker felidar guardian or something? (I have only a little understanding of how magic the gathering works) $\endgroup$
    – SQLnoob
    Feb 25 at 3:23
  • 2
    $\begingroup$ @justhalf Here is the formal definition: "Scry N (Look at the top N cards of your library, then put any number of them on the bottom of your library and the rest on top in any order.)" It contains both of the steps in the puzzling version. $\endgroup$
    – A. P.
    Feb 25 at 14:41
  • 1
    $\begingroup$ @Sconibulus This loop is fine competitively. Four Horsemen runs into the slow play issue because you can't choose a number N and also say what the game state will be after N loops. With the scry sort you are able to choose a finite N and also describe the game state deterministically as long as N is big enough. The fact that the library is still technically hidden information is fine since we the player can still state with 100% certainty what state the library will be in. $\endgroup$ Feb 25 at 19:14
  • 1
    $\begingroup$ Read better the Charming prince. He doesn't flicker stuff, you only get the creature back at the end of turn, hence there is no infinite loop. $\endgroup$
    – pqnet
    Feb 26 at 12:28
  • 2
    $\begingroup$ @pqnet it still works. You start it during your main phase; the loop runs at the beginning of your end step. It's all Felidar Guardian though: once it enters without being cast, it doubles up: the real one flickers anything in play; the token flickers the real one. Loop until you get bored. That loop lets you fast-flicker the charming prince. once per cycle, which all happen immediately. $\endgroup$
    – fectin
    Feb 26 at 16:38

4 Answers 4

16
$\begingroup$

Assume the N cards are labeled with their desired order, 1 through N.

  1. Compare the top two cards and place the smaller of the two on the bottom.
  2. Repeat step 1 (N − 1) times.
  3. Move the top card to the bottom.
  4. Repeat steps 1 through 3 (N − 1) times.

This executes a:

Bubble sort.

To see how:

First note that by moving the top card to the bottom, we can cycle through the whole deck in N moves. Step 1 is equivalent to swapping the two cards if they are unordered, then moving the top card to the bottom. By repeating this step we cycle through the deck, examining successive pairs in turn, which is the inner loop of bubble sort. Remember we need N moves to cycle through the whole deck, so we add step 3 to get back to our original position in the deck. Finally, repeating 1 through 3 executes the outer loop of bubble sort.

We can optimize the algorithm by:

Stopping at step 4 when, in one loop of steps 1 through 3, we move the top card to the bottom in every move. This is equivalent to stopping when every pair is ordered, which is the standard version of bubble sort. A further optimization is to implement the "optimized" variant of bubble sort where we only consider the first N − i pairs on the i-th loop of step 4; we can't actually skip over the last i − 1 pairs, since we need cycle the deck back to the starting position, but we can step through the pairs two at a time by moving both the top cards to the bottom in each step, which reduces the total number of moves required by about 25%.

$\endgroup$
0
7
$\begingroup$

This was getting too long for a comment, so I'm writing an answer.

Just a heads up for when you run this in your EDH deck, Prince is a blink, not a flicker. This means that the Felidar will return at the next end step. Your loop should look like this:

  1. Prince blinks Felidar

  2. At the next end step, Felidar ETB

  3. Put Preston's trigger (token copy of Felidar) on the stack.

  4. Put Felidar's trigger (target Prince) on the stack.

  5. Felidar resolves, flickering Prince. (Preston is still on the stack)

  6. Prince ETB. Don't worry about stack order for Prince and Preston, but make sure Prince and the token both scry. (Preston's Felidar trigger is still on the stack)

  7. Prince, and the token copy both resolve, letting you scry 2 twice. (Preston's Felidar trigger is still on the stack)

  8. Preston's Felidar trigger resolves. The token ETB and targets the non-token Felidar.

  9. Felidar ETB -> Go to step 3.

This gives you two scry 2 triggers per loop, but they all happen at the beginning of your end step. To make sure it's during one of your main phases, you want to flicker Felidar with something else. Also, there are plenty of other permanents which scry 2 when they ETB, so the Prince is not the only option.

As 2012rcampion stated in their answer, this means that you:

can bubble sort your deck and have whatever you want.


Update:

If you want to perform it in fewer steps, then use the loop above with a permanent that can scry more than the Prince, such as these cards. But the thopter won't work if Preston is your commander.

$\endgroup$
3
  • $\begingroup$ " Prince is a blink, not a flicker. " First time I've heard of this distinction - surprised that flickerwisp doesn't flicker :o $\endgroup$
    – Fadeway
    Feb 26 at 8:52
  • $\begingroup$ Myr custodian will let the enemy scry 1 as many time as they want. While that isn't enough to sort their deck as well, they can choose any single card to put on top and very likely they'll draw it before we can draw anything on our side $\endgroup$
    – pqnet
    Feb 26 at 13:22
  • 1
    $\begingroup$ @pqnet so Oltec Archaeologists or Threefold Signal would be better. They let you cry 3, so you can sort your deck in fewer repetitions of the Felidar-Preston cycle. $\endgroup$ Feb 26 at 23:16
5
$\begingroup$

There is a simpler algorithm than bubble sort if you can afford infinite scry 2 operations.

Infinite scry 2 operation allows to perform 2 different operations:

  • scry two top or first bottom and second top allows you to rotate your deck until the card you want is on top
  • scry first top second bottom let you do the rotate the deck in whatever position you like while keeping a card out of the rotation

With these two operation it's easy to see that you can just scroll to a card, pick it up and keep scrolling until you find the place where you want to put it, then repeat until you have all the cards in order. This is akin to a selection sort. Compared to bubble sort it has these advantages:

  • it is very simple and hard to mess up in an actual game if you have to do it (just look for the card that you want, then put it where you want).
  • it is easy to explain to your opponent to convince him that it would be faster if he just allows you to pick your deck up and reorder the cards however you want because you are basically allowed to do so (you are more likely to get a concession out of them since you'll be having a gazillion life point and a gazillion felidar tokens and a gazillion mana and he likely doesn't have any permanent at that point)
$\endgroup$
3
$\begingroup$

It is known (pretty standard introductory abstract algebra exercise) that for any n>1, the symmetric group on n elements is generated by the two permutations (123...n) and (12). And it is not difficult to implement either using your operations.

  • The (12) permutation is done by swapping the top two cards
  • The (123...n) permutation is performed by moving the top card to the bottom and leaving the second card on the top

(Well, almost. It's a cyclical permutation and an adjacent transposition, and that's what matters, but tecnically, the second point yields the inverse of (123...n). To actually do (123...n), you would have to perform the step n-1 times.)

Alternately, the symmetric group is also generated by the collection of all the adjacent transpositions (i(i+1)). These are performed by the following steps:

  1. Move cards cyclically to the bottom until card i is on the top
  2. Swap the two top cards
  3. Move cards cyclically to the bottom until you have moved a total of n cards cyclically between point 1 and point 3
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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