################################################################################
################################################################################
################################################################################
''' WARNING!!! SAVE THIS FILE AS program.py '''
''' WARNING!!! WRITE BELOW YOUR NAME, SURNAME AND STUDENT ID '''
nome = "NAME"
cognome = "SURNAME"
matricola = "STUDENT ID"
###############################################################################
################################################################################
################################################################################
# DEBUG SUGGESTIONS
# to run only some of the tests, you can comment rows 288-292 at the end of grade.py
#
# to check the error stack trace, you can uncomment row 36 of testlib.py
################################################################################
################################################################################
################################################################################
'''Ex 1: 6 points.
A file contains some integer numbers written as follows:
- each number is separated by one or more empty lines
- each number is written in one or more consecutive lines, one for
each digit
- each line with a digit begins with a % sign and has the digit in its
unary representation, namely, with as many 1's as its value.
- each number is written from the most significant digit to the least
one.
As an example, file "U1.txt" contains the numbers 5049, 10, 94, 0, 49, 66.
The ones are always consecutive (no white spaces or other char between 1's).
The file always ends with an empty line.
Design the function ex1(pathname) that gets as input the pathname of a
file as described above and returns the list of the numbers written in
it. The list has to be ordered with respect to the number of digits
and, then, to their value.
As an example, for file 'U1.txt', the function has to return the following list:
[5049,10,49,66,94,0]
'''
def ones_to_digit(string):
return string.count('1')
def ex1(pathname):
digits = ''
numbers = []
with open(pathname) as f:
for line in f:
if line.startswith('%'):
digits+= str(ones_to_digit(line[1:]))
else:
if digits:
numbers.append(int(digits))
digits = ''
if digits:
numbers.append(int(digits))
numbers.sort(key = lambda x: (-len(str(x)), x))
return numbers
#####################################################################################
'''
Ex 2: 8 points
We have a set P containing points, each point is a tuple (x,y)
with the coordinates of the point. We want to produce an image
with the given points and, possibly, some vertical and some
horizontal segments.
In particular:
1) the height h and the width w of the image are the minimum
values able to contain the coordinates of all points.
2) The points are drawn in the image with the red color (255,0,0)
on a black background (0,0,0).
3) For every point p=(x,y) for which there are two points
p1=(x1,y) with x1>x and same y
and p2=(x,y1) with y1>y and same x
a white segment (255,255,255) is drawn that joins p to the nearest
point between p1 and p2 (to p1 if the two distances are equal).
In other words if to the right of p there is a point p1 with the same
y-coordinate as p1 and below p there is a point p2 with the same x
coordinate, in the image will appear
- a horizontal segment between p and p1, if p1 is less distant
(or at the same distance) than p2 from p, or
- a vertical segment between p and p2, if p1 is more distant than
p2 from p.
For example the image corresponding to the set
P={(20,10),(20,20),(20,40),(40,40),(50,20),(50,70),(60,20)}
will have height 70 and width 60 and is shown in figure I1.png
Design the function ex2(P, fname) that takes as input the set of
points P and the address fname of a .png file. The function saves
at the address fname the image obtained from the set of points P
and returns the number of horizontal segments in the image.
To load and save PNG files, use the load and save functions of the
images library. '''
import images
def ex2(P,fname):
xsegments = []
ysegments = []
for x,y in P:
## For each point, build the set of points with same coords
xset = {p for p in P if p[0] == x and p[1] > y}
yset = {p for p in P if p[1] == y and p[0] > x}
if xset and yset: # only if a point shares both coords with other points
x1 = min(yset) # get the closer one on the right of x,y
y1 = min(xset, key = lambda p:p[1]) # get the closer one below x,y
if x1[0]-x <= y1[1]-y: # if the closer between the two is on the right
xsegments.append((x,y,x1[0],x1[1]))
else: # if the closer between the two is below
ysegments.append((x,y,y1[0],y1[1]))
# determine the size of the image
maxx = max(P)[0]
maxy = max(P, key = lambda p:p[1])[1]
# create the image, with size maxx+1 * maxy+1 (if a point is at coord x,
# we have x+1 pixels, since we start counting from 0)
imm = []
for i in range(maxy+1):
imm.append([(0,0,0)]*(maxx+1))
# draw the red points
for x,y in P:
imm[y][x] = (255,0,0)
# draw the horizontal segments
for x,y,x1,y1 in xsegments:
for i in range(x+1,x1):
imm[y][i] = (255,255,255)
# draw the vertical segments
for x,y,x1,y1 in ysegments:
for j in range(y+1,y1):
imm[j][x] = (255,255,255)
# save the image
images.save(imm, fname)
return len(xsegments)
############################################################################
'''
Ex. 3: 9 points
Given a node in a tree, the node degree is the number of children
of the node.
Design the recursive function ex3(r) (or a function that makes use
of of recursive function(s) or method(s)) that receives as
parameter the root r of a tree made by nodes of type Node, as
defined in the tree.py library. The function returns a dictionary.
The dictionary contains as keys, the degrees of the nodes in the
tree. For each key, the associated value is the list of values of
the nodes in the tree with that degree. The list must be in
non-decreasing order.
As an example, given the following tree:
16
________|_____________
| | |
2 4 5
| _____|______
10 | | | | |
1 2 9 8 2
__|__
| |
3 6
the function ex3 returns the dictionary
{3: [16], 1: [2], 0: [1, 2, 3, 5, 6, 8, 9, 10], 5: [4], 2: [2]}
NOTE: any subfunction, if present, should be defined at the external
level to pass the recursion check '''
import tree
def ex3(r):
dict_return = {len(r.sons):[r.value]}
# base case: r is a leaf
if r.sons == []:
return dict_return
# recursive case: r has some sons
for son in r.sons:
son_dict = ex3(son)
# get the dictionary generated by each subtree and...
for degree, value_list in son_dict.items():
# ... use it to extend the actual dictionary
if degree not in dict_return:
dict_return[degree] = value_list
else:
dict_return[degree].extend(value_list)
# sort the lists in the dictionary
for value_list in dict_return.values():
value_list.sort()
return dict_return
###########################################################################
'''
Ex. 4: 9 points
Design and implement a recursive function (or a function that uses
recursive functions or methods) ex4(dirname, s) that receives as
an input the name of a directory (dirname) and a string (s). The
function explores the directory dirname and its subdirectories and
returns a list of tuples. There is one tuple for each file with
extension .txt containing occurrences of the string s
(case-insensitive) encountered during the visit. The tuples are
pairs (a,b) where:
- a is the full name of the file
- b is the number of times the string was found in that file.
The list is in alphabetical order, with respect to the first
coordinate of the tuples.
Any file or directory starting with '.' or '_' has to be ignored.
As an example, if dirname='dir1' and s='angelo', the function ex4
returns the list:
[('dir1/st1/st2/1W.txt', 4), ('dir1/st1/st2/Ncn.txt', 5), ('dir1/zzzEFG.txt', 1)]
NOTE: it is forbidden to use os.walk or similar recursive system
functions
NOTE: any subfunction, if present, should be defined at the external
level to pass the recursion check
'''
import os
def ex4(dirname, s):
ret = []
for file in os.listdir(dirname):
fullpath = os.path.join(dirname,file)
if os.path.isfile(fullpath) and file.endswith('.txt'):
with open(fullpath) as f:
text = f.read()
n = text.lower().count(s.lower())
if n>0:
ret.append((fullpath, n))
elif os.path.isdir(fullpath) and not file.startswith('.') and not file.startswith('_'):
ret.extend(ex4(fullpath, s))
ret.sort()
return ret
#################################################################################