Order the deck
Arrange a deck so that dealing it by a fixed rule shows the cards in increasing order, by simulating the rule on positions instead of cards. About 16 minutes.
Work backwards with positions
A dealer follows a rule: reveal the top card, then move the next top card to the bottom, and repeat. You want the revealed cards to come out in increasing order. Which arrangement of the deck makes that happen?
The rule moves places, not values. Use a queue of place numbers 0 to n minus 1, and run the rule on it. The first place revealed must hold the smallest card.
from collections import deque q = deque(range(5)) # 0, 1, 2, 3, 4 spot = q.popleft() # 0
Reveal place 0: it gets 2. Place 1 moves to the back. Queue: 2, 3, 4, 5, 6, 1.
Then move one to the back
After revealing a place, the rule says to move the next top card to the bottom. On the queue, that means taking the new front place off and adding it to the back.
If the queue is empty after a reveal, there is nothing left to move, so check before moving. When the sorted cards run out, every place has been filled, and the result is the arrangement.
q.append(q.popleft()) # to the back
Why can we run the rule on place numbers instead of on the actual cards?
- AThe rule only moves places around and never looks at card values
- BThe deck is already sorted
- CCards are slower to move than numbers
Show the answer
The rule only moves places around and never looks at card values. So the order in which places are revealed is the same for every deck of that size.
Reveal cards in increasing order
You are given an integer array deck with distinct values. You may arrange the deck in any order, and then it is dealt like this: reveal the top card and take it away, then move the next top card to the bottom of the deck, and repeat until all cards are revealed. Return the arrangement (top card first) for which the revealed cards come out in increasing order.
deck = [17, 13, 11, 2, 3, 5, 7] → [2, 13, 3, 11, 5, 17, 7]
1 ≤ length of deck ≤ 100,000 · 1 ≤ deck[i] ≤ 1,000,000 · all values are different