PARTIAL EXAM INFORMATICS: FIRST CHANCE

THE PRACTICE OF COMPUTING USING PYTHON AND UNIX

Bachelor of Science in Molecular Biotechnology Friday 30-11-2018, 8h30-12h30
Bachelor of Science in Environmental Technology First term – Group A1 & A2
Bachelor of Science in Food Technology Academic year 2018-2019

Lecturer-in-charge: Wesley De Neve

Teaching assistants: Mijung Kim, Jasper Zuallaert, Utku Özbulak

Student name: …………………………………………………………………………………………………………………

Student number: …………………………………………………………………………………………………………………

Score non-periodic evaluation: ………………………………………………………………….……… / 5

Score periodic evaluation: ………………………………………………………………….……… / 15

Partial exam score: …………………………………………………………………….…… / 20

1
Exam guidelines

Practical arrangements

 Students must be in possession of a Ghent University student ID card. This student ID card
must remain on the desk of the student for the duration of the exam.

 Students have four hours to complete the assignments.

 Students who take part in the exam should stay in the room for at least 30 minutes; if a
student wishes to submit the exam blank, it is sufficient to send a notification by email to the
lecturer on the day before the exam, in which case it is no longer necessary to attend the
exam physically; the assignments will be posted on Minerva shortly after the exam. Students
are not permitted to leave within the last 30 minutes of the exam.

 This is an open-book exam, allowing for the usage of the following materials and tools:

the course slides and your personal notes a Python IDE (e.g., PyCharm)
the course handbook an interactive Python session
your personal solutions for the hands-on sessions the Minerva course site
the example solutions for the hands-on sessions Google Translate

 Students are not allowed to make use of Dodona and the Online Python Tutor, nor are
students allowed to make use of tools for instant messaging and e-mail, tools for online
social networking, and tools for file sharing. These tools need to be turned off during the
exam. This will be actively checked by staff members present in the room. Also, students are
not allowed to visit websites other than Minerva and Google Translate.

 Students must not communicate in any way with other students during the exam. Also,
students are not allowed to make use of electronic devices other than a personal laptop.

 Students are allowed to continue the exam on paper in case of a laptop failure, on the
condition that students have first informed the staff members present. A penalty of five
points will be imposed.

 Make sure to upload all your Python scripts to the Dropbox section of Minerva, using the file
names provided. Multiple submissions are allowed, and the most recent submission
uploaded before the end of the exam will be used for grading purposes. Make sure your
Python script contains your name and your student number. Double-check the integrity of
your Python script on Minerva. Solutions will be graded on correctness and coding style,
following the four-eyes principle. Moreover, the following grading policy is in place:

Criterion Penalty Penalty Penalty

assignment 1 assignment 2 assignment 3
No comments -4 points -5 points -6 points
No test examples or doctests -2 points -2 points -2 points
No meaningful variable and function names -2 points -2 points -2 points
Script not executable -2 points -2 points -2 points
Wrong file name or wrong file type -1 point -1 point -1 point
No student name or student number -1 point -1 point -1 point

 Test examples and doctests are available in the following folder on the Minerva course site:
Documents > 20181130_am_exam_informatics_term1

2
Cheating policy

 Upon detection of cheating during an exam, the student(s) involved will get a notification of
the staff members present. Next, the staff members present will take a snapshot of the
current state of the exam, after which the student(s) involved are allowed to continue with
the exam. Immediately after the exam, the Examination Board will be notified. The
Examination Board will also be notified upon detection of cheating during grading (e.g., upon
detection of identical or suspicious patterns in the solutions submitted).

 Penalties for cheating during an exam are severe and are described in detail in the Education
and Examination Code of Ghent University. Upon confirmation of cheating by the
Examination Board, as a minimum, all students involved will get a zero, both the students
sharing and copying/modifying solutions. In addition, all students involved run the risk of
expulsion, with a transcript explicitly mentioning cheating, severely hampering the chance of
getting admission at another university.

Hints and tricks

 This exam tests to what extent you are able to apply the program design cycle for creative
problem solving, asking you to tackle three coding challenges taken from either the field of
mathematics, computer science, biology, physics, or chemistry.

 Read each assignment carefully, focusing on the information you really need in order to solve
the problem at hand.

 Take a few minutes to plan the outline of your solution on paper. This will help you write
well-structured source code in a step-by-step fashion. Make sure to apply the divide-and-
conquer problem-solving strategy.

 Plan in advance how much time you will allow yourself to spend initially on each of the
assignments.

 Add comments to your source code. Give clues about the structure and non-trivial sections
of your code to the people grading your solutions.

 Save intermediate versions of your solutions, or take advantage of the fact that you can
submit multiple versions of your solutions.

 The total time for the exam is four hours. If time allows, you can check whether there is a
better (read: shorter or faster) solution for the assignments than the one you came up with
initially; a better solution may give you a score that is higher (use comments to indicate
where you have made additional improvements).

 If you do not pass this first exam opportunity for the first term, then please be reminded that
a second-chance exam will take place in June, and a third-chance exam in August.

3
Programming assignment 1: Early warning (4 points)
Published in 1915, Cleveland Moffet's The Conquest of America imaged a German assault on the
United States in 1921. Moffett had intended the novel as a warning of the importance of military
preparedness, and it was quickly forgotten, but one passage would come to take on an eerie
significance — an attack on Manhattan:

"Ah! So!" said von Hindenburg, and he glanced at a gun crew who were loading a half-ton
projectile into an 11.1-inch siege-gun that stood on the pavement. "Which is the Woolworth
Building?" he asked, pointing across the river.

"The tallest one, Excellency — the one with the Gothic lines and gilded cornices," replied one
of his officers.

"Ah, yes, of course. I recognize it from the pictures. It's beautiful. Gentlemen," — he
addressed the American officers, — "I am offering twenty-dollar gold pieces to this gun crew
if they bring down that tower with a single shot. Now, then, careful! …

"Ready!"

We covered our ears as the shot crashed forth, and a moment later the most costly and
graceful tower in the world seemed to stagger on its base. Then, as the thousand-pound shell,
striking at the twenty-seventh story, exploded deep inside, clouds of yellow smoke poured out
through the crumbling walls, and the huge length of twenty-four stories above the jagged
wound swayed slowly toward the east, and fell as one piece, flinging its thousands of tons of
stone and steel straight across the width of Broadway, and down upon the grimy old Post
Office Building opposite.

"Sehr gut!" nodded von Hindenburg. "It's amusing to see them fall. Suppose we try another?
What's that one on the left?"

"The Singer Building, Excellency," answered the officer.

"Good! Are you ready?"

Then the tragedy was repeated, and six hundred more were added to the death toll, as the
great tower crumbled to earth.

"Now, gentlemen," — von Hindenburg turned again to the American officers with a tiger
gleam in his eyes, — "you see what we have done with two shots to two of your tallest and
finest buildings. At this time tomorrow, with God's help, we shall have a dozen guns along this
bank of the river, ready for whatever may be necessary."

In the end, J.P. Morgan, Andrew Carnegie, and John D. Rockefeller are held hostage and ordered to
raise a billion dollars to indemnify the city. "The Conquest of America is as full of thrills as the most
excitable and fearful patriot need ask," raved the Independent. "If all the prominent Americans
named in the tale, as hostages or otherwise, get about the business of preparedness, this invasion
will never be."

4
 Fig. 1 The Conquest of America (Cleveland Moffett, 1915).

Assignment
We consider the skyline of a city with a number of tall buildings standing next to each other. Below,
as an example, you can see the skyline of New York City, with a number of the largest buildings
displayed to scale.

Fig. 2 Sections of buildings that can be seen when looking from a large distance to the left to the New York City skyline.

If you would look at these buildings from a large distance to the left, which sections of what building
would be visible, if we assume that buildings in the back are completely hidden by the buildings in
front of them?

Input
The first line contains a number 𝑛 ∈ ℕ0 that indicates the number of buildings that are standing next
to each other. The 𝑛 buildings are then described from the left to the right by their name and their
height in meters (an integer), each on a separate line.

5
Output
Describe the sections of the buildings that are visible if you look at the given skyline from a large
distance to the left. In doing so, you may assume that buildings in the back are completely hidden by
the buildings in front of them. The (sections of the) buildings must be listed in increasing distance
order from the point of view. The exact format of the output can be derived from the example given
below. This example corresponds to the skyline depicted in the above figure.
Example
Input:

8
Singer Building
187
Woolworth Building
241
Chrysler Building
319
Metropolitan Life Tower
213
One World Trade Center
541
Comcast Building
259
New York Times Tower
319
Empire State Building
381

Output:

Singer Building is visible from the ground floor up to 187 meters.

Woolworth Building is visible from 187 meters up to 241 meters.
Chrysler Building is visible from 241 meters up to 319 meters.
One World Trade Center is visible from 319 meters up to 541 meters.

Submission
Upload the Python script lastname_firstname_warning.py to the Dropbox section of the
Minerva course site before the end of the exam. Submit this Python script to all teachers.

6
Programming assignment 2: 123 (5 points)
Write down a positive integer on a piece of paper:

886328712442992

Count up the number of even and odd digits, and the total number of digits:

10 5 15

String the digits of those three numbers together to make a new number:

10515

Perform the same operation on the obtained number:

1 4 5 ⟶ 145

And keep iterating:

1 2 3 ⟶ 123

You will always arrive at the number 123.

Note

In applying the procedure to determine the next number, leading zeros must be dropped
(this will occur if the original number has no even digits). For example, if we start from the
number 111, we determine the next number as

0 3 3 ⟶ 33 (not 033)

This makes a difference because 33 has no even digits (and gives 22 if we apply the
procedure once more), whereas 033 does have an even digit (and would give 123 if we
apply the procedure once more).

Assignment

 Write a function evenOdd that takes as input an integer 𝑛 ∈ ℕ. The function must return a
tuple containing two integers, that respectively indicate how many even and odd digits occur
in 𝑛.

 Write a function step that takes as input an integer 𝑛 ∈ ℕ. The function must return the
number obtained when applying the operation as described in the introduction once to 𝑛.

 Write a function steps that takes as input an integer 𝑛 ∈ ℕ. The function must return how
often the operation from the introduction must be applied before the number 123 is
reached, if we start from 𝑛.

7
Example

>>> evenOdd(886328712442992)
(10, 5)
>>> evenOdd(10515)
(1, 4)
>>> evenOdd(145)
(1, 2)

>>> step(886328712442992)
10515
>>> step(10515)
145
>>> step(145)
123

>>> steps(886328712442992)
3
>>> steps(1217637626188463187643618416764317864)
4
>>> steps(0)
2
>>> steps(1)
5

Submission
Upload the Python script lastname_firstname_123.py to the Dropbox section of the Minerva
course site before the end of the exam. Submit this Python script to all teachers.

8
Programming assignment 3: Merry Christmas (6 points)
With the holiday season approaching, Charles Trigg proposed this festive cryptarithm in The
American Mathematical Monthly, edition December 1956.

Fig. 3 Puzzle proposed by Charles Trigg.

The above sentence contains four words and ten different letters. If each letter is a unique
representation of a digit, and each word is a perfect square, what are the four numbers?

The puzzle turned out to have two different solutions. The table below shows how the letters have to
be replaced by digits to get these two solutions.

The four perfect squares of the first solution are:

Fig. 4 One of two possible solutions of the puzzle proposed by Charles Trigg.

9
The four perfect squares of the second solution are 34225 7396 81 900. If we would fine-tune
the puzzle to MERRY XMAS TO YA ALL, then YA is replaced by 59 in the second solution, which
is not a perfect square. However, the first solution remains correct, as it results in the following
perfect squares: 27556 3249 81 64 400.

Assignment
Solve a puzzle where the words of a given sentence contain ten different uppercase letters. The
words of the sentence are separated by a single space.

A solution of the puzzle is a one-to-one correspondence (a bijection) between the ten uppercase
letters in the sentence and the ten digits. When all letters of the sentence are replaced by their
corresponding digit, then a solution is valid on the condition that each word of the sentence is a
perfect square. We use two different representations for a solution.

 The dictionary representation of a solution is a dictionary that maps the ten different
uppercase letters onto the ten digits, with the digits represented as integers.

 The string representation of a solution contains two strings. The first string contains the ten
different uppercase letters. The second string contains the ten digits, with each uppercase
letter of the first string corresponding to the digit at the same position in the second string.
The second string does not have to be mentioned explicitly if the ten letters in the first string
are mapped onto the digits 0, 1, 2, …, 9.

Your task:
1. Write a function solution that takes as input the string representation of a solution (one
or two arguments). The function must return the dictionary representation of that solution.

2. Write a function replace that takes as input two arguments: 𝑖) a string containing the
sentence of a puzzle and 𝑖𝑖) the dictionary representation of a solution. The function must
return the given sentence, where all letters have been replaced by the corresponding digits
according to the given solution of the puzzle.

3. Write a function isSquare that takes as input a positive number (int). The function must
return a Boolean value that indicates whether the given number is a perfect square.

4. Write a function isCorrect that takes as input the sentence of a puzzle (one string
argument) and the string representation of a solution (one or two string arguments). The
function must return a Boolean value that indicates whether the given solution is a correct
solution for the given puzzle.

Hint: Make use of default parameters in order to deal with a variable number of arguments.

The functions solution and isCorrect must raise an AssertionError with the message
invalid solution, in case the first argument of the given solution is not a string containing ten
different uppercase letters or in case the second argument of the given solution is not a string that
contains the ten different digits.

The functions replace and isCorrect must raise an AssertionError with the message
invalid puzzle, in case the words of the given sentence are not composed of the letters in the
given solution or in case the words of the given sentence are not separated from each other by a
single space.

10
Example

>>> solution('LOMXARYETS')
{'L': 0, 'O': 1, 'M': 2, 'X': 3, 'A': 4, 'R': 5, 'Y': 6, 'E': 7, 'T': 8, 'S': 9}
>>> solution('AELMORSTXY', '4702159836')
{'L': 0, 'O': 1, 'M': 2, 'X': 3, 'A': 4, 'R': 5, 'Y': 6, 'E': 7, 'T': 8, 'S': 9}
>>> solution('MERYXASTOL', '2765349810')
{'L': 0, 'O': 1, 'M': 2, 'X': 3, 'A': 4, 'Y': 5, 'R': 6, 'E': 7, 'T': 8, 'S': 9}
>>> solution('BANANARAMA')
Traceback (most recent call last):
AssertionError: invalid solution

>>> l2c = solution('LOMXARYETS')

>>> replace('MERRY XMAS TO ALL', l2c)
'27556 3249 81 400'
>>> replace('MERRY XMAS TO YA ALL', l2c)
'27556 3249 81 64 400'

>>> l2c = solution('LORMEYSXTA')

>>> replace('MERRY XMAS TO ALL', l2c)
'34225 7396 81 900'
>>> replace('HAPPY NEWYEAR', l2c)
Traceback (most recent call last):
AssertionError: invalid puzzle

>>> isSquare(27556)
True
>>> isSquare(34225)
True
>>> isSquare(12345)
False

>>> isCorrect('MERRY XMAS TO ALL', 'LOMXARYETS')

True
>>> isCorrect('MERRY XMAS TO ALL', 'LORMEYSXTA')
True
>>> isCorrect('MERRY XMAS TO YA ALL', 'AELMORSTXY', '4702159836')

11
True
>>> isCorrect('MERRY XMAS TO YA ALL', 'MERYXASTOL', '2765349810')
False
>>> isCorrect('MERRY XMAS TO ALL', 'BANANARAMA')
Traceback (most recent call last):
AssertionError: invalid solution
>>> isCorrect('HAPPY NEWYEAR', 'LOMXARYETS')
Traceback (most recent call last):
AssertionError: invalid puzzle

Submission
Upload the Python script lastname_firstname_christmas.py to the Dropbox section of the
Minerva course site before the end of the exam. Submit this Python script to all teachers.

12