Matrices lists 3 - Challenges

Download exercises zip

Browse online files

We now propose some exercises without solution, do you accept the challenge?

Challenge - Tiles

✪✪ You are working in a construction site, and they tell you to fill the floor with tiles. You have a stack of tiles to place. On each, there is written at which coordinates it should be placed, and also the decoration it should show. The architect did not tell you exactly the dimensions the tiled floor should have, so you will have to deduce them by looking at the tiles coordinates.

Each time you take one tile from the stack, you place it in the appropriate cell on the floor.

Write some code which creates a NEW matrix of lists of lists called mat: before placing the tiles you will have to prepare a matrix with the appropriate number of cells to cover (retrieve dimensions by scanning the stack)

  • tiles which remain empty will be marked with '*' symbol

  • MODIFY the given stack, by reducing it one item at a time (suppose the top of the stack is the end of list): at the end of your program it must be empty

  • DO NOT create a new stack (so no lines beginning with stack =)

  • DO NOT use .remove nor .index methods

Example - given:

stack = [(1,1,'U'),(1,3,'U'),(2,2,'H'),(3,0,'A'),(3,1,'A'),
         (2,1,'|'),(3,3,'A'),(2,3,'|'),(3,4,'A')]

Your code should produce:

>>> pprint(mat)
[['*', '*', '*', '*', '*'],
 ['*', 'U', '*', 'U', '*'],
 ['*', '|', 'H', '|', '*'],
 ['A', 'A', '*', 'A', 'A']]
[1]:
from pprint import pprint




stack = [(1,1,'U'),(1,3,'U'),(2,2,'H'),(3,0,'A'),(3,1,'A'),
         (2,1,'|'),(3,3,'A'),(2,3,'|'),(3,4,'A')]

# write some code here


pprint(mat)

assert stack == []
assert mat == [ ['*', '*', '*', '*', '*'],
                ['*', 'U', '*', 'U', '*'],
                ['*', '|', 'H', '|', '*'],
                ['A', 'A', '*', 'A', 'A'] ]

Challenge - The Ark

It’s year 2050, humans went far too often shopping with their SUVs, and now Earth is without natural resources with sun rays scorching what remains of the atmosphere.

Luckily, a planet which could host life called Aurora has been recently discovered. A billionaire enterprenur who foresaw the disaster decided to build in secret a spaceship to escape: it was named The Ark. The billionaire is now old and wouldn’t survive a long space travel, so he decides to send only animals to Aurora. Humans won’t be allowed, as they would probably mess up that planet as they did with Earth. Sophisticated roboservants will then take care of the animals.

Animals are herded in a hurry to a field nearby the secret launch station.

The Ark 1. Sort the herd

✪✪ The herd is a list of animals, in no particular order. The herd needs to stay in a farm while last checks are performed on the spaceship. Before entering the farm, animals are sorted by their weight, which are provided as a dictionary herd_weights.

Implement function sort_herd(animals, weights) which MODIFIES animals so that is sorted according to weight.

Example - given:

herd = ['elephant', 'owl','elephant','lion','owl','zebra','elephant','giraffe',
        'giraffe', 'fox', 'zebra','fox','fox','owl','zebra','owl',
        'lion','zebra','fox','lion','lion','owl','zebra', 'giraffe',
        'owl', 'owl', 'owl', 'owl','zebra','fox', 'owl',
        'fox','lion','fox','owl','owl','lion', 'fox','fox']

herd_weights = {'elephant': 4800,
                'fox'     : 4,
                'owl'    :  3,
                'giraffe' : 800,
                'lion'    : 175,
                'zebra'   : 384}

it should result (NOTE it’s one list of strings, here we display it on many lines just for convenience):

>>> sort_herd(herd, herd_weights)
>>> print(herd)
['owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl',
 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox',
 'lion', 'lion', 'lion', 'lion', 'lion', 'lion',
 'zebra', 'zebra', 'zebra', 'zebra', 'zebra', 'zebra',
 'giraffe', 'giraffe', 'giraffe',
 'elephant', 'elephant', 'elephant']
[2]:

herd = ['elephant', 'owl','elephant','lion','owl','zebra','elephant','giraffe',
        'giraffe', 'fox', 'zebra','fox','fox','owl','zebra','owl',
        'lion','zebra','fox','lion','lion','owl','zebra', 'giraffe',
        'owl', 'owl', 'owl', 'owl','zebra','fox', 'owl',
        'fox','lion','fox','owl','owl','lion', 'fox','fox']

herd_weights = {'elephant': 4800,
                'fox'     : 4,
                'owl'    :  3,
                'giraffe' : 800,
                'lion'    : 175,
                'zebra'   : 384}

# sort them according to the weight

def sort_herd(animals, weights):
    """ MODIFIES animals so that is sorted in-place according to weight
    """
    raise Exception('TODO IMPLEMENT ME !')


sort_herd(herd, herd_weights)

assert herd == ['owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl',
                'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox',
                'lion', 'lion', 'lion', 'lion', 'lion', 'lion',
                'zebra', 'zebra', 'zebra', 'zebra', 'zebra', 'zebra',
                'giraffe', 'giraffe', 'giraffe',
                'elephant', 'elephant', 'elephant']

assert sort_herd(herd, herd_weights) == None  # should return nothing!

The Ark 2. Enter the Farm

✪✪✪ After getting sorted, animals are ready to enter the farm. A farm is organized in a series of cattle pens: we can model them as a list of lists of different lengths, each holding a different kind of animals. Implement a function enter_farm(animals) which RETURN a NEW list of lists.

  • NOTE: lists may have different lengths, so we cannot call this a matrix !

Example - given:

sorted_herd = ['owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl',
               'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox',
               'lion', 'lion', 'lion', 'lion', 'lion', 'lion',
               'zebra', 'zebra', 'zebra', 'zebra', 'zebra', 'zebra',
               'giraffe', 'giraffe', 'giraffe',
               'elephant', 'elephant', 'elephant']

it should result:

>> from pprint import pprint
>> farm = enter_farm(sorted_herd)
>> pprint(farm, width=190)

[['owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl'],
 ['fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox'],
 ['lion', 'lion', 'lion', 'lion', 'lion', 'lion'],
 ['zebra', 'zebra', 'zebra', 'zebra', 'zebra', 'zebra'],
 ['giraffe', 'giraffe', 'giraffe'],
 ['elephant', 'elephant', 'elephant']]
[3]:

def enter_farm(animals):
    """ RETURN a NEW list of lists
    """
    raise Exception('TODO IMPLEMENT ME !')

sorted_herd = ['owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl', 'owl',
               'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox', 'fox',
               'lion', 'lion', 'lion', 'lion', 'lion', 'lion',
               'zebra', 'zebra', 'zebra', 'zebra', 'zebra', 'zebra',
               'giraffe', 'giraffe', 'giraffe',
               'elephant', 'elephant', 'elephant']

assert enter_farm(sorted_herd) == [
 ['owl','owl','owl','owl','owl','owl','owl','owl','owl','owl','owl','owl'],
 ['fox','fox','fox','fox','fox','fox','fox','fox','fox'],
 ['lion','lion','lion','lion','lion','lion'],
 ['zebra','zebra','zebra','zebra','zebra','zebra'],
 ['giraffe','giraffe','giraffe'],
 ['elephant','elephant','elephant']
]

assert enter_farm([]) == []
assert enter_farm(['beetle']) == [ ['beetle'] ]
assert enter_farm(['sheep', 'sheep']) == [ ['sheep', 'sheep'] ]
sorted_herd2 = ['sheep', 'dog']
assert enter_farm(sorted_herd2) == [ ['sheep'],
                                     ['dog'] ]
assert sorted_herd2 == ['sheep', 'dog']  # check it did not change the input

The Ark 3. Enter the Ark

✪✪ An Ark spaceship is a huge rocket divided vertically in stages, each divided in exactly three compartments. Laws of physics suggest it’s best to stack heavier elements at the bottom, so it is decided to populate the base of the rocket with big animals like elephants, while lighter ones like birds will go to the tip.

We can model The Ark as a list of lists matrix, where each row contains exactly three tuples of animals. Given as input a farm with animals already sorted, RETURN a NEW list of lists with the animals grouped in tuples.

  • ASSUME animals in rows are always exactly divisible by 3

  • WRITE something general, which handles also weird cases like a floor with mixed animal species

Example - given:

farm = [
 ['owl','owl','owl','owl','owl','owl','owl','owl','owl','owl','owl','owl'],
 ['fox','fox','fox','fox','fox','fox','fox','fox','fox'],
 ['lion','lion','lion','lion','lion','lion'],
 ['zebra','zebra','zebra','zebra','zebra','zebra'],
 ['giraffe','giraffe','giraffe'],
 ['elephant','elephant','elephant']
]

your code should produce (don’t care about formatting, here we manually displayed tuples in columns for clarity):

>>> enter_ark(farm)
[
 [('owl','owl','owl','owl'), ('owl', 'owl', 'owl', 'owl'), ('owl','owl','owl','owl')],
 [('fox', 'fox','fox'),      ('fox', 'fox','fox'),         ('fox', 'fox', 'fox')],
 [('lion', 'lion'),          ('lion', 'lion'),             ('lion', 'lion')],
 [('zebra', 'zebra'),        ('zebra', 'zebra'),           ('zebra', 'zebra')],
 [('giraffe',),              ('giraffe',),                 ('giraffe',)],
 [('elephant',),             ('elephant',),                ('elephant',)]
]
[4]:

def enter_ark(animals):
    """ RETURN a NEW list of lists
    """
    raise Exception('TODO IMPLEMENT ME !')

farm = [
    ['owl','owl','owl','owl','owl','owl','owl','owl','owl','owl','owl','owl'],
    ['fox','fox','fox','fox','fox','fox', 'fox','fox','fox'],
    ['lion','lion','lion','lion','lion','lion'],
    ['zebra','zebra','zebra','zebra','zebra','zebra'],
    ['giraffe','giraffe','giraffe'],
    ['elephant','elephant','elephant']
]

assert enter_ark(farm) == [
 [('owl','owl','owl','owl'), ('owl', 'owl', 'owl', 'owl'), ('owl','owl','owl','owl')],
 [('fox', 'fox','fox'),      ('fox', 'fox','fox'),         ('fox', 'fox','fox')],
 [('lion', 'lion'),          ('lion', 'lion'),             ('lion', 'lion')],
 [('zebra', 'zebra'),        ('zebra', 'zebra'),           ('zebra', 'zebra')],
 [('giraffe',),              ('giraffe',),                 ('giraffe',)],
 [('elephant',),             ('elephant',),                ('elephant',)]
]

assert enter_ark([]) == []
cat_farm = [ ['cat','cat','cat'] ]
assert enter_ark(cat_farm) == [ [('cat',),('cat',),('cat',)] ]
assert cat_farm == [['cat','cat','cat']]  #check function didn't change the input
assert enter_ark([ ['cat','dog','mouse'] ]) == [ [('cat',),('dog',),('mouse',)] ]  # general case

The Ark 4. Aurora

✪✪ Implement function land which takes a spaceship and PRINTS a message about its content.

Example:

ark = [
    [('owl', 'owl', 'owl', 'owl'), ('owl', 'owl', 'owl', 'owl'), ('owl', 'owl', 'owl', 'owl')],
    [('fox', 'fox', 'fox'), ('fox', 'fox', 'fox'), ('fox', 'fox', 'fox')],
    [('lion', 'lion'), ('lion', 'lion'), ('lion', 'lion')],
    [('zebra', 'zebra'), ('zebra', 'zebra'), ('zebra', 'zebra')],
    [('giraffe',), ('giraffe',), ('giraffe',)],
    [('elephant',), ('elephant',), ('elephant',)]
]

>>> land(ark)
The spaceship reached Aurora and has successfully landed:

   12 owls
   9 foxs
   6 lions
   6 zebras
   3 giraffes
   3 elephants

A new chapter begins...
[5]:

def land(spaceship):
    """ PRINTS a success message
    """
    raise Exception('TODO IMPLEMENT ME !')

ark1 = [
    [('owl', 'owl', 'owl', 'owl'), ('owl', 'owl', 'owl', 'owl'), ('owl', 'owl', 'owl', 'owl')],
    [('fox', 'fox', 'fox'), ('fox', 'fox', 'fox'), ('fox', 'fox', 'fox')],
    [('lion', 'lion'), ('lion', 'lion'), ('lion', 'lion')],
    [('zebra', 'zebra'), ('zebra', 'zebra'), ('zebra', 'zebra')],
    [('giraffe',), ('giraffe',), ('giraffe',)],
    [('elephant',), ('elephant',), ('elephant',)]
]

land(ark1)  # should only print stuff

assert land(ark1) == None  # should return nothing!

Challenge - Go camping

✪✪✪ Let’s go camping in the wild! But first, you need to check you have everything needed. In particular, you are worried about not having all the items you wrote down in a blocknote. You open the bag with all the camping stuff, and spread the content around on your bed.

Given a matrix bed as a list of lists of strings, and a tuple blocknote of elements to find, write a function go_camping which RETURN True if ALL the elements of blocknote are present in bed, otherwise RETURN False.

  • DO NOT use search methods like index, count, remove, … they’re slow!

  • DO NOT use in operator on lists

Example 1 - given:

blocknote = ('bottle','lighter','sunscreen')
bed = [ ['bottle','glasses','hat','hat'],
        ['hat','lighter','bottle','bottle'],
        ['hat','lighter','sunscreen','bottle']]

'bottle', 'lighter' and 'sunscreen' are all present, we expect True:

>>> print(go_camping(blocknote, bed))
True

Example 2 - given:

blocknote = ('bottle','lighter','sunscreen')
bed = [  ['book','glasses','hat','hat'],
         ['hat','lighter','book','book'],
         ['hat','lighter','sunscreen','book']]

'lighter' and 'sunscreen' are present, but 'bottle' is not, we expect False:

>>> print(go_camping(blocknote, bed))
False
[6]:


def go_camping(notes, bed):
    raise Exception('TODO IMPLEMENT ME !')

# expect True
print(go_camping(('bottle','lighter','sunscreen'),
                 [ ['bottle','glasses','hat','hat'],
                   ['hat','lighter','bottle','bottle'],
                   ['hat','lighter','sunscreen','bottle']]))

# expect False
print(go_camping(('bottle','lighter','sunscreen'),
                 [  ['book','glasses','hat','hat'],
                    ['hat','lighter','book','book'],
                    ['hat','lighter','sunscreen','book']]))

assert go_camping(('a',), [['a']]) == True
assert go_camping(('b',), [['a']]) == False
assert go_camping(('a','b'), [['a','a'],
                             ['a','b'],]) == True
assert go_camping(('a','c'), [['a','a'],
                             ['a','b'],]) == False
assert go_camping(('a','c'), [['a','a'],
                             ['a','b'],]) == False

assert go_camping(('a','c','d'), [['a','e','b','b'],
                                 ['b','c','a','a'],
                                 ['b','c','d','a']]) == True
assert go_camping(('a','c','d'), [['f','e','b','b'],
                                 ['b','c','f','f'],
                                 ['b','c','d','f']]) == False

m = [['f','e','b','b'],
     ['b','c','f','f'],
     ['b','c','d','f']]
go_camping(('a','c','d'), m)
# shouldn't modify input
assert m == [['f','e','b','b'],
             ['b','c','f','f'],
             ['b','c','d','f']]