# Sort a stack of numbers in ascending order only using push

I have a stack of numbers ranging from 1 to 1 million representing a pile of numbered DVDs. Given the stack in random order I am to sort the stack by only taking an element from the stack and push it to the top and then calculate the minimum of such pushes necessary. My code is way too inefficient when dealing with large amounts of elements in the stack and I have a requirement that it must run in less than 4 seconds for any input size < 1 million. Right now it took me 28 secs to run with an input of 10 000 DVDs, so it's nowhere close to the goal!
How can I make the code more efficient?

import heapq

class Node:
# Creates a DVD node
# right och left corresponds to up and down in the stack
def __init__(self, value):
self.value = value
self.right = None
self.left = None

def __lt__(self, other): # necessary for comparing node size in the heap
return self.value < other.value

# the skeleton of the stack
def __init__(self):
self._first = None
self._last = None
self._length = 0

def length(self):
return self._length

def enqueue(self, dvd):
# Puts the DVD at the end of the "queue", i.e. on top of stack
ny = Node(dvd)
if self._first == None:
self._first = ny
else:
if self._last == None:
self._first.right = ny
self._last = ny
self._last.left = self._first
else:
previous = self._last
self._last.right = ny
self._last = ny
self._last.left = previous
self._length += 1
return ny

def push(self, node):
# Push the element to top
if node.left != None: # If node not first. The node can not be at the last spot because of criteria given in investigate_values
left_node = node.left
right_node = node.right
left_node.right = right_node
right_node.left = left_node
else:
right_node = node.right
right_node.left = None
self._first = right_node
node.right = None
node.left = self._last
self._last.right = node
self._last = node

def isEmpty(self):
if self._length == 0:
return True
else:
return False

def investigate_values(elements_to_be_moved, stack, count_movements, remember_used):
# If a DVD's number is higher than another DVD to the right(above in stack)
# it must be moved sooner or later to be in correct order. This is the fundamental idea of my entire algorithm
last_element = stack._last
lowest_number = last_element.value
while last_element:  # O(N)

if last_element.value > lowest_number: # Then last_element must be moved
if not remember_used[last_element.value-1]: # A new DVD not already in the heap , O(1)
heapq.heappush(elements_to_be_moved, last_element) # Heapq sortes the heap upon appending , O(logN)
count_movements += 1 # Every DVD's number is unique so no crashes will occur
remember_used[last_element.value-1] = True
if last_element.value < lowest_number:
lowest_number = last_element.value

last_element = last_element.left

return elements_to_be_moved, count_movements, remember_used

def move_elements(stack, elements_to_be_moved, nodes):
# pushes the dvd in the right order that gives us a sorted stack in least amount of movements
next_item = elements_to_be_moved
item_value = next_item.value
heapq.heappop(elements_to_be_moved) # O(logN)
first_element = stack._first
keep_going = True
stack.push(nodes[item_value]) # O(1)

return elements_to_be_moved

#Note: Must be in a special way, I don't use some variables but they have to be there beacuse of given conditions in the task.
number_of_input = int(input()) # How many different stacks, runs independently
save_data = []
save_numbers = []
dict_list = [] # For keeping the nodes
for instance in range(0,number_of_input):
how_long = input() # Ghost Variable, not used
save_data.append((input()).split())

for element in save_data:
hashnode = {}
for number in element: # O(N)
number = int(number)
node = stack.enqueue(number)
hashnode.update({number:node}) # Unique numbers, no duplicates
save_numbers.append(stack)
dict_list.append(hashnode)
return save_numbers, dict_list

def main():
for (stack, nodes) in zip(get_data, saved_nodes):
count_movements = 0 # Keeps track of how many pushes been executed, this gives the final answer
remember_used = [False]*(stack._length)
elements_to_be_moved = [] # Becomes a heap
keep_sorting = True
while keep_sorting:
elements_to_be_moved, count_movements, remember_used = investigate_values(elements_to_be_moved, stack, count_movements, remember_used)
try:
crash_variable = elements_to_be_moved # If error occurs the heap is empty and we're done

except IndexError:
print(count_movements)
break
else:
elements_to_be_moved = move_elements(stack,elements_to_be_moved, nodes)

main()

• Line 5: # right och left ..., funny ;) Jan 29 '16 at 9:31
• I'm somewhat confused with the text versus the code. The code clearly indicates you are using a three structure, but in the text you keep on talking about one stack and one push. Is this an attempt to solve The Kattis DVDs problem? Feb 23 '16 at 22:03
• Note that a "stack" of DVDs is not a stack data structure (whose operations would be push and pop). Mar 26 '16 at 8:36

As always, you can make your code much more efficient by analysing the problem algorithmically before you start coding. Please note that the problem - Kattis DVDs - does not ask you to sort the given input; it asks for the minimum number of steps needed for sorting in the manner described.

The problem is special in two regards. First, the input is a permutation of the numbers 1 through n. No duplicates, no gaps. Every number between 1 and n occurs exactly once. Second, the sorting procedure can only move DVDs to the back of the sequence (top of the stack); this means that the only DVDs which need not be moved are those which are part of the perfectly increasing subsequence that starts with the DVD labelled '1'. Everything else needs to be moved, and in the optimal case (minimal number of sorting steps) each out-of-order DVD will be moved exactly once.

Hence it is trivial to compute the minimum number of moves as asked in the programming challenge, like in this pseudo code:

int next = 1;

foreach (int x in input_vector)
if (x == next)
++next;

result = input_vector.Length - (next - 1);


That takes care of the Kattis challenge but the real challenge that presents itself here - should one be so inclined - is to actually sort the DVD stack in the described manner, because that turns out to be surprisingly tricky.

One could imagine processing the input in order to generate a list of numbers for a hypothetical robot, where each number k signifies 'pull the kth DVD from the stack and put it on top'. Or one could imagine writing a control program for said robot.

A simple strategy that sorts the stack using the minimal number of moves (and a lot of time) would be this:

• find the last DVD which is part of the perfectly increasing subsequence that starts with 1
• set k to the name of this DVD
• while ++k < n: find the DVD labelled k, pull it and put it on top

This algorithm is obviously quadratic in n and hence awfully slow.

Building a list of DVDs to be moved based on their initial positions is easy enough and efficiently done. A single pass through the input yields the initial slot indices for all DVDs that are not part of a perfect increasing subsequence that starts at #1, and sorting the pairs of slot index and DVD label into label order isn't rocket science.

However, when outputting the list of slot indices for the robot it is necessary to adjust the indices, because pulling a DVD causes all DVDs on top of it to move down by one. In other words, it is necessary to subtract from each index the number of lower slot indices which have already been output at that point. This boils down to a linear scan again, unless a data structure is employed that reduces the effort to log(n) or better.

The hypothetical robot control program could use the same strategy directly, or something analogous; in any case the same subproblem would be encountered. Hence the really interesting element in this challenge is the support structure for counting elements that are less in both label order and slot order.

The ideal structure for this purpose would be an ordered set with efficient rank computation, since the label element of each pair can be implied via query/insert order during the processing. Van Emde Boas trees come to mind but I've yet to meet anyone who'd program such a beast voluntarily, without a lot of green-backed inducement. A sorted vector would certainly do the job up to the point where insert cost becomes prohibitive, which is somewhere between 10^4 and 10^5. It would essentially replace the effort of the scan with a more efficient memory move but bigger inputs require something smarter.

In an imperative language the best bang for buck would be a simple insert-only form of a B-tree, or a hybrid like a summarising index on top of a simple bitset. The difficulty with the usual builtin tree-based maps/sets - apart from their poor performance - is the fact they normally don't expose the underlying tree structure, which makes it impossible to implement the log(n) rank order computation with a few simple tweaks.

A structure that I've used occasionally is a brutally simple ersatz B-tree with just two levels, which is comparatively easy to implement because it is insert-only and elements move only left to right overall. The frequency of inserts into the root vector - and hence the cost of moving stuff around in it - is effectively divided by the size of the leaves, and hence the 'reach' of the simple sorted vector solution gets effectively multiplied by the leaf capacity (modulo average utilisation).

The case under consideration is a bit more demanding than what I've used this for (e.g. questions like 'what are then ten million best results out of a few billion') because the top level needs to be scanned linearly towards the nearer end in order to determine the base rank of a given page. Again, the cost of the original linear scan gets effectively divided by the page size.

In a competitive situation - in order to achieve unrivalled speed - it might be worth it to increase the number of levels to three, or to switch completely to a full in-memory B-tree with page size equal to the L1 cache line size (64 bytes). The implementation would be much simpler than that for an augmented Red-Black tree and performance better by orders of magnitude. However, the latter variant is probably only viable in imperative languages with precise memory control, like C, C++ or Pascal.

Available B-tree libraries might not offer direct support for rank but those that come disguised as indexed in-memory datasets might have it, in the form of a virtual record number (row number).

This review is made under the assumptions that the challenge you're solving is the Kattis DVDs challenge, and the proposed solution has not been tested, but hopefully it does do the trick. But before proposing the new solution, lets review parts of your code for style:

• Comments for classes and functions should be docstrings – Instead of using ordinary comments, the style guidelines dictates that one should use """docstrings""" to comment classes and functions. This will in proper editors (and help) system be displayed next to the class or function.
• Use not self.first instead of self.first == None – As long as the the value, i.e. self.first, it is more common to use not self.first instead of actually comparing against None. The only case you don't want to do this is in is with code like not self.value, where self.value = 0 could be legal, but should possibly not trigger a case unless it was actually None. In other words, don't use not value if the value legally can be a falsy value.
• Be consistent and have spaces after operators – In code like move_elements(stack,elements_to_be_moved, nodes), be consistent and always add space after commas (and other operators), i.e. move_elements(stack, elements_to_be_moved, nodes). Similar stuff applies to expressions like remember_used[last_element.value - 1]
• Simplify truthy if conditions and blocks – When you repeat the condition in the response, it can usually be simplifed into a single statment. I.e. your isEmpty() can be written like this:

def isEmpty(self):
return self._length == 0

• Consider moving end-of-line comments to separate lines – Instead of pro-longing already long lines with comments at the end, I would suggest to move the comment to line ahead of it, and possible even add a blank line in front of the comment. (See examples below)
• Consider adding more vertical space – Adding vertical space can often ease reading code, and I tend to add some in front of if, while and for and in front of blocks of code.

## Algorithmic review with proposed solution

Often challenges like these present all needed information related to solving the challenge. On top of the information given, which includes a very specific remove element from middle of stack and leave at top, you've chosen to implement a tree structure, re-implement a stack/enqueue, and also using dicts for remembering touched values (or similar).

This kind is kind of like shooting sparrows with cannons. There is actually no need to use such big guns here, let's review parts of the challenge:

• Find a candidate in the stack, pull it out, and push it to the top of the stack:
• Use a loop to find candidate, keep track of index
• Remove this index, i.e. pop(index)
• Push to top of stack, or end of list, append(value)
• In order to reduce the number of moves, what are we sure to move to top? Well, any value larger than the current top of stack
• Repeat this until is sorted

Note that in the following code the stack is actually a native list with the top of stack being the end of the list. When looping and changing this list it is vital not to disturb the looping indexes whilst modifying the list. I've therefore opted to use an index variable, and looping from the end to start, and this turns out rather neat, it seems.

So here is an alternative solution to the challenge:

def move_to_top(stack, index):
"""Move element from index to top of stack."""
stack.append(stack.pop(index))

"""From inputfile read number of elements, and then stack it self."""

stack = [int(i) for i in inputfile.readline().split()]

return stack_length, stack

def sort_dvds(stack_length, stack):
"""Sort DVD's by pulling elements larger than the top and put it top."""
previous_move_count = -1
move_count = 0

# Repeat until stack is sorted
while previous_move_count != move_count:
previous_move_count = move_count

# Loop through from top till bottom, moving larger elements to top
for index in xrange(stack_length-1, 0, -1):
if stack[index - 1] > stack[-1]:
move_to_top(stack, index - 1)
move_count += 1

return move_count

def main():

with open("dvds.in") as inputfile:
for _ in xrange(testcases):

moves_needed = sort_dvds(stack_length, stack)
print("{}".format(moves_needed))

if __name__ == '__main__':
main()


I've also changed the logic into some more parts, so that there is one part, main(), which handle the overall logic, and a dedicated read for each test cases, read_testcase(), and a dedicated sorter for each case, sort_dvds(). This separations allows for a lower memory footprint, and in my point of view easier read of what happens in the different parts of the program.

Hopefully, this gives you some guidelines on how to improve your code in your future, and hopefully it solves the challenge within the time limits (and correctly :-) ).

• Have you checked whether your code computes the right result? It seems to me that it does not use the minimal number of moves as required by the set task... Mar 28 '16 at 14:06

My solution to this was to implement the Union Find algorithm. It is essentially a graph but you have a defined limit on storage; not to mention, it's trivial to implement here.

The two main operations you are concerned with are:

• Changing the parent of one node to 0, indicating it is at the top of the Stack. The parent is just its targeted index, whereas the node is the index it is currently located. This is done in O(1) time.
• The second thing you want to do is find where in the Stack a number is contained. This number will be referred to as the node, as aforementioned. The Union Find algorithm, by default, allows O(logN) time for searching. Although your version will be slightly more complicated (not by much, though) because you will have to find its position on the list, then change it.

A few important considerations to make are that.

Since the maximum size of the Stack S (or Union, I suppose), is between 1 and 1 000 000, and there are Q times, the maximum number of times you must search for and reassign the value of an index is S + Q. Notably, if all the indices are set to 0, there is evidently a problem because you cannot distinguish between the positions of various CDs in the Stack. You must create global accumulator that starts at Q and decrements one each time you assign a node's index to "0".

My first attempt at this was to keep track of the node alone, as this is significantly faster than a Stack. However, its time complexity was O(N^2) which proved slow for the problem considering I am using Java.

Good luck!

• Bottom line: Stack implementation is way too slow. You need an array of integers if you want to get it right in Python especially. Maybe in C++ you could get away with it with some heavy optimization, but now with Python... Aug 22 '17 at 13:51