Description

1.1. Aims. The purpose of the assignment is to:
• let you design solutions to simple problems;
• let you implement these solutions in the form of short python programs;
• practice the use of arithmetic computations, string manipulation, tests, repetitions, lists, tuples, dictionaries, reading from files.
1.3. Assessment. Each of the 4 exercises is worth 2.5 marks. For all exercises, the automarking script will let each of your programs run for 30 seconds. Still you should not take advantage of this and strive for a solution that gives an immediate output for “reasonable” inputs.
The outputs of your programs should be exactly as indicated.
1
2
2. Rain
rain.py, that performs the following task.
directory, then the program outputs an (arbitrary) error message and exits.
• The program prompts the user to input a nonnegative integer. If the input is not a nonnegative integer, then the program outputs an (arbitrary) error message and exits.
• The contents of the file consists of some number of lines, each line being a sequence of the same number of nonnegative integers separated by at least one space, with possibly spaces before and after the first and last number, respectively. These numbers represent the height in centimetres of a block with a square base of 10 square centimetres. For instance, the contents of the file land.txt can be represented as
2 2 2 2 2
1 3 4 3 2
2 3 5 3 2
2 4 1 1 2
and would represent a land covering an area of 50 centimetres by 40 centimetres, with a block of height 2 centimetres in each corner, etc. The number input by the user represents a quantity of rain in decilitres, to be poured down on the land.
• The program outputs the height in centimetres, with a precision of 2 digits after the decimal point, that is reached by the water.
Here is a possible interaction:
$ cat land.txt
2 2 2 2 2
1 3 4 3 2
2 3 5 3 2
2 4 1 1 2
$ python3 rain.py
Which data file do you want to use? land.txt
How many decilitres of water do you want to poor down? 1 The water rises to 1.33 centimetres.
$ $ python3 rain.py
Which data file do you want to use? $ land.txt
How many decilitres of water do you want to poor down? 33 The water rises to 4.00 centimetres.
$ $ python3 rain.py
Which data file do you want to use? $ land.txt
How many decilitres of water do you want to poor down? 50 The water rises to 4.89 centimetres.
You can assume that the contents of any test file is as expected, you do not have to check that it is as expected.
3
3. Triangle
triangle.py, that performs the following task.
directory, then the program outputs an (arbitrary) error message and exits.
• The contents of the file consists of some number of lines, each line being a sequence of integers separated by at least one space, with possibly spaces before and after the first and last number, respectively, the Nth line having exactly N numbers. For instance, the contents of the file triangle_1.txt can be displayed as follows.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
• The program outputs:
– the largest value than can be obtained by summing up all numbers on a path that starts from the top of the triangle, and at every level down to the penultimate level, goes down to the immediate left or right neighbour;
– the number of paths that yield this largest value; – the leftmost such path, in the form of a list.
Here is a possible interaction:
$ cat triangle_1.txt
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
$ python3 triangle.py
Which data file do you want to use? triangle_1.txt
The largest sum is: 30
The number of paths yielding this sum is: 1
The leftmost path yielding this sum is: [7, 3, 8, 7, 5] $ cat triangle_2.txt
1
2 2
1 2 1
2 1 1 2
1 2 1 2 1
2 1 2 2 1 2
$ python3 triangle.py
Which data file do you want to use? triangle_2.txt
The largest sum is: 10
The number of paths yielding this sum is: 6
The leftmost path yielding this sum is: [1, 2, 1, 2, 2, 2]
You can assume that the contents of any test file is as expected, you do not have to check that it is as expected.
4
4. Fishing towns
fish.py, that performs the following task.
directory, then the program outputs an (arbitrary) error message and exits.
• The contents of the file consists of some number of lines, each line being a sequence of two nonnegative integers separated by at least one space, with possibly spaces before and after the first and second number, respectively, the first numbers listed from the first line to the last line forming a strictly increasing sequence. The first number represents the distance (say in kilometres) from a point on the coast to a fishing town further down the coast (so the towns are listed as if we were driving down the coast from some fixed point); the second number represents the quantity (say in kilos) of fish that has been caught during the early hours of the day by that town’s fishermen. For instance, the contents of the file coast_1.txt can be displayed as
5 70
15 100
1200 20
which corresponds to the case where we have 3 towns, one situated 5 km south the point, a second one situated 15 km south the point, and a third one situated 1200 km south the point, with 70, 100 and 20 kilos of fish being caught by those town’s fishermen, respectively.
• The aim is to maximise the quantity of fish available in all towns (the same in all towns) by possibly transporting fish from one town to another one, but unfortunately losing x kilos of fish per kilometre. For instance, if one decides to send 20 kilos of fish from the second town to the first one, then the second town ends up having 100−20 = 80 kilos of fish, whereas the first one ends up having 70+20−(15−5) = 80 kilos of fish too.
• The program outputs that maximum quantity of fish that all towns can have by possibly transporting fish in an optimal way.
Here is a possible interaction:
$ cat coast_1.txt
5 70
15 100
1200 20
$ python3 fish.py
Which data file do you want to use? coast_1.txt
The maximum quantity of fish that each town can have is 20.
$ cat coast_2.txt
20 300
40 400
340 700
360 600
$ python3 fish.py
Which data file do you want to use? coast_2.txt
The maximum quantity of fish that each town can have is 415.
You can assume that the contents of any test file is as expected, you do not have to check that it is as expected.
5
5. Partial orders
nonredundant.py, that performs the following task.
directory, then the program outputs an (arbitrary) error message and exits.
• The contents of the file consists of lines with text of the form R(m,n) where m and n are integers (that just represent labels), with possibly spaces before and after the opening and closing parentheses, respectively. It represents a partial order relation R (so an asymmetric and transitive binary relation). For instance, the contents of the file partial_order.txt can be represented as:

It can be seen that two facts are redundant:
– the fact R(3,1), which follows from the facts R(3,5), R(5,2) and R(2,1);
– fhe fact R(4,1), which follows from the facts R(4,2) and R(2,1).
• The program outputs the facts that are nonredundant, respecting the order in which they are listed in the file.
Here is a possible interaction:
$ cat partial_order.txt
R(3,5)
R(4,2)
R(5,2)
R(2,1)
R(3,1)
R(4,1)
$ python3 nonredundant.py
Which data file do you want to use? partial_order.txt The nonredundant facts are:
R(3,5)
R(4,2)
R(5,2)
R(2,1)
You can assume that the contents of any test file is as expected, you do not have to check that it is as expected.