Sort a stack of numbers in ascending order only using push

Question

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
class LinkedQ:
 # 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[0] 
 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 
def read_data():
#Reads input 
#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:
 stack = LinkedQ()
 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():
 get_data, saved_nodes = read_data()
 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[0] # 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()

• 301_Moved_Permanently: Line 5: # right och left ..., funny ;)
• holroy: 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?
• 200_success: Note that a "stack" of DVDs is not a stack data structure (whose operations would be push and pop).

Answer 1

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).

Answer 2

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))
def read_testcase(inputfile):
 """From inputfile read number of elements, and then stack it self."""
 stack_length = int(inputfile.readline())
 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:
 testcases = int(inputfile.readline())
 for _ in xrange(testcases):
 stack_length, stack = read_testcase(inputfile)
 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 :-) ).

• DarthGizka: 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...

Answer 3

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!

• Imagine Dragons: 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...