How to sort your library in exactly 51,271 steps | Hacker News Reader

How to sort your library in exactly 51,271 steps

david.kolo.ski

94 pointstaintegral27 comments

I don't think this should legally qualify as a loop because per 4.4 Loops the loop actions must be identical and cannot contain conditionals. You're changing the order you put the cards in on the bottom for every step. The MTG Judge blog seems to not consider this though and allows infinite Petal casts to sort the library, I guess it doesn't count as a meaningful decision for the purposes of the loop.

The big problem arises because players are able to interrupt after a set number of iterations of a loop to so what does your deck look like 25k iterations into the 51271 steps required to sort a 60 (edit: 59) card library?

I love how the rules imply that not providing these proofs and applying them is against the rules.

It's also a matter of table courtesy. When I play Commander format, sometimes one person dying is enough for the table to recognize who has the 'best numbers on board'. Instead of grinding things out, it's sometimes more fun overall to call the game and start a new one.

Also, see what can happen with long-running combos, and it'll make a lot more sense: https://youtu.be/EXRnOhUfKwo

I love the whimsy of this. I'm not familiar with Magic, but now I wonder - is Magic Turing complete? And of course the answer appears to be yes! [0]

[0] https://arxiv.org/abs/1904.09828

I might be misunderstanding the ruling, but I believe if your play involves an infinite loop that cannot resolve, you tie the game. Combine that with the fact the game is Turing complete, and this makes it such that you could force a game state where you must solve the halting problem in order to determine if you draw or not.

If the game state is "meaningfully changed" each iteration then it is considered a non-deterministic loop and it cannot be shortcut.

Here’s a live demo: https://youtu.be/pdmODVYPDLA

Here's your link without the creepy Google tracking:

https://youtu.be/pdmODVYPDLA

Wouldn't it make more sense to compute a single number of operations that is sufficient to obtain any possible order, for any number of cards in your library smaller than 60? In this way one would have to memorize just a single number and not the whole table.

That should be valid. Though if your opponent knows the real number you need to hit and can interrupt your cycle they could choose a lower number in which case I guess you'd be best off just shuffling your library to 'resolve' the number of loops cast.

I'd do it for 98 cards though so you could apply the number in (c)EDH where you're likely to actually see this combo happen though. It would still be valid because if you can sort your library to an arbitrary state S in N moves you can sort it to a state S' that could result in S in any number of moves greater than N as well.

So in the case of N divisible by 3, there are impossible end states. But can you still go ahead and declare that you will sort your library within the possible end states? If so how would one prove that one did not step outside of possible states without showing the cards themselves?

Maybe one could first divide the library into 3 piles and sort within each piles first.

Well, due to it being divisible by 3, possible end states just mean that you can just make an arbitrary permutation within each triplet of cards. But you can do that simply in exactly N/3 casts, at which point it's probably just easier to simulate them.

As the author notes, these numbers are upper bounds for a fixed trivial strategy. That makes me wonder, which permutations (for each size) are the most difficult to achieve using an optimal strategy? How might we solve such a problem short of brute force?

I've worked out a few such puzzles involving permutations and the answer always seems to be either "one vexatious ordering" or "half of all permutations"

A variant of bubble sort I think would work. Taking into consideration the 'rotating index', each operation would correctly order three cards within the rotating index.

In each N pass, we should see each element at least 3 times, and it must advance toward it's desired position at least once. since it can't be at the 'wrong' end of the triple multiple times.

Worst case in N^2 ops we should be done.

> as long as the number of cards in it is not divisible by three or is equal to three

I'm curious about the distinction here. Is it needed? Isn't N divisible by N? Or is there a mathematically-meaningful difference?

n=3 is the exception, but if the library is otherwise divisible by three, you can't sort it in it's entirety.

as example: the library has 6 cards; the spell allows you to choose the top 3 cards and put them into the bottom in any order. So the spell only allows you to sort either the first set of 3 or the second set of 3 top cards, and there is no way to intermix the cards from the two sets of three => no way to sort the entire library.

Hope this make senses as to why N=3 is an exception as well!

Note it's "not divisible by three". n = 3 is the only exception.

Oh, I parsed that as "(is not ((divisible by three) or (is equal to three)))" and didn't think further.

Math and MTG? This is why I love HN

Reply on news.ycombinator.com