1        (20 marks)     Python Programming: Basic Programming Structure

The code must be written in the provided file question_1.py, failing to do so will result in loss of marks.

The Caesar cipher is a very simple encryption method and it is easily breakable. In this question

we used an improved encryption method. Given a plain text message T of n characters using an alphabet A of m letters, and a list S of n positive integers from the set {0, 2, .., k - 1}, T is       encrypted by shifting the kth character T[k] by an amount S[k]. An example is given in Figure1

where T = [B, A, B, Y] and S = [2, 1, 1, 3]. The first character ’B’ is shifted by 2 giving the     character ’D’, then the second character ’A’ is shifted by 1 giving ’B’ and so on. The encrypted message is "DBCB".

Figure 1: Example of the encryption method proposed in this question.(a) the top row represents the character to be encrypted, the bottom row is the encrypted character given a certain shift. Note how the alphabet is repeated in the bottom row. (b) shows the encryption of

the message "BABY" using a shift sequence 2113 resulting in the encrypted message "DBCB".

(i)       [10 marks]     Implement the function encrypt(message,  shifts,  alphabet) that  takes a plain text message as a string, the shifts sequence as a list of integers, and the    alphabet as a string. The alphabet can be any sequence of symbols, not necessarily the     English alphabet. The function returns a string containing the encrypted message. The function raises a ValueError exception if:

•  the message contains characters that are not in the alphabet,

•  the size of the shifts is not the same as the size of message,

•  shifts contains negatives values or values greater or equal to the size of the alphabet.

(ii)      [10 marks]     Write the docstring for this function. The docstring must follow Google

documentation style.

2        (15 marks)     Python Programming: String and List

The code must be written in the provided file question_2.py, failing to do so will result in loss of marks.

The aim of this exercise is to transform a string representing a molecule into a list of tuples,      where the first element of a tuple is the String corresponding to an atom, and the second          element is the number of occurrences of that atom at the given position in the structure of the  molecule. For example, the molecule CO2 given by the string ’CO2’ is represented by the list of tuples  [(’C’,1),(’O’,2)].

Glucose C6H12O6 is represented by ’C6H12O6’ and  [(’C’,6),(’H’,12),(’O’.6)].

The Acetic acid molecule CH3COOH is given by the string ’CH3COOH’ and the list of tuples [(’C’,1),   (’H’,3),   (’C’,1),   (’O’,1),   (’O’,1),   (’H’,1)].

Some atoms are described by more than one character, like calcium Ca. The first character is uppercase and the second character is lower case. For example, the calcium carbonate          molecule CaCO3 is represented by the string ’CaCO3’ . Its list representation is

[(’Ca’,1),   (’C’,1),   (’O’,3)].

(i)       [15 marks]     Implement a function molecule_to_list(molecule) that takes a string

representation of a molecule as described above and return its list of tuples representation. The function raises a ValueError exception if:

•  molecule does not start with a uppercase letter from the English alphabet,

•  molecule contains characters that are not alphanumeric.

•  molecule has an invalid format, for example the symbol of an atom is lower case like ca instead of Ca or h instead of H.

Up to 10 marks will be given if the function handles molecules containing only single character atoms, and up to 15 marks if the function can handle any kind of molecules.

ATOMS.

4        (15 marks)     Recursion

The code for this question must be written in the provided file question_4.py.

Warning: if the implemented function for this question is not recursive, a mark of 0 will be         awarded.  The aim of the exercise is to check if a game level is feasible or not. The game is a  simple 2D platform composed of springboards with power ups and deadly traps (represented by mines). The power ups’ number below the springboard represents the player’s maximum jump

length from that board. The aim of the game is to depart from the first springboard and arrive to the last one without stepping on a mine. Figure 2shows a game level that is feasible, whereas Figure 3shows a game level that a player cannot win.

Figure 2: Example of a game level that is feasible. One solution is to jump 2 steps from index 0 to 2, then 2 steps from index 2 to 4 and finally another 2 steps to the last index.

Figure 3: Example of a game level that is impossible to complete. Whatever the choice you make, you will always arrive at index 3 which is a deadly trap.  It is therefore impossible to reach the last index.

To represent the level, we have chosen a list of non-negative integers. The starting point of the level is at the first index of the list, and the exit is at the last index of the list. The numbers in the

list represent the power up of the springboard at that position. A mine is represented by the       value 0. In this context, if the element at the last index is 0 then the level is not feasible. For       example, the board shown in Figure 2 is represented by the list  [3,1,2,0,4,0,1]. Similarly, the board shown in Figure 3 is represented by the list  [3,2,1,0,2,0,2].

(i)       [15 marks]     Implement a recursive function check_level(level) that takes a list of positive integers representing a game level and returns True if the level is feasible, False otherwise. The efficiency of the solution does not matter, you should implement a brute force approach that tries all possible cases.

5        (30 marks)     User defined data structures

The code for this question must be written in the provided file question_5.py.

In this question, we will start building the game Blotris, a knock-off version of Tetris™. The aim is to add many random shapes to the board before we cannot add more. In Figure 4we can see  how a shape is added at a given position. When a row is fully occupied, it is removed and the   rows above that row are shifted down. For example, when adding the shape in Figure 4, two     rows are fully occupied. Figure 5shows how these two rows are removed and how the rows     above them are shifted down.

(i)       [5 marks]     Implement a class Blotris, with a constructor that takes two integer parameters rows and cols in that order. The parameter rows represents the number of rows on the      board, and cols the number of columns. The board shown in Figure 4was constructed with 8 rows and 5 columns.

•  the class Blotris has an instance attribute _board which is a 2D list of integers       representing the board. The value 0 represents an empty block, the value 1 an occupied block.

•  the constructor should initialise _board to a 2D list of rows rows and cols columns containing only zeros.

•  The constructor raises a ValueError if rows or cols is not greater or equal to 5.

•  You can add more instance attributes if needed.

.

(ii)      [10 marks]     Implement the method add(self,  shape,  row,  col) that adds a shape to a game board at row row and column col. The pair (row, col) is where the top-left corner of the shape should be. Figure 4shows a shape added at row = 3 and col = 1. Remember

rows and columns start at index 0.

Figure 4: Example of adding a shape to the game board at row 3 column 1, that is the fourth row and the second column.