Exam - Mon 12, Jul 2021

Scientific Programming - Data Science Master @ University of Trento

Download exercises and solutions

Part A - DOOM

Open Jupyter and start editing this notebook exam-2021-07-12.ipynb

The Union Aerospace Corporation (UAC) is the largest inter-planetary corporate entity in existence. While drilling Mars soil, UAC discovered that what human legends call Hell, is actually a dimension reachable from a portal buried in Mars ground. UAC promptly sends space marines into the portal to extract demonic creatures, which now intends to use as military weapons. You are asked to develop a software to map and simulate the entities inside the Mars base. The offer looks questionable, but they pay well, so you accept.

Historical note: DOOM is a glorious videogame by Id Software which first introduced somewhat credible 3d graphics in the early 90s, plus lots of gore. Over time, a number of fans made extensions for it, and even serious projects were born like VizDoom which allows developing AI bots that play DOOM using visual information.

A1 parse_map

Map data is provided in doom-map.udmf, in the UDMF text format (complete specification is long, but we will only use a small subset of it)

We are interested in 3 categories of objects: vertex, linedef, and thing. Each of these objects has a numeric integer id, progressively numbered according to its position in the file starting from zero.

  • a vertex holds coordinates float x ad y.

  • a linedef describes a map segment and holds references to the ids of two verteces v1 and v2

  • a thing can be an entity in the map, like a monster or a space marine. A thing has float x and y coordinates, and an attribute called type (as int)

  • ignore all other categories (like sidedef and sector) and attributes (sidefront, etc)

  • whatever follows a // is a comment

Parse it one line at a time like this and output a dictionary as in expected_map.py file.

  • DO NOT assume number of blank lines is constant

  • DO NOT assume number of parameters is constant

  • DO NOT perform mega .replace on the whole file (i.e. to make it look like a JSON)

Show solution
[2]:


def parse_map(filepath):
    raise Exception('TODO IMPLEMENT ME !')

doom_map = parse_map('doom-map.udmf')
doom_map

Parsing map doom-map.udmf
{'filepath': 'doom-map.udmf',
 'linedef': [{'id': 0, 'v1': 4, 'v2': 1},
             {'id': 1, 'v1': 1, 'v2': 2},
             {'id': 2, 'v1': 2, 'v2': 3},
             {'id': 3, 'v1': 3, 'v2': 0},
             {'id': 4, 'v1': 0, 'v2': 4},
             {'id': 5, 'v1': 5, 'v2': 6},
             {'id': 6, 'v1': 6, 'v2': 7},
             {'id': 7, 'v1': 7, 'v2': 8},
             {'id': 8, 'v1': 8, 'v2': 5}],
 'thing': [{'id': 0, 'type': 1, 'x': -352.0, 'y': 0.0},
           {'id': 1, 'type': 71, 'x': -160.0, 'y': 128.0},
           {'id': 2, 'type': 67, 'x': -128.0, 'y': -64.0},
           {'id': 3, 'type': 71, 'x': 70.0, 'y': 200.0}],
 'vertex': [{'id': 0, 'x': -480.0, 'y': 192.0},
            {'id': 1, 'x': 160.0, 'y': 192.0},
            {'id': 2, 'x': -64.0, 'y': -160.0},
            {'id': 3, 'x': -384.0, 'y': -160.0},
            {'id': 4, 'x': -160.0, 'y': 416.0},
            {'id': 5, 'x': -224.0, 'y': 64.0},
            {'id': 6, 'x': -256.0, 'y': 256.0},
            {'id': 7, 'x': -32.0, 'y': 256.0},
            {'id': 8, 'x': -32.0, 'y': 32.0}]}

[3]:

# TESTING
from pprint import pformat; from expected_map import expected_map
for category in expected_map.keys():
    if category not in doom_map:
        print('\nERROR: MISSING category', category); break
    if category != 'filepath' and len(expected_map[category]) != len(doom_map[category]):
        print('\nERROR: DIFFERENT lengths for category', category); break
    for some_id in range(len(expected_map[category])):
        if category != 'filepath' and expected_map[category][some_id] != doom_map[category][some_id]:
            print('\nERROR at category', category, 'id:',some_id)
            print('  ACTUAL:\n', pformat(doom_map[category][some_id]))
            print('  EXPECTED:\n', pformat(expected_map[category][some_id]))
            break

A2 simulate

UAC is particularly interested in the tactical value of Pain Elementals, which can generate an apparent infinite amount of Lost Souls. UAC has estimated some parameters of these creatures, and wants you to devise a simulation of their behaviour.

PRINT OUTPUT as in the example

MODIFY provided doom map like so (for full modified map see expected_sim.py):

  • The simulation is done in discrete steps of one second each, starting at t=0

  • Every spawn_time seconds, each Pain Elemental generates a new Lost Soul, which must be added to things

  • Each second a Lost Soul moves of up to +/- m integer units along both x axis and/or y axis. The x and y deltas are uniformly distributed independent random variables (hint: to calculate them use random.randint(a,b))

  • For simplicity we assume Lost Souls can pass through walls, but we still impose that they cannot leave the smallest rectangle enclosing the map.

  • At each step, MODIFY every Lost Soul thing by updating its x and y, and keep track of location past values (x,y) as a list in a new parameter trace you will associate to the thing. NOTE: trace holds only past values, never the current one.

  • Assume all other entities stay still

Show solution
[4]:

import random

LOST_SOUL_TYPE = 3006
PAIN_ELEMENTAL_TYPE = 71

def simulate(dmap, duration, m, spawn_time):
    #VERY IMPORTANT: DO *NOT* REMOVE THIS LINE: IT INITIALIZES THE PSEUDO RANDOM
    # NUMBER GENERATOR SO DIFFERENT RUNS ALWAYS GIVE THE SAME 'RANDOM' SEQUENCE
    random.seed(1)

    raise Exception('TODO IMPLEMENT ME !')

doom_map = parse_map('doom-map.udmf')
simulate(doom_map, 31,65,8)  # return *nothing* !

print("\nExample of last generated Lost Soul:\n",doom_map["thing"][-1])

Parsing map doom-map.udmf
Simulating...
Map boundaries:   minx -480.0   miny -160.0   maxx 160.0   maxy 416.0
t = 8 Pain Elemental id = 1 : Spawning Lost Soul id = 4
t = 8 Pain Elemental id = 3 : Spawning Lost Soul id = 5
t = 16 Pain Elemental id = 1 : Spawning Lost Soul id = 6
t = 16 Pain Elemental id = 3 : Spawning Lost Soul id = 7
t = 24 Pain Elemental id = 1 : Spawning Lost Soul id = 8
t = 24 Pain Elemental id = 3 : Spawning Lost Soul id = 9
Elapsed time: 31 seconds

Example of last generated Lost Soul:
 {'id': 9, 'x': 19.0, 'y': 157.0, 'type': 3006, 'trace': [(70.0, 200.0), (50.0, 181.0), (53.0, 144.0), (104.0, 161.0), (66.0, 160.0), (115.0, 224.0), (82.0, 213.0)]}

A3 plot_map

Draw the map:

  • use filename as title

  • there’s no need to plot verteces dots

  • only plot entity names (inserting newlines) - to get them import provided entities_db.py which maps an entity type to its data.

  • make it fancy following this example: plot dark background, and Lost Soul traces with dark color for old trace and bright for recent using alpha parameter

EXTRA (was not required during exam): plot images taking file names from entities_db.py and files from img/ folder

Show solution
[5]:

%matplotlib inline
import matplotlib.pyplot as plt
from entities_db import entities_db

def plot_map(entities, doom_map):
    raise Exception('TODO IMPLEMENT ME !')

plot_map(entities_db, doom_map)
../../../_images/exams_2021-07-12_solutions_exam-2021-07-12-sol_18_0.png

Part B

  • Open Visual Studio Code and start editing the folder on your desktop

  • For running tests: open Accessories -> Terminal

B1 Theory

Write the solution in separate ``theory.txt`` file

B1.1 Complexity

Given a list L of \(n\) elements, please compute the asymptotic computational complexity of the my_fun function, explaining your reasoning. NOTE: please notice that it calls the function my_fun2

def my_fun2(L):
    n = len(L)
    tmp = []
    for i in range(n):
        for j in range(n):
            tmp.append(L[i]/(1+L[j]))
    return tmp

def my_fun(L):
    n = len(L)
    if n <= 1:
        return 1
    else:
        L1 = L[0:n//2]
        L2 = L[n//2:]
        a = my_fun(L1) + max(my_fun2(L1))
        b = my_fun(L2) + max(my_fun2(L2))
        return a - b

B1.2 Hash

What is a hash function? Which python data structures use hash functions?

B2 PyraStack

You are given a PyraStack class which holds a list of lists called _rows. Internal lists only contain - character. Implement this method:

def drop(self, w):
    """ Drops a block of size w on the pyrastack, trying to place it on
        the top leftmost position without having missing blocks below.
        If top row is not feasible, scans for the first available leftmost
        place which can fully accomodate the block.

        - if w is negative, raise ValueError
        - if w is zero, no change is made

        - MUST run in O(h + w) where h is the stack height
    """

Example (rows are printed bottom-up):

[7]:

from pyrastack_sol import *

s = PyraStack()
s.drop(10)
s.drop(7)
s.drop(5)
s.drop(2)
s.drop(3)
s.drop(6)
s.drop(6)
s.drop(1)
s.drop(7)
from pprint import pprint
print("_rows are:");pprint(s._rows, width=150)

DEBUG:  Dropped 10, pyrastack is:
        ----------
DEBUG:  Dropped 7, pyrastack is:
        -------
        ----------
DEBUG:  Dropped 5, pyrastack is:
        -----
        -------
        ----------
DEBUG:  Dropped 2, pyrastack is:
        --
        -----
        -------
        ----------
DEBUG:  Dropped 3, pyrastack is:
        -----
        -----
        -------
        ----------
DEBUG:  Dropped 6, pyrastack is:
        -----
        -----
        -------
        ----------------
DEBUG:  Dropped 6, pyrastack is:
        -----
        -----
        -------------
        ----------------
DEBUG:  Dropped 1, pyrastack is:
        -
        -----
        -----
        -------------
        ----------------
DEBUG:  Dropped 7, pyrastack is:
        -
        -----
        ------------
        -------------
        ----------------
_rows are:
[['-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-'],
 ['-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-'],
 ['-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-', '-'],
 ['-', '-', '-', '-', '-'],
 ['-']]

B3 union_rec

Open bin_tree.py and implement following method:

def union_rec(self, other):
    """ Supposing this is a binary tree of integers, takes another binary tree
        and MODIFIES self so it becomes the union of the two.

        Imagine to overlay the two trees, and:
        - whenever two nodes occupy the same position, the self one is updated
            by summing the corresponding node data from other
        - if other has more nodes than self, create corresponding NEW nodes in self

        - a recursive solution is acceptable
        - DO *NOT* share nodes between the trees
        - DO *NOT* throw away existing nodes in self
        - MUST run in O(max(n,m)) where n,m are the number of nodes in self
          and other
    """

Testing: python3 -m unittest bin_tree_test.UnionRecTest

Example:

[9]:

from bin_tree_sol import *
from bin_tree_test import bt

[10]:

ta = bt(3,
        bt(5,
                bt(7,
                    None,
                    bt(1,
                        bt(17)))),
        bt(6))

tb = bt(8,
        bt(10,
                bt(9,
                    bt(13))),
        bt(12,
                bt(11,
                        None,
                        bt(2)),
                bt(4)))
ta.union_rec(tb)

[11]:

print(ta)

11
├15
│├16
││├13
││└1
││ ├17
││ └
│└
└18
 ├11
 │├
 │└2
 └4

[ ]: