From time to time, it’s good to sharpen ones skills by doing a puzzle or two. Personally, I enjoy reviewing interview questions. They provide me with both experience with interview questions, and often fun subtle tricks.
The problem I found today was probably one of my favorites[1]:
You are given a deck containing n cards. While holding the deck:
- Take the top card off the deck and set it on the table
- Take the next card off the top and put it on the bottom of the deck in your hand.
- Continue steps 1 and 2 until all cards are on the table. This is a round.
- Pick up the deck from the table and repeat steps 1-3 until the deck is in the original order.
Write a program to determine how many rounds it will take to put a deck back into the original order.
At first, this problem appears pretty straight forward. An example round looks like the following:
Sample input/output with 6 cards:
Round 0: 1 2 3 4 5 6
Round 1: 4 6 2 5 3 1
Round 2: 5 1 6 3 2 4
Round 3: 3 4 1 2 6 5
Round 4: 2 5 4 6 1 3
Round 5: 6 3 5 1 4 2
Round 6: 1 2 3 4 5 6
It takes 6 rounds to get back!
However, it quickly becomes a challenge, let’s walk through it shall we, starting with the naive solution.
Naive Solution
Constructing a naive solution is relatively easy. We basically just have to walk through the steps, and code it verbatim. To recap, the first three steps are:
- Take a card off the top of the deck and set on table
- Take a card off the top of the deck and put on bottom
- Repeat steps one and two, until there are no cards in hand
That is what is called a round. To code this, we will assume that we have a deck in array form. Then we can create a new empty array called table which we fill from the deck in hand.
The code below completes one round:
Once we have the code for one round, we can run through an entire game simulation. We generate a deck, then run through the rounds until the deck is the same as the original. Finally, we return the number of rounds we have to iterate through.
Now, if we run through the decks of the size 2 to 99 we get the following number of rounds per deck size (i’ll only display the last 25):
Size of Deck : # of Rounds
75 : 66
76 : 50
77 : 621
78 : 78
79 : 24
80 : 210
81 : 9690
82 : 55440
83 : 3465
84 : 1122
85 : 5040
86 : 370
87 : 87
88 : 720
89 : 630
90 : 90
91 : 783
92 : 92
93 : 78
94 : 50
95 : 95
96 : 96
97 : 6435
98 : 132
99 : 780
This takes a total of 5.56 seconds. That’s not exactly fast.If we then try our application against a deck size that is 10,000 cards it will basically never finish.
In other words, the naive approach works, but not very well. There should be a better solution, because there is definitely a pattern to solving this problem. The code to run this yourself is found on my github, under naive.py.
Towards an Improved Solution
To discover an improved solution, lets first take a look at what the basics of the problem are. Every round there is a group of cards that rotates positions within the deck (based on which stays on the hand and gets placed on the table).
A great example of this comes from this stackoverflow post:
Consider a deck of 11 cards. The state of the deck for the first few rounds is:
ABCDEFGHIJK FJBHDKIGECA KCJGHAEIDBF ABCIGFDEHJKNotice that during the first round, A moved to the location where K was, K moved where F was, and F moved where A was. So A,F, and K form a rotation group of size 3. If we ignore the other letters and just watch A,F, and K, we see that AFK return to their original positions every three rounds.
Likewise
BCJform a group of 3, andDEGHIform a group of 5. Since some of the cards return to their original position every 3 rounds, and the others return every 5 rounds.
This is very similar to the mathematical solution to the Rubik’s Cube. Essentially, what was previously described as a rotation group could be considered a canonical cycle:
If P consists of multiple cycles of varying length, then the order of that permutation is n, since applying P n times returns the beginning state. If P consists of multiple cycles of varying length, then the order is the least common multiple of the lengths of the cycles, since that number of cycle steps will return both chains to their starting states.
In other words, the least common multiple of every rotation group determines how many times the deck will need to be rotated to get back to it’s original position.
You can think of it this way, if we have one rotation group that is of size 3 and one of size 5 it takes 3 * 5 or 15 rotations to get back to the original position (or LCM(3, 5) = 15). This is because we are looking for all permutations of the deck following that pattern. After all permutations of card positions the deck that could exist (following that pattern of the game) have been cycled through, the card positions will return to their original positions.
With this insight, we can dramatically reduce the amount of computation to solve the problem.
Improved Solution
To begin to improve our solution, we should first list the design of our program:
- Complete one round (or steps 1 – 3), and save the position of the cards in the deck.
- Determine the size of the rotation groups (or cycles) between the cards after one round, and the original positions inside the deck.
- Determine the lowest common multiple between the size of each group.
In code, this is all relatively straight forward. The first step is simple running through a single round (which we can use our previous code to do):
After we have one round complete, we can attempt to determine the number of rotation groups or cycles between the initial deck configuration of the cards (which were in numerical order: 1, 2, …, n) to the current card positions:
The output of the function above is an array containing the group size for every card based on its index. For example, if we run a deck of size 13 (after one round), through the function above, we get:
[4, 1, 4, 4, 3, 4, 4, 3, 1, 4, 3, 4, 4]
Giving us the total number of rounds, 4 * 3 * 1, the least common multiple between each of the groups. This is also basically our last function we need to build. AKA finding the least common multiple (LCM) of the groups in the deck:
With this improved version of the program, if we again run through the decks that are the size 2 to 99 we get the following number of rounds per deck size (i’ll only display the last 25):
Size of Deck : # of Rounds
75 : 66
76 : 50
77 : 621
78 : 78
79 : 24
80 : 210
81 : 9690
82 : 55440
83 : 3465
84 : 1122
85 : 5040
86 : 370
87 : 87
88 : 720
89 : 630
90 : 90
91 : 783
92 : 92
93 : 78
94 : 50
95 : 95
96 : 96
97 : 6435
98 : 132
99 : 780
This is exactly the same as before, but it takes only 0.040989 seconds. Less than one hundredth of the time of the original naive version of the application. With the improved version of the code, it is also possible (in seconds or less) to calculate the number of rounds it takes to return 10,000 cards to the original order of the deck:
10000 cards => 515373532738806568226400 rounds
Although there may still be some rounding errors. You can find the code to run this yourself on my github, under improved.py.
Closing Remarks: Runtime
Usually, when trying to construct a solution of this type you are looking for running time, in big-O notation. In this case, the running time is based off the number of rounds we have to iterate through to get the deck back to the original ordering.
The naive approach just simulates this and counts the number of rounds. Alternatively, our improved solution calculates the simulation time. It accomplishes this in O(nm) time, where n is the size of the deck and m is the least common multiple.