COMP9021 T1 2023 Assignment 2

1. General matters

• 1.1. Aim. The purpose of the assignment is to:
  • develop your problem solving skills;
  • design and implement the solutions to problems in the form of small sized Python programs;
  • • in particular but no to only, parse text in files, make use of the dynamic programming algorithmic technique, implement class methods.
• 1.2. Submission. Your programs will be stored in files named poker_dice.py and perimeter.py. After you have developed and tested your program, upload it using Ed (unless you worked directly in Ed). Assignments can be submitted more than once; the last version is marked. Your assignment is due by March 27, 10:00am.
• 1.3. Assessment. The assignment is worth 13 marks. It is going to be tested against a number of inputs. For each test, the automarking script will let your program run for 30 seconds. Late assignments will be penalised: the mark for a late submission will be the minimum of the awarded mark and 13 minus the number of full and partial days that have elapsed from the due date. The outputs of your programs should be exactly as indicated.
• 1.4. Reminder on plagiarism policy. You are permitted, indeed encouraged, to discuss ways to solve the assignment with other people. Such discussions must be in terms of algorithms, not code. But you must implement the solution on your own. Submissions are routinely scanned for similarities that occur when students copy and modify other people’s work, or work very closely together on a single implementation. Severe penalties apply.

2. General presentation

This presentation refers to a number of text files that are provided together with this pdf. Consider the two text files file_1_1.txt and file_1_2.txt:

$ cat -n file_1_1.txt
1 A line to delete: 1
2 A line to delete: 2
3 A line that stays: 1
4 A line that stays: 2
5 A line to change: 1
6 A line that stays: 3
7 A line that stays: 4
8 A line that stays: 5
9 A line that stays: 6
10 A line to delete: 3
11 A line that stays: 7
12 A line that stays: 8
13 A line to change: 2
14 A line to change: 3
15 A line to change: 4
16 A line to change: 5
17 A line that stays: 9
$ cat -n file_1_2.txt
1 A line that stays: 1
2 A line to insert: 1
3 A line that stays: 2
4 A changed line: 1
5 A line that stays: 3
6 A line that stays: 4
7 A line to insert: 2
8 A line to insert: 3
9 A line that stays: 5
10 A line that stays: 6
11 A line that stays: 7
12 A line that stays: 8
13 A changed line: 2
14 A changed line: 3
15 A changed line: 4
16 A line that stays: 9

The Unix diff command can be applied to file_1_1.txt and file_1_2.txt:

$ diff file_1_1.txt file_1_2.txt
1,2d0
< A line to delete: 1
< A line to delete: 2
3a2
> A line to insert: 1
5c4
< A line to change: 1
---
> A changed line: 1
7a7,8
> A line to insert: 2
> A line to insert: 3
10d10
< A line to delete: 3
13,16c13,15
< A line to change: 2
< A line to change: 3
< A line to change: 4
< A line to change: 5
---
> A changed line: 2
> A changed line: 3
> A changed line: 4

Study this example to understand diff’s output.

• d is for delete, for commands of the form l_1dl_2 with l_1 and l_2 two line numbers, or of the form l_1,l_2dl_3 with l_1, l_2 and l_3 three line numbers.
• a is for add, for commands of the form l_1al_2 with l_1 and l_2 two line numbers, or of the form l_1al_2,l_3 with l_1, l_2 and l_3 three line numbers.
• c is for change, for commands of the form l_1cl_2 with l_1 and l_2 two line numbers, or of the form l_1,l_2cl_3 with l_1, l_2 and l_3 three line numbers, or of the form l_1cl_2,l_3 with l_1, l_2 and l_3 three line numbers, or of the form l_1,l_2cl_3,l_4 with l_1, l_2, l_3 and l_4 four line numbers

diff identifies a longest common subsequence (LCS) of lines that are common to both files. It then computes the unique minimal set of commands that allows one to convert the first file into the second one (the ed editor can actually precisely do this). With the previous example, there is a unique LCS, consisting of the lines A line that stays: 1, A line that stays: 2, A line that stays: 3 and A line that stays: 4

...

3. Task specifications

Write a program stored in a file named diff.py that implements three classes,

• DiffCommands,
• DiffCommandsError and
• OriginalNewFiles, the second one deriving from Exception. DiffCommands does not provide any method in its public interface. It builds a DiffCommands object from a text file meant to store a plausible sequence of diff commands, one command per line, without any space on any line, and without any extra line. In case the text file does not satisfy those conditions, the init() method of DiffCommands raises a DiffCommandsError error (1 mark) with as message ...