A sequence of items can be sorted in increasing order using a technique that is inspired by the Patience1 card game. Sorting is done in two phases. First, the items are placed one by one in a series of stacks according to these rules:

  1. initially there are no stacks

  2. the first item forms a new stack that only contains the item

  3. each subsequent item $$i$$ is placed on the leftmost stack whose top item is greater than or equal to item $$i$$; if all top items are smaller than item $$i$$, the item forms a new stack to the right of all existing stacks

When there are no more items to be placed, the sorted sequence is recovered by repeatedly picking off the smallest visible item. The visible items are the items on top of the stacks.

stacks
Stacks after all items have been placed on a stack.

For instance, consider sorting the integer sequence (4 3 9 1 5 2 7 8 6) using the Patience sorting technique. The first stack gets 4 and 3. Since 9 is larger than 3, it starts a second stack, 1 goes on the first stack, then 5 and 2 go on the second stack. At this point the first stack (top to bottom) consists of (1 3 4), the second stack consists of (2 5 9), and the remaining sequence consists of the integers (7 8 6). Now 7 goes on a third stack, 8 goes on a fourth stack, and 6 goes on top of the 7 in the third stack. With all the items placed, 1 is collected from the first stack, 2 from the second stack, 3 and 4 from the first stack, 5 from the second stack, 6 and 7 from the third stack, 8 from the fourth stack and 9 from the second stack.

Assignment

An item is represented as an integer (int). A stack of items is represented as a list, where the first element is the item on top of the stack and the last element is the item at the bottom of the stack. A series of stacks that are next to each other is represented as a list, where the first element is the leftmost stack and the last element is the rightmost stack.

Define a class PatienceSorter that can be used to sort a sequence of items in increasing order using the Patience sorting technique. Upon creation of a new object of the class PatienceSorter there isn't any stack of items yet. The class must support at least the following methods:

Example

>>> sorter = PatienceSorter()
>>> sorter.stacks()
[]
>>> sorter.stack_count()
0
>>> sorter.add_item(4).stacks()
[[4]]
>>> sorter.stack_count()
1
>>> sorter.add_item(3).stacks()
[[3, 4]]
>>> sorter.add_item(9).stacks()
[[3, 4], [9]]
>>> sorter.stack_count()
2
>>> sorter.add_item(1).stacks()
[[1, 3, 4], [9]]
>>> sorter.add_item(5).stacks()
[[1, 3, 4], [5, 9]]
>>> sorter.add_item(2).stacks()
[[1, 3, 4], [2, 5, 9]]
>>> sorter.add_item(7).stacks()
[[1, 3, 4], [2, 5, 9], [7]]
>>> sorter.stack_count()
3
>>> sorter.add_item(8).stacks()
[[1, 3, 4], [2, 5, 9], [7], [8]]
>>> sorter.add_item(6).stacks()
[[1, 3, 4], [2, 5, 9], [6, 7], [8]]
>>> sorter.stack_count()
4
>>> sorter.item_count()
9
>>> sorter.remove_item()
1
>>> sorter.stacks()
[[3, 4], [2, 5, 9], [6, 7], [8]]
>>> sorter.remove_item()
2
>>> sorter.stacks()
[[3, 4], [5, 9], [6, 7], [8]]
>>> sorter.remove_item()
3
>>> sorter.stacks()
[[4], [5, 9], [6, 7], [8]]
>>> sorter.remove_item()
4
>>> sorter.stacks()
[[5, 9], [6, 7], [8]]
>>> sorter.stack_count()
3
>>> sorter.remove_item()
5
>>> sorter.stacks()
[[9], [6, 7], [8]]
>>> sorter.remove_item()
6
>>> sorter.stacks()
[[9], [7], [8]]
>>> sorter.remove_item()
7
>>> sorter.stacks()
[[9], [8]]
>>> sorter.remove_item()
8
>>> sorter.stacks()
[[9]]
>>> sorter.remove_item()
9
>>> sorter.stacks()
[]
>>> sorter.remove_item()
Traceback (most recent call last):
AssertionError: no more items

>>> sorter = PatienceSorter()
>>> sorter.add_items([7, 5, 2, 1, 8, 6, 3, 9, 4]).stacks()
[[1, 2, 5, 7], [3, 6, 8], [4, 9]]
>>> sorter.stack_count()
3
>>> sorter.item_count()
9
>>> sorter.remove_items()
(1, 2, 3, 4, 5, 6, 7, 8, 9)
>>> sorter.stacks()
[]
>>> sorter.stack_count()
0
>>> sorter.item_count()
0

Resources