3 ms·
And yet sorting a deck of cards is vastly easier than solving a Rubik's Cube. Which shows that these numbers don't at all measure puzzle difficulty.
by BurningFrog 8y ago
And yet sorting a deck of cards is vastly easier than solving a Rubik's Cube.
Which shows that these numbers don't at all measure puzzle difficulty.
- Dylan16807 8y agoEasier by what metric, though? Someone with moderate practice at both can do the cube faster. Someone with zero practice won't know what you mean by "sorting" a deck of cards. The cards only win at going backwards from goal to algorithm. And do we have any idea what God's Number is for sorting a deck of cards?
- rocqua 8y agoDepending on what you will define as an 'operation' there are some probably some easy numbers. I think the simplest answer is 52. You need to place each card correctly once. Things get complicated if you account for searching in the deck, but we don't account for looking at the rubiks cube either. A more interesting question is 'what if we count how far we need to move the card' (i.e. moving it from position 1 to 52 is 52 steps, and from 1 to 3 is only 2 steps). This is a question of simple group theory though. Shuffling cards is the group S_52. The 'moving a card one position' is working with 51 simple operations of swap (idx, idx + 1). This is essentially bubble sort.
- BurningFrog 8y agoI can also do the cube faster. That's completely separate from how easy the problem is to solve for a novice. Yes, obviously the solver has to understand what the desired solved state is in each case. If you can't see that sorting a deck of cards is easier, I doubt I can explain it to you, but the metric I'd use is give each problem to 100 people, and see how well each group does.
- jerf 8y ago"And do we have any idea what God's Number is for sorting a deck of cards?" It depends on your definition of sorting. Since we have a known, finite, compact set of incoming inputs, essentially the numbers 1-52, as rocqua says we can use a bin sort with 52 bins and sort the cards in essentially 52 operations. This is physically practical as well. Generally the "constant overhead" on it is such that people will sort with something more like a merge sort, but it's certainly completely practical to find a space large enough to hold the entire deck laid out physically. If you limit sorting to the computer science sense of the term, in which the sort must be accomplished by swaps, I expect it could be worked out pretty easily by people skilled in the art of sorting, again because the small constant size and input makes it relatively easy. I know it can be proved that this style of sort can't take less than O(n log n) comparisons, but I'm not 100% sure I can guarantee it's literally ciel(52 * log2 52). Somebody else may be able to.