OOP Matrix Challenge

Download exercises zip

Browse files online

We want to model operations on IMMUTABLE matrices, the object oriented way.

You have a generic interface called Matrix in file matrix.py, and you have to implement two descendants of the interface, DenseMatrix and SparseMatrix.

IMPORTANT: work in group and share tests!

You will make a lot of mistakes, some hard to debug: help yourself by writing test cases, we also invite you to share the tests (not the solutions!) with your fellow students.

Please note there are many cornercases, even if stuff seems to work there will probably occasions where it fails - you won’t probably be able to find them all on your own.

What to do

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

oop
   matrix.py
   oop-matrix-chal.ipynb
   .
   .

You can ignore the notebook, and edit .py files in Visual Studio Code.

DenseMatrix

Let’s begin with the simpler implementation, which is DenseMatrix: you will code it by storing data inside lists of lists.

Create a new file dense_matrix.py and declare a class DenseMatrix which inherits from Matrix. Copy inside all the methods definitions from Matrix.

from matrix import Matrix

class DenseMatrix(Matrix):
    """ A Matrix represented internally as a list of lists

        When creating it from list of lists, perform a DEEP COPY of the input
        and store it inside a private field you will call  _cells (use ONE underscore)
    """

Constructors and printing

Generally first methods we implement are the constructor and methods to show the class content such as __str__ and __repr__. All methods are documented in the matrix.py interface, let’s see now the constructor. Copy paste the following inside your DenseMatrix class.

def __init__(self, *args):
        """Initializes the Matrix with either:

            One argument: a list of lists
            Three arguments: number of rows
                             number of columns
                             a list of cell triplets (row_index,col_index,value)
                            - if number of rows or columns is less than indeces found
                              in triplets, raise Value Error

            In both cases, provided data must allow the creation of a matrix with
            at least one row and a column, otherwise raise ValueError
        """
        raise Exception("Should be implemented in a descendant of Matrix!")

Constructor as list of lists

We see the the constructor takes the special *args argument, which means it can accept a variable number of arguments. To check for the two cases, you might write something like this:

class DenseMatrix(Matrix):
    def __init__(self, *args):

        if len(args) == 1:   # list of lists
            rows = args[0]
            # do something ...
        elif len(args) == 3:
            n,m,triplets = args
            # do something
        else:
            raise ValueError('Expected one or three args!')

You can start by handling only the one argument case, which we will interpret as a list of lists. You can store a deep copy of the list of lists in a private field you can call _cells. Why should we store a deep copy? It’s a form a so-called defensive-programming: if we store a copy, it’s less likely that a user of our class will later mess with the instance internal data. If we store the data in a field beginning with one underscore _, we will signal external users we do not want them to directly access it (notice if they really want they will still be able to do it)

from dense_matrix_chal_sol import *
from sparse_matrix_chal_sol import *

dma = DenseMatrix([ [0,6,8,0],
                    [0,0,0,5],
                    [9,0,7,0] ])

dma

DenseMatrix([[0, 6, 8, 0], [0, 0, 0, 5], [9, 0, 7, 0]])

type(DenseMatrix)

type

str and repr

Implement __str__ and __repr__

def __str__(self):
    """ RETURN a nice human-readable formatted string, possibly like this:

          Matrix  [ [5,2,6,3],
                    [8,4,7,4],
                    [2,1,9,8] ]

          - substitute Matrix with the descendant class name
          - NOTE: sometimes this representation is impractical (i.e. sparse matrices
                  with large n/m), in that case use another format of your choice
    """
    raise Exception("Should be implemented in a descendant of Matrix!")

def __repr__(self):
    """ RETURN one-line string representing a Python expression which would recreate the atrix
    """
    raise Exception("Should be implemented in a descendant of Matrix!")

str(dma)

'DenseMatrix [ [0, 6, 8, 0]\n              [0, 0, 0, 5]\n              [9, 0, 7, 0] ]'

print(dma)

DenseMatrix [ [0, 6, 8, 0]
              [0, 0, 0, 5]
              [9, 0, 7, 0] ]

repr(dma)

'DenseMatrix([[0, 6, 8, 0], [0, 0, 0, 5], [9, 0, 7, 0]])'

dma

DenseMatrix([[0, 6, 8, 0], [0, 0, 0, 5], [9, 0, 7, 0]])

constructor as list of triplets

Now extend the constructor to handle also the list of triplets case:

dmb = DenseMatrix(3,4, [(0,1,6),(0,2,8),(1,3,5),(2,0,9),(2,2,7)])

dmb

DenseMatrix([[0, 6, 8, 0], [0, 0, 0, 5], [9, 0, 7, 0]])

print(dmb)

DenseMatrix [ [0, 6, 8, 0]
              [0, 0, 0, 5]
              [9, 0, 7, 0] ]

shape

Implement shape method:

def shape(self):
    """RETURN the number of rows and columns as a tuple
    """

dma.shape()  # NOTE the ()

(3, 4)

Brackets operator

Override the square bracket operator by reimplementing the method __getitem__

IMPORTANT: Read carefully Python documentation!!

def __getitem__(self, key):
    """Overrides default bracket access behaviour.
       key is whatever the user passes within the brackets, in our case
       we want user to be able to write

       my_mat[2,5]  to access element at row 2 and column 5

       NOTE 1: if the user types 2,5 inside the brackets, Python will actually
             generate a TUPLE (2,5)  so that is the key type you should
             accept (a tuple of *exactly two* integers)
       NOTE 2: Since this method signature is defined by Python documention:

          https://docs.python.org/3/reference/datamodel.html#object.__getitem__

        you MUST write it respecting ALL the indications of the docs, in particular
        think also about  what should happen in undesired scenarios when
        the user enters a key of wrong type, wrong value, etc as described
        in the documentation
    """

print(dma)

DenseMatrix [ [0, 6, 8, 0]
              [0, 0, 0, 5]
              [9, 0, 7, 0] ]

dma[0,1]

6

dma[0,2]

8

Negative indeces should also be supported:

dma[0,-3]

6

nonzero

def nonzero(self):
        """Return a list of triplets (row index, column index, value) of non-zero cells,
           in no particular order.
        """

Since we stored the rows in a private field _cells, we have to offer users other ways to access data. For example, by calling nonzero() method users should be able to obtain non-zero values, as a list of triplets with row index, column index and value of cells. You might wonder what the utility is, after we already implemented the brackets operator: the reason will become clearer when you start implementing methods that need to visit a generic Matrix, like the following ones.

print(dma)

DenseMatrix [ [0, 6, 8, 0]
              [0, 0, 0, 5]
              [9, 0, 7, 0] ]

dma.nonzero()

[(0, 1, 6), (0, 2, 8), (1, 3, 5), (2, 0, 9), (2, 2, 7)]

isclose

Implement this method:

DO NOT MAKE ASSUMPTIONS ABOUT other CLASS!

In the implementation, use other like if it were a generic Matrix, it might not always be a DenseMatrix. So the only way to access elements will be either by using the brackets operator or by calling nonzero()

def isclose(self, other, delta):
        """ RETURN True if each cell in this matrix is within a delta distance
            from other Matrix. RETURN False if any cell couple differs more than delta.

            - if matrices have different dimensions, raise ValueError
        """

print(dma)

DenseMatrix [ [0, 6, 8, 0]
              [0, 0, 0, 5]
              [9, 0, 7, 0] ]

dmd = DenseMatrix([ [0,     5.9,   8,   0],
                    [0,       0, 0.1,   5],
                    [9.15, -0.1,   7, 0.1] ])

dma.isclose(dmd, 0.2)

True

dma.isclose(dmd, 0.05)

False

Equality

Override == operator:

dma = DenseMatrix([ [0,6,8,0],
                    [0,0,0,5],
                    [9,0,7,0] ])

dmb = DenseMatrix(3,4, [(0,1,6),(0,2,8),(1,3,5),(2,0,9),(2,2,7)])

dma == dmb

True

Notice in this case, since we want in general to check equality to the last bit, we will want to check that other is actually a DenseMatrix, otherwise we will return False

dma == 'ciao'

False

Equality with a different shape should just return False, without raising exceptions:

dma == DenseMatrix([[2,4],
                    [9,3]])

False

Equality with different numbers:

dmc = DenseMatrix([ [1,2,3,4],
                    [6,7,8,9],
                    [10,11,12,13] ])
dma == dmc

False

Sum

Override + operator so can sum other Matrix instances:

DO NOT MAKE ASSUMPTIONS ABOUT other CLASS!

In the implementation, use other like if it were a generic Matrix, it might not always be a DenseMatrix. So the only way to access elements will be either by using the brackets operator or by calling nonzero()

dma = DenseMatrix([ [0,6,8,0],
                    [0,0,0,5],
                    [9,0,7,0] ])

dmc = DenseMatrix([ [1,2,3,4],
                    [6,7,8,9],
                    [10,11,12,13] ])

print(dma + dmc)

DenseMatrix [ [1, 8, 11, 4]
              [6, 7, 8, 14]
              [19, 11, 19, 13] ]

Note dma and dmc where not modified:

print(dma)

DenseMatrix [ [0, 6, 8, 0]
              [0, 0, 0, 5]
              [9, 0, 7, 0] ]

print(dmc)

DenseMatrix [ [1, 2, 3, 4]
              [6, 7, 8, 9]
              [10, 11, 12, 13] ]

Multiplication

Override * operator so we can multiply by a scalar:

print(dma * 2)

DenseMatrix [ [0, 12, 16, 0]
              [0, 0, 0, 10]
              [18, 0, 14, 0] ]

DO NOT MAKE ASSUMPTIONS ABOUT other CLASS!

In the implementation, use other like if it were a generic Matrix, it might not always be a DenseMatrix. So the only way to access elements will be either by using the brackets operator or by calling nonzero()

Again multiplication by a scalar does not modify the original:

print(dma)

DenseMatrix [ [0, 6, 8, 0]
              [0, 0, 0, 5]
              [9, 0, 7, 0] ]

Multiplying a scalar by a matrix should also work:

print(2 * dma)

DenseMatrix [ [0, 12, 16, 0]
              [0, 0, 0, 10]
              [18, 0, 14, 0] ]

Again original dma was not changed:

print(dma)

DenseMatrix [ [0, 6, 8, 0]
              [0, 0, 0, 5]
              [9, 0, 7, 0] ]

Matrix vector multiplication

Next implement support for multiplication of a matrix by a properly dimensioned vector on the right, which must have the same number of rows as the matrix number of columns:

     matrix   vector      result

\j    012
i  0  aaa        v0       a00*v0 + a01*v1 + a02*v2
   1  aaa        v1       a10*v0 + a11*v1 + a12*v2
   2  aaa        v2       a20*v0 + a21*v1 + a22*v2
   3  aaa                 a30*v0 + a31*v1 + a32*v2

The result will have the same number of rows as the matrix.

DO NOT MAKE ASSUMPTIONS ABOUT other CLASS!

In the implementation, use other like if it were a generic Matrix, it might not always be a DenseMatrix. So the only way to access elements will be either by using the brackets operator or by calling nonzero()

dmveca = DenseMatrix([[1],[2],[3],[4]])

print(dmveca)

DenseMatrix [ [1]
              [2]
              [3]
              [4] ]

print(dma)

DenseMatrix [ [0, 6, 8, 0]
              [0, 0, 0, 5]
              [9, 0, 7, 0] ]

print(dma * dmveca)

DenseMatrix [ [36]
              [20]
              [30] ]

Multiplication by a vector does not modify the originals:

print(dmveca)

DenseMatrix [ [1]
              [2]
              [3]
              [4] ]

Notice dimensions must be compatible, this should not work:

>>> print(dma*DenseMatrix([[1],[2]]))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-33-bc850efec5f1> in <module>()
----> 1 print(dma*DenseMatrix([[1],[2]]))

TypeError: unsupported operand type(s) for *: 'DenseMatrix' and 'DenseMatrix'

Vector matrix multiplication

Next implement support for multiplication of a matrix by a properly dimensioned horizontal vector on the left, which must have the same number of columns as the matrix number of rows:

  ector matrix result

\j  012   0123 0123
i   vvv 0 aaaa rrrr
        1 aaaa
        2 aaaa


res = a00*v0+a10*v1+a20*v2, a01*v0+a11*v1+a21*v2, a02*v0+a12*v1+a22*v2, a03*v0+a13*v1+a23*v2

The result will have the same number of columns as the matrix.

DO NOT MAKE ASSUMPTIONS ABOUT other CLASS!

In the implementation, use other like if it were a generic Matrix, it might not always be a DenseMatrix. So the only way to access elements will be either by using the brackets operator or by calling nonzero()

print(dma)

DenseMatrix [ [0, 6, 8, 0]
              [0, 0, 0, 5]
              [9, 0, 7, 0] ]

dmvecb = DenseMatrix([[1,2,3]])

print(dmvecb * dma)

DenseMatrix [ [27, 6, 29, 10] ]

Matrix matrix multiplication

This would be the general problem but for the purposes of this challenge, it is not mandatory to support multiplication by a matrix, even if they have compatible dimensions:

>>> print(dma*DenseMatrix([[3,2],
                           [3,7],
                           [2,8],
                           [9,3],]))

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-34-ed1ad440c418> in <module>()
      2                        [3,7],
      3                        [2,8],
----> 4                        [9,3],]))

TypeError: unsupported operand type(s) for *: 'DenseMatrix' and 'DenseMatrix'

SparseMatrix

If you’ve arrived so far, congratulations, that was quite a journey. But only half of it! We’ve seen matrices as lists of lists for a long time, let’s now see if we can save some space. Many real-world matrices have often most cells set to zero, so it would be convenient to avoid storing in memory those cells, and reserve space only for non-zero valued cells. There are many ways to do it (see Wikipedia), in this challenge we will adopt the simplest which is the so-called Dictionary of Keys (DOK in short). DOK consists of a dictionary that maps (row, column)-pairs to the value of the elements. Elements that are missing from the dictionary are assumed to be zero.

Now we can see the real reason why we supported also a constructor with triplets: if the goal of using a SparseMatrix is to avoid creating huge tables in memory, initializing it with a list of lists would defeat the purpose! In what follows, sometimes we may still use the list of lists initialization, but that would only be for clarity purposes.

Sparse constructors and printing

Create a new file sparse_matrix.py and copy inside this with the method definitions you find in matrix.py as done before.

from matrix import Matrix

class SparseMatrix(Matrix):
    """ A SparseMatrix is a matrix which contains very few non-zero elements.

        In this implementation, storage is modelled as a dictionary of keys (DOK in short),
        where each key is a tuple of cell coordinates which maps to a non-zero cell value.

        NOTE: *NEVER* store zero-valued cells.
    """

Ffollow the same implementation order as before, so start with the constructor __init__, __str__ and __repr__ overrides. Note this time our class implementation will have a dictionary as private _cells field.

With sparse matrices we can have a big 30x20 matrix and occupy very little memory:

sma = SparseMatrix(30,20, [(26,17,3),(24,11,5)])

You can save the shape inside a private _shape field.

Since shape can be much bigger than atcual data, with __str__ you must show the internal dictionary and the shape:

print(sma)

SparseMatrix {
    (24, 11): 5,
    (26, 17): 3
}
shape: (30, 20)

__repr__ will show the triplets constructor:

repr(sma)

'SparseMatrix(30,20, [(24, 11, 5), (26, 17, 3)])'

sma

SparseMatrix(30,20, [(24, 11, 5), (26, 17, 3)])

Sparse shape

Implement shape():

sma.shape()   # note the round brackets

(30, 20)

Sparse Brackets operator

Override the square bracket operator by reimplementing the method __getitem__

CAREFUL!

Even more than before, you have to super-carefully read Python documentation!!

To respect Python documentation, this time you can’t rely on built-in errors and features of lists as you probably did in the DenseMatrix case, so you will have to write a lot of if that check for various possible errors (bad types, values, etc) and raise the appropriate errors (IndexError, TypeError, KeyError, etc)

Implement brackets operator:

sma[24,11]

5

sma[26,17]

3

sma[29,3]   # shouldn't explode

0.0

Support negative numbers:

sma[-6,11]

5

sma[29,-2]

0.0

Sparse nonzero

This is very important, as it allows iterating the data structure in an efficient way - depending on the shape, trying all the couples i, j with the square brackets might be prohibitively costly.

sma.nonzero()

[(24, 11, 5), (26, 17, 3)]

Sparse isclose

Be careful to write generic code, and avoid iterating all possible i,j couples - you should only look into nonzero ones.

print(sma)

SparseMatrix {
    (24, 11): 5,
    (26, 17): 3
}
shape: (30, 20)

sma.isclose(SparseMatrix(30,20, [(24, 11, 4.9), (26, 17, 3.1)]), 0.2)

True

sma.isclose(SparseMatrix(30,20, [(24, 11, 4.9), (26, 17, 3.1)]), 0.05)

False

sma.isclose(SparseMatrix(30,20, [(24, 11, 4.9), (26, 17, 3.1), (13,18,0.5)]), 0.2)

False

sma.isclose(SparseMatrix(30,20, [(24, 11, 4.9), (26, 17, 3.1), (13,18,0.1)]), 0.2)

True

sma.isclose(SparseMatrix(30,20, [(24, 11, 4.9), (26, 17, 3.1), (13,18,-0.1)]), 0.2)

True

The interesting part comes when we try isclose with another class, like DenseMatrix. If you wrote general enough code, only assuming other is a generic Matrix the following should work without particular effort:

smp = SparseMatrix([[1,    0,   3],
                    [4,    5,   0]])
dmp = DenseMatrix( [[1.1,  0.1, 2.9],
                    [4.05, 4.9, -0.05]])

smp.isclose(dmp, 0.2)

True

smp.isclose(dmp, 0.05)

False

dmp.isclose(smp, 0.2)

True

dmp.isclose(smp, 0.05)

False

Sparse equality

Be careful to write generic code, and avoid iterating all possible i,j couples - you should only look into nonzero ones.

sma

SparseMatrix(30,20, [(24, 11, 5), (26, 17, 3)])

smb = SparseMatrix(30,20, [(24, 11, 5), (26, 17, 3)])

sma == sma

True

sma == smb

True

sma == SparseMatrix(30,20, [(24, 11, 5), (26, 17, 123)])

False

sma == SparseMatrix(30,20, [(24, 11, 5), (26, 17, 3), (5,10,6)])

False

Equality among different types should always be False, even if they descend from the same ancestor:

SparseMatrix([[1,2],[3,4]]) == DenseMatrix([[1,2],[3,4]])

False

DenseMatrix([[1,2],[3,4]]) == SparseMatrix([[1,2],[3,4]])

False

Sparse sum

Be careful to write generic code, and avoid iterating all possible i,j couples - you should only look into nonzero ones.

smq = SparseMatrix([[1,2,0],
                    [4,0,6]])
dmq = DenseMatrix([[0,8,0],
                   [0,7,3]])

print(smq + smq)

SparseMatrix {
    (0, 1): 4,
    (1, 2): 12,
    (1, 0): 8,
    (0, 0): 2
}
shape: (2, 3)

Again the interesting bit is when you try summing among different classes:

print(smq + dmq)

SparseMatrix {
    (0, 1): 10,
    (1, 2): 9,
    (1, 0): 4,
    (0, 0): 1,
    (1, 1): 7
}
shape: (2, 3)

print(dmq + smq)

DenseMatrix [ [1, 10, 0.0]
              [4, 7.0, 9] ]

Sparse multiplication

As always, be careful writing general code, and avoid iterating all possible i,j couples - you should only look into nonzero ones.

Sparse matrix vector multiplication

smq = SparseMatrix([[1,0,3],
                    [4,5,0]])

smvecq = SparseMatrix([[1],
                       [0],
                       [3]])
print(smq * smvecq)

SparseMatrix {
    (1, 0): 4.0,
    (0, 0): 10
}
shape: (2, 1)

Let’s try mixing types:

dmq = DenseMatrix([[1,0,3],
                   [4,5,0]])

dmvecq = DenseMatrix([[1],
                      [0],
                      [3]])
print(smq * dmvecq)

SparseMatrix {
    (1, 0): 4,
    (0, 0): 10
}
shape: (2, 1)

print(dmq * smvecq)

DenseMatrix [ [10.0]
              [4.0] ]

Sparse vector matrix multiplication

smvecr = SparseMatrix([[1,2,0]])

smr = SparseMatrix([ [0, 6, 8, 0],
                     [0, 0, 0, 5],
                     [9, 0, 7, 0] ])

print(smvecr * smr)

SparseMatrix {
    (0, 1): 6,
    (0, 3): 10,
    (0, 2): 8.0
}
shape: (1, 4)

Let’s mix types:

dmvecr = DenseMatrix([[1,2,0]])

dmr = DenseMatrix([ [0, 6, 8, 0],
                    [0, 0, 0, 5],
                    [9, 0, 7, 0] ])

print(smvecr * dmr)

SparseMatrix {
    (0, 1): 6,
    (0, 3): 10,
    (0, 2): 8.0
}
shape: (1, 4)

print(dmvecr * smr)

DenseMatrix [ [0, 6, 8, 10] ]