Stacks

Download exercises zip

Browse files online

0. Introduction

References

• theory: https://sciproalgo2019.readthedocs.io/slides/Lecture5.pdf

• stack definition on the book

and following sections :

• Stack Abstract Data Type

• Implementing a Stack in Python

• Simple Balanced Parenthesis

• Balanced Symbols - a General Case

What to do

• unzip exercises in a folder, you should get something like this:

stacks
    stacks.ipynb
    capped_stack.py
    capped_stack_sol.py
    capped_stack_test.py
    ...
    jupman.py
    sciprog.py

• open the editor of your choice (for example Visual Studio Code, Spyder or PyCharme), you will edit the files ending in .py files

• Go on reading this notebook, and follow instuctions inside

1. CappedStack

You will try to implement a so called capped stack, which has a limit called cap over which elements are discarded.

• Your internal implementation will use python lists

• Please name internal variables that you don’t want to expose to class users by prepending them with one underscore '_', like _elements or _cap

  • The underscore is just a convention, class users will still be able to get internal variables by accessing them with field accessors like mystack._elements

  • If users manipulate private fields and complain something is not working, you can tell them it’s their fault!

• try to write robust code. In general, when implementing code in the real world you might need to think more about boundary cases. In this case, we add the additional constraint that if you pass to the stack a negative or zero cap, your class initalization is expected to fail and raise a ValueError.

• For easier inspection of the stack, implement also an __str__ method so that calls to print show text like CappedStack: cap=4 elements=['a', 'b']

IMPORTANT: you can exploit any Python feature you deem correct to implement the data structure. For example, internally you could represent the elements as a list , and use its own methods to grow it.

QUESTION: If we already have Python lists that can more or less do the job of the stack, why do we need to wrap them inside a Stack? Can’t we just give our users a Python list?

QUESTION: When would you not use a Python list to hold the data in the stack?

Notice that:

• We tried to use pythonic names for methods, so for example isEmpty was renamed to is_empty

• In this case, when this stack is required to pop or peek but it is found to be empty, an IndexError is raised

CappedStack Examples

To get an idea of the class to be made, in the terminal you may run the python interpreter and load the solution module like we are doing here:

from capped_stack_sol import *

s = CappedStack(2)

print(s)

CappedStack: cap=2 elements=[]

s.push('a')

print(s)

CappedStack: cap=2 elements=['a']

s.peek()

'a'

s.push('b')

s.peek()

'b'

print(s)

CappedStack: cap=2 elements=['a', 'b']

s.peek()

'b'

s.push('c')  # exceeds cap, gets silently discarded

print(s)   # no c here ...

CappedStack: cap=2 elements=['a', 'b']

s.pop()

'b'

print(s)

CappedStack: cap=2 elements=['a']

s.pop()

'a'

s.pop()   # can't pop empty stack

---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-41-c88c8c48122b> in <module>()
----> 1 s.pop()

~/Da/prj/sciprog-ds/prj/stacks/capped_stack_sol.py in pop(self)
     63         #jupman-raise
     64         if len(self._elements) == 0:
---> 65             raise IndexError("Empty stack !")
     66         else:
     67             return self._elements.pop()

IndexError: Empty stack !

s.peek()     # can't peek empty stack


---------------------------------------------------------------------------
IndexError                                Traceback (most recent call last)
<ipython-input-18-f056e7e54f5d> in <module>()
----> 1 s.peek()

~/Da/prj/sciprog-ds/prj/stacks/capped_stack_sol.py in peek(self)
     77         #jupman-raise
     78         if len(self._elements) == 0:
---> 79             raise IndexError("Empty stack !")
     80
     81         return self._elements[-1]

IndexError: Empty stack !

Capped Stack basic methods

Now open capped_stack.py and start implementing the methods in the order you find them.

All basic methods are grouped within the CappedStackTest class: to execute single tests you can put the test method name after the test class name, see examples below.

1.1 __init__

Test: python3 -m unittest capped_stack_test.CappedStackTest.test_01_init

1.2 cap

Test: python3 -m unittest capped_stack_test.CappedStackTest.test_02_cap

1.3 size

Test: python3 -m unittest capped_stack_test.CappedStackTest.test_03_size

1.4 __str__

Test: python3 -m unittest capped_stack_test.CappedStackTest.test_04_str

1.5 is_empty

Test: python3 -m unittest capped_stack_test.CappedStackTest.test_05_is_empty

1.6 push

Test: python3 -m unittest capped_stack_test.CappedStackTest.test_06_push

1.7 peek

Test: python3 -m unittest capped_stack_test.CappedStackTest.test_07_peek

1.8 pop

Test: python3 -m unittest capped_stack_test.CappedStackTest.test_08_pop

1.9 peekn

Implement the peekn method:

def peekn(self, n):
    """
        RETURN a list with the n top elements, in the order in which they
        were pushed. For example, if the stack is the following:

            e
            d
            c
            b
            a

        peekn(3) will return the list ['c','d','e']

        - If there aren't enough element to peek, raises IndexError
        - If n is negative, raises an IndexError

    """
    raise Exception("TODO IMPLEMENT ME!")

Test: python3 -m unittest capped_stack_test.PeeknTest

1.10 popn

Implement the popn method:

def popn(self, n):
    """ Pops the top n elements, and RETURN them as a list, in the order in
        which they where pushed. For example, with the following stack:

            e
            d
            c
            b
            a

        popn(3)

        will give back ['c','d','e'], and stack will become:

            b
            a

        - If there aren't enough element to pop, raises an IndexError
        - If n is negative, raises an IndexError
    """

Test: python3 -m unittest capped_stack_test.PopnTest

1.11 set_cap

Implement the set_cap method:

def set_cap(self, cap):
    """ MODIFIES the cap, setting its value to the provided cap.

        If the cap is less then the stack size, all the elements above
        the cap are removed from the stack.

        If cap < 1, raises an IndexError
        Does *not* return anything!

        For example, with the following stack, and cap at position 7:

        cap ->  7
                6
                5  e
                4  d
                3  c
                2  b
                1  a


        calling method set_cap(3) will change the stack to this:

        cap ->  3  c
                2  b
                1  a

    """

Test: python3 -m unittest capped_stack_test.SetCapTest

2. SortedStack

You are given a class SortedStack that models a simple stack. This stack is similar to the CappedStack you already saw, the differences being:

• it can only contain integers, trying to put other type of values will raise a ValueError

• integers must be inserted sorted in the stack, either ascending or descending

• there is no cap

Example:

     Ascending:       Descending

        8                 3
        5                 5
        3                 8

from sorted_stack_sol import *

To create a SortedStack sorted in ascending order, just call it passing True:

s = SortedStack(True)
print(s)

SortedStack (ascending):   elements=[]

s.push(5)
print(s)

SortedStack (ascending):   elements=[5]

s.push(7)
print(s)

SortedStack (ascending):   elements=[5, 7]

print(s.pop())

7

print(s)

SortedStack (ascending):   elements=[5]

print(s.pop())

5

print(s)

SortedStack (ascending):   elements=[]

For descending order, pass False when you create it:

sd = SortedStack(False)
sd.push(7)
sd.push(5)
sd.push(4)
print(sd)

SortedStack (descending):   elements=[7, 5, 4]

2.1 transfer

Now implement the transfer function.

NOTE: function is external to class SortedStack, so you must NOT access fields which begin with underscore (like _elements), which are meant to be private !!

def transfer(s):
    """ Takes as input a SortedStack s (either ascending or descending) and
        returns a new SortedStack with the same elements of s, but in reverse order.
        At the end of the call s will be empty.

        Example:

            s       result

            2         5
            3         3
            5         2
    """
    raise Exception("TODO IMPLEMENT ME !!")

Testing

Once done, running this will run only the tests in TransferTest class and hopefully they will pass.

**Notice that exercise1 is followed by a dot and test class name .TransferTest : **

python -m unittest sorted_stack_test.TransferTest

2.2 merge

Implement following merge function. NOTE: function is external to class SortedStack.

def merge(s1,s2):
    """ Takes as input two SortedStacks having both ascending order,
       and returns a new SortedStack sorted in descending order, which will be the sorted merge
       of the two input stacks. MUST run in O(n1 + n2) time, where n1 and n2 are s1 and s2 sizes.

       If input stacks are not both ascending, raises ValueError.
       At the end of the call the input stacks will be empty.


       Example:

       s1 (asc)   s2 (asc)      result (desc)

          5          7             2
          4          3             3
          2                        4
                                   5
                                   7

    """

    raise Exception("TODO IMPLEMENT ME !")

Testing: python -m unittest sorted_stack_test.MergeTest

3. WStack

Using a text editor, open file wstack.py. You will find a WStack class skeleton which represents a simple stack that can only contain integers.

3.1 implement class WStack

Fill in missing methods in class WStack in the order they are presented so to have a .weight() method that returns the total sum of integers in the stack in O(1) time.

Example:

from wstack_sol import *

s = WStack()

print(s)

WStack: weight=0 elements=[]

s.push(7)

print(s)

WStack: weight=7 elements=[7]

s.push(4)

print(s)

WStack: weight=11 elements=[7, 4]

s.push(2)

s.pop()

2

print(s)

WStack: weight=11 elements=[7, 4]

3.2 accumulate

Implement function accumulate:

def accumulate(stack1, stack2, min_amount):
    """ Pushes on stack2 elements taken from stack1 until the weight of
        stack2 is equal or exceeds the given min_amount

        - if the given min_amount cannot possibly be reached because
          stack1 has not enough weight, raises early ValueError without
          changing stack1.
        - DO NOT access internal fields of stacks, only use class methods.
        - MUST perform in O(n) where n is the size of stack1
        - NOTE: this function is defined *outside* the class !
    """

Testing: python -m unittest wstack_test.AccumulateTest

Example:

s1 = WStack()


print(s1)

WStack: weight=0 elements=[]

s1.push(2)
s1.push(9)
s1.push(5)
s1.push(3)

print(s1)

WStack: weight=19 elements=[2, 9, 5, 3]

s2 = WStack()
print(s2)

WStack: weight=0 elements=[]

s2.push(1)
s2.push(7)
s2.push(4)

print(s2)

WStack: weight=12 elements=[1, 7, 4]

# attempts to reach in s2 a weight of at least 17

accumulate(s1,s2,17)

print(s1)

WStack: weight=11 elements=[2, 9]

Two top elements were taken from s1 and now s2 has a weight of 20, which is >= 17

4. Backpack

Open a text editor and edit file backpack_sol.py

We can model a backpack as stack of elements, each being a tuple with a name and a weight.

A sensible strategy to fill a backpack is to place heaviest elements to the bottom, so our backback will allow pushing an element only if that element weight is equal or lesser than current topmost element weight.

The backpack has also a maximum weight: you can put any number of items you want, as long as its maximum weight is not exceeded.

Example

from backpack_sol import *

bp = Backpack(30)  # max_weight = 30

bp.push('a',10)   # item 'a' with weight 10

DEBUG:  Pushing (a,10)

print(bp)

Backpack: weight=10 max_weight=30
          elements=[('a', 10)]

bp.push('b',8)

DEBUG:  Pushing (b,8)

print(bp)

Backpack: weight=18 max_weight=30
          elements=[('a', 10), ('b', 8)]

>>> bp.push('c', 11)

DEBUG:  Pushing (c,11)

ValueError: ('Pushing weight greater than top element weight! %s > %s', (11, 8))

bp.push('c', 7)

DEBUG:  Pushing (c,7)

print(bp)

Backpack: weight=25 max_weight=30
          elements=[('a', 10), ('b', 8), ('c', 7)]

>>> bp.push('d', 6)

DEBUG:  Pushing (d,6)

ValueError: Can't exceed max_weight ! (31 > 30)

4.1 class

✪✪ Implement methods in the class Backpack, in the order they are shown. If you want, you can add debug prints by calling the debug function

IMPORTANT: the data structure should provide the total current weight in O(1), so make sure to add and update an appropriate field to meet this constraint.

Testing: python3 -m unittest backpack_test.BackpackTest

4.2 remove

✪✪ Implement function remove:

# NOTE: this function is implemented *outside* the class !

def remove(backpack, el):
    """
        Remove topmost occurrence of el found in the backpack,
        and RETURN it (as a tuple name, weight)

        - if el is not found, raises ValueError

        - DO *NOT* ACCESS DIRECTLY FIELDS OF BACKPACK !!!
          Instead, just call methods of the class!

        - MUST perform in O(n), where n is the backpack size

        - HINT: To remove el, you need to call Backpack.pop() until
                the top element is what you are looking for. You need
                to save somewhere the popped items except the one to
                remove, and  then push them back again.

    """

Testing: python3 -m unittest backpack_test.RemoveTest

Example:

bp = Backpack(50)

bp.push('a',9)
bp.push('b',8)
bp.push('c',8)
bp.push('b',8)
bp.push('d',7)
bp.push('e',5)
bp.push('f',2)

DEBUG:  Pushing (a,9)
DEBUG:  Pushing (b,8)
DEBUG:  Pushing (c,8)
DEBUG:  Pushing (b,8)
DEBUG:  Pushing (d,7)
DEBUG:  Pushing (e,5)
DEBUG:  Pushing (f,2)

print(bp)

Backpack: weight=47 max_weight=50
          elements=[('a', 9), ('b', 8), ('c', 8), ('b', 8), ('d', 7), ('e', 5), ('f', 2)]

remove(bp, 'b')

DEBUG:  Popping ('f', 2)
DEBUG:  Popping ('e', 5)
DEBUG:  Popping ('d', 7)
DEBUG:  Popping ('b', 8)
DEBUG:  Pushing (d,7)
DEBUG:  Pushing (e,5)
DEBUG:  Pushing (f,2)

('b', 8)

print(bp)

Backpack: weight=39 max_weight=50
          elements=[('a', 9), ('b', 8), ('c', 8), ('d', 7), ('e', 5), ('f', 2)]

print(s2)

WStack: weight=20 elements=[1, 7, 4, 3, 5]

5. Tasks

Very often, you begin to do a task just to discover it requires doing 3 other tasks, so you start carrying them out one at a time and discover one of them actually requires to do yet another two other subtasks….

To represent the fact a task may have subtasks, we will use a dictionary mapping a task label to a list of subtasks, each represented as a label. For example:

subtasks = {
        'a':['b','g'],
        'b':['c','d','e'],
        'c':['f'],
        'd':['g'],
        'e':[],
        'f':[],
        'g':[]
    }

Task a requires subtasks b andg to be carried out (in this order), but task b requires subtasks c, d and e to be done. c requires f to be done, and d requires g.

You will have to implement a function called do and use a Stack data structure, which is already provided and you don’t need to implement. Let’s see an example of execution.

IMPORTANT: In the execution example, there are many prints just to help you understand what’s going on, but the only thing we actually care about is the final list returned by the function!

IMPORTANT: notice subtasks are scheduled in reversed order, so the item on top of the stack will be the first to get executed !

from tasks_sol import *

do('a', subtasks)

DEBUG:  Stack:   elements=['a']
DEBUG:  Doing task a, scheduling subtasks ['b', 'g']
DEBUG:           Stack:   elements=['g', 'b']
DEBUG:  Doing task b, scheduling subtasks ['c', 'd', 'e']
DEBUG:           Stack:   elements=['g', 'e', 'd', 'c']
DEBUG:  Doing task c, scheduling subtasks ['f']
DEBUG:           Stack:   elements=['g', 'e', 'd', 'f']
DEBUG:  Doing task f, scheduling subtasks []
DEBUG:           Nothing else to do!
DEBUG:           Stack:   elements=['g', 'e', 'd']
DEBUG:  Doing task d, scheduling subtasks ['g']
DEBUG:           Stack:   elements=['g', 'e', 'g']
DEBUG:  Doing task g, scheduling subtasks []
DEBUG:           Nothing else to do!
DEBUG:           Stack:   elements=['g', 'e']
DEBUG:  Doing task e, scheduling subtasks []
DEBUG:           Nothing else to do!
DEBUG:           Stack:   elements=['g']
DEBUG:  Doing task g, scheduling subtasks []
DEBUG:           Nothing else to do!
DEBUG:           Stack:   elements=[]

['a', 'b', 'c', 'f', 'd', 'g', 'e', 'g']

The Stack you must use is simple and supports push, pop, and is_empty operations:

s = Stack()

print(s)

Stack:   elements=[]

s.is_empty()

True

s.push('a')

print(s)

Stack:   elements=['a']

s.push('b')

print(s)

Stack:   elements=['a', 'b']

s.pop()

'b'

print(s)

Stack:   elements=['a']

5.1 do

Now open tasks.py and implement function do:

def do(task, subtasks):
    """ Takes a task to perform and a dictionary of subtasks,
        and RETURN a list of performed tasks

        - To implement it, inside create a Stack instance and a while cycle.
        - DO *NOT* use a recursive function
        - Inside the function, you can use a print like "I'm doing task a',
          but that is only to help yourself in debugging, only the
          list returned by the function will be considered in the evaluation!
    """

Testing: python3 -m unittest tasks_test.DoTest

5.2 do_level

In this exercise, you are asked to implement a slightly more complex version of the previous function where on the Stack you push two-valued tuples, containing the task label and the associated level. The first task has level 0, the immediate subtask has level 1, the subtask of the subtask has level 2 and so on and so forth. In the list returned by the function, you will put such tuples.

One possibile use is to display the executed tasks as an indented tree, where the indentation is determined by the level. Here we see an example:

IMPORTANT: Again, the prints are only to let you understand what’s going on, and you are not required to code them. The only thing that really matters is the list the function must return !

subtasks = {
        'a':['b','g'],
        'b':['c','d','e'],
        'c':['f'],
        'd':['g'],
        'e':[],
        'f':[],
        'g':[]
    }

do_level('a', subtasks)

DEBUG:                                                  Stack:   elements=[('a', 0)]
DEBUG:  I'm doing   a               level=0 Stack:   elements=[('g', 1), ('b', 1)]
DEBUG:  I'm doing     b             level=1 Stack:   elements=[('g', 1), ('e', 2), ('d', 2), ('c', 2)]
DEBUG:  I'm doing       c           level=2 Stack:   elements=[('g', 1), ('e', 2), ('d', 2), ('f', 3)]
DEBUG:  I'm doing         f         level=3 Stack:   elements=[('g', 1), ('e', 2), ('d', 2)]
DEBUG:  I'm doing       d           level=2 Stack:   elements=[('g', 1), ('e', 2), ('g', 3)]
DEBUG:  I'm doing         g         level=3 Stack:   elements=[('g', 1), ('e', 2)]
DEBUG:  I'm doing       e           level=2 Stack:   elements=[('g', 1)]
DEBUG:  I'm doing     g             level=1 Stack:   elements=[]

[('a', 0),
 ('b', 1),
 ('c', 2),
 ('f', 3),
 ('d', 2),
 ('g', 3),
 ('e', 2),
 ('g', 1)]

Now implement the function:

def do_level(task, subtasks):
    """ Takes a task to perform and a dictionary of subtasks,
        and RETURN a list of performed tasks, as tuples (task label, level)

        - To implement it, use a Stack and a while cycle
        - DO *NOT* use a recursive function
        - Inside the function, you can use a print like "I'm doing task a',
          but that is only to help yourself in debugging, only the
          list returned by the function will be considered in the evaluation
    """

Testing: python3 -m unittest tasks_test.DoLevelTest

6. Stacktris

Open a text editor and edit file stacktris.py

A Stacktris is a data structure that operates like the famous game Tetris, with some restrictions:

• Falling pieces can be either of length 1 or 2. We call them 1-block and 2-block respectively

• The pit has a fixed width of 3 columns

• 2-blocks can only be in horizontal

We print a Stacktris like this:

\ j 012
i
4  | 11|    # two 1-block
3  | 22|    # one 2-block
2  | 1 |    # one 1-block
1  |22 |    # one 2-block
0  |1 1|    # on the ground there are two 1-block

In Python, we model the Stacktris as a class holding in the variable _stack a list of lists of integers, which models the pit:

class Stacktris:

    def __init__(self):
        """ Creates a Stacktris
        """
        self._stack = []

So in the situation above the _stack variable would look like this (notice row order is inverted with respect to the print)

[
    [1,0,1],
    [2,2,0],
    [0,1,0],
    [0,2,2],
    [0,1,1],
]

The class has three methods of interest which you will implement, drop1(j) , drop2h(j) and _shorten

Example

Let’s see an example:

from stacktris_sol import *

st = Stacktris()

At the beginning the pit is empty:

st

Stacktris:
EMPTY

We can start by dropping from the ceiling a block of dimension 1 into the last column at index j=2. By doing so, a new row will be created, and will be a list containing the numbers [0,0,1]

IMPORTANT: zeroes are not displayed

st.drop1(2)

DEBUG:  Stacktris:
        |  1|

[]

Now we drop an horizontal block of dimension 2 (a 2-block) having the leftmost block at column j=1. Since below in the pit there is already the 1 block we previosly put, the new block will fall and stay upon it. Internally, we will add a new row as a python list containing the numbers [0,2,2]

st.drop2h(1)

DEBUG:  Stacktris:
        | 22|
        |  1|

[]

We see the zeroth column is empty, so if we drop there a 1-block it will fall to the ground. Internally, the zeroth list will become [1,0,1]:

st.drop1(0)

DEBUG:  Stacktris:
        | 22|
        |1 1|

[]

Now we drop again a 2-block at column j=2, on top of the previously laid one. This will add a new row as list [0,2,2].

st.drop2h(1)

DEBUG:  Stacktris:
        | 22|
        | 22|
        |1 1|

[]

In the game Tetris, when a row becomes completely filled it disappears. So if we drop a 1-block to the leftmost column, the mid line should be removed.

NOTE: The messages on the console are just debug print, the function drop1 only returns the extracted line [1,2,2]:

st.drop1(0)

DEBUG:  Stacktris:
        | 22|
        |122|
        |1 1|

DEBUG:  POPPING [1, 2, 2]
DEBUG:  Stacktris:
        | 22|
        |1 1|

[1, 2, 2]

Now we insert another 2-block starting at j=0. It will fall upon the previously laid one:

st.drop2h(0)

DEBUG:  Stacktris:
        |22 |
        | 22|
        |1 1|

[]

We can complete teh topmost row by dropping a 1-block to the rightmost column. As a result, the row will be removed from the stack and the row will be returned by the call to drop1:

st.drop1(2)

DEBUG:  Stacktris:
        |221|
        | 22|
        |1 1|

DEBUG:  POPPING [2, 2, 1]
DEBUG:  Stacktris:
        | 22|
        |1 1|

[2, 2, 1]

Another line completion with a drop1 at column j=0:

st.drop1(0)

DEBUG:  Stacktris:
        |122|
        |1 1|

DEBUG:  POPPING [1, 2, 2]
DEBUG:  Stacktris:
        |1 1|

[1, 2, 2]

We can finally empty the Stacktris by dropping a 1-block in the mod column:

st.drop1(1)

DEBUG:  Stacktris:
        |111|

DEBUG:  POPPING [1, 1, 1]
DEBUG:  Stacktris:
        EMPTY

[1, 1, 1]

6.1 _shorten

Start by implementing this private method:

def _shorten(self):
    """ Scans the Stacktris from top to bottom searching for a completely filled line:
        - if found, remove it from the Stacktris and return it as a list.
        - if not found, return an empty list.
    """

If you wish, you can add debug prints but they are not mandatory

Testing: python3 -m unittest stacktris_test.ShortenTest

6.2 drop1

Once you are done with the previous function, implement drop1 method:

NOTE: In the implementation, feel free to call the previously implemented _shorten method.

def drop1(self, j):
    """ Drops a 1-block on column j.

         - If another block is found,  place the 1-block on top of that block,
           otherwise place it on the ground.

        - If, after the 1-block is placed, a row results completely filled, removes
          the row and RETURN it. Otherwise, RETURN an empty list.

        - if index `j` is outside bounds, raises ValueError
    """

Testing: python3 -m unittest stacktris_test.Drop1Test

6.3 drop2h

Once you are done with the previous function, implement drop2 method:

def drop2h(self, j):
    """ Drops a 2-block horizontally with left block on column j,

         - If another block is found,  place the 2-block on top of that block,
           otherwise place it on the ground.

        - If, after the 2-block is placed, a row results completely filled,
          removes the row and RETURN it. Otherwise, RETURN an empty list.

        - if index `j` is outside bounds, raises ValueError
    """

Testing: python3 -m unittest stacktris_test.Drop2hTest