Practical Exam 1 CSC_1F001, Groups 6-10, 8:00-10:00

Part 1: Run-length encoding

In this first part your main task will be to encode and decode such pictures by converting them between:

• a visual representation with ' ' and '*', and
• a numerical representation with integers.

We want to encode a picture line by line, so that every line is coded as a sequence of integers obtained by gathering blocks of identical consecutive symbols. For instance the line ' * * *** ' will be coded by the integers 3 1 2 1 4 3 1. The first integer is always the number of spaces, so if the string starts with *, the integer encoding will start with 0. The remaining integers will always be positive. For example '** *' will be encoded by 0 2 3 1.

This process is known as run-length encoding — a simple and efficient compression method that represents consecutive identical symbols by their count rather than by repetition. It is often used in image compression (for example in some bitmap or fax file formats) because it significantly reduces the size of images that contain large uniform regions.

Exercise 1: Converting a string of digits into a list

To begin we define a function to convert a string of digital characters separated by spaces into a list of numbers. Write a new function string_to_integers_list which takes as input a string representing a series of numerical values, separated by spaces, and returns the list of these numerical values as integers.

Copy the following function stub into your file and complete it:

def string_to_integers_list(string):
    """
    Converts a space-separated string of integers into a list of integers.
    """
    pass # remove this line and replace with your own code

Testing

Now test your code by doing this in the console:

In [1]: string_to_integers_list("3 2 1")
Out[1]: [3, 2, 1]

In [2]: string_to_integers_list("   20 1 1    2")
Out[2]: [20, 1, 1, 2]

Note: It is important to test your function in the console as there is no grader feedback.

Now take a moment to upload your pictures.py file to the moodle assignment corresponding to this exam.

(You can upload pictures.py several times, but only your final upload will be graded - don’t wait until the last moment to upload a preliminary version, in case you miss the cut-off!)

Exercise 2: Converting integers to a line of symbols

Implement and test the function integers_list_to_string, that converts a list of non-negative integers into a string of alternating blocks (spaces then stars). Note that, if the list starts with 0, the string should start with a star.

Copy the following function stub into your file and complete it:

def integers_list_to_string(integers_list):
    """
    Converts a list of integers into a string made of alternating
    blocks of spaces and stars, starting with spaces.
    """
    pass # remove this line and replace with your own code

Testing

Now test your code by doing this in the console:

In [3]: integers_list_to_string([3, 1, 2, 1, 4, 3, 1])
Out[3]: '   *  *    *** '

In [4]: integers_list_to_string([0, 2, 1])
Out[4]: '** '

Hint: you can concatenate strings in Python using the + operator. For example:

In [5]: 'a' + 'b'
Out[5]: 'ab'

We also remind that you can check if a number is even or odd by computing the remainder of its division by 2 with a % 2.

Now take a moment to upload your pictures.py file to the moodle assignment corresponding to this exam.

(You can upload pictures.py several times, but only your final upload will be graded - don’t wait until the last moment to upload a preliminary version, in case you miss the cut-off!)

Exercise 3: From file of digits to picture

Implement and test the function integers_to_picture, that given a file of integer lines, write the corresponding picture into the target file.

Copy the following function stub into your file and complete it:

def integers_to_picture(infilename, outfilename):
    """
    Reads a file with space-separated integers and 
    writes the corresponding picture using 
    alternating blocks of spaces and stars.
    """
    pass # remove this line and replace with your own code

Using the functions you have written for the two previous exercises may be a very good idea.

Testing

Now test your code by doing this in the console:

In [6]: integers_to_picture("integers1.txt", "picture1.txt")

In [7]: integers_to_picture("integers2.txt", "picture2.txt")

You can open the produced files picture1.txt and picture2.txt directly in Spyder. The file picture1.txt should contain this:

                     
          *          
         ***         
        ** **        
       **   **       
        ** **        
         ***         
          *          
                     

while picture2.txt should contain that:

                      
 ******************** 
 ******************** 
 ******************** 
 ******************** 
 ******************** 
 ******************** 
                      

Now take a moment to upload your pictures.py file to the moodle assignment corresponding to this exam.

(You can upload pictures.py several times, but only your final upload will be graded - don’t wait until the last moment to upload a preliminary version, in case you miss the cut-off!)

Exercise 4: Converting a line of symbols into a list of integers

Implement and test the function pattern_to_integers_list, that converts a string of alternating blocks (spaces then stars) into the corresponding list of integers where the first integer is allowed to be zero (if the string starts with *) and all others must be positive.

Copy the following function stub into your file and complete it:

def pattern_to_integers_list(line):
    """
    Converts a string made of alternating blocks of spaces and stars, 
    starting with spaces, into a list of integers representing 
    the lengths of these consecutive blocks.
    """
    pass # remove this line and replace with your own code

Testing

Now test your code by doing this in the console:

In [8]: pattern_to_integers_list('   *  *    *** ')
Out[8]: [3, 1, 2, 1, 4, 3, 1]

In [9]: pattern_to_integers_list(' **')
Out[9]: [1, 2]

In [10]: pattern_to_integers_list('* **')
Out[10]: [0, 1, 1, 2]

Now take a moment to upload your pictures.py file to the moodle assignment corresponding to this exam.

(You can upload pictures.py several times, but only your final upload will be graded - don’t wait until the last moment to upload a preliminary version, in case you miss the cut-off!)

Exercise 5: Integer representation of a picture

Implement and test the function picture_to_integers, that converts a picture made of spaces and stars into its run-length encoded integer representation.

Copy the following function stub into your file and complete it:

def picture_to_integers(infilename, outfilename):
    """
    Reads a picture file made of spaces ' ' and stars '*' and 
    converts each line of that picture into a line of integers representing 
    the run lengths of consecutive blocks of characters. 
    Then writes those integer sequences into an output file.
    """
    pass # remove this line and replace with your own code

Hint: The lines you read from file will contain the endline caracter '\n' at the end. You can remove it by s.strip('\n').

Testing

Now test your code by doing this in the console:

In [11]: picture_to_integers("picture1.txt", "runlength1.txt")

In [12]: picture_to_integers("picture2.txt", "runlength2.txt")

Alternatively, if you did not succeed in producing the files picture1.txt and picture2.txt you can use diamond.txt and block.txt as follows:

In [13]: picture_to_integers("diamond.txt", "runlength1.txt")

In [14]: picture_to_integers("block.txt", "runlength2.txt")

You can open the produced files runlength1.txt and runlength2.txt directly in Spyder. As expected they should be the same as integers1.txt and integers2.txt. In details the file runlength1.txt should contain this:

21
10 1 10
9 3 9
8 2 1 2 8
7 2 3 2 7
8 2 1 2 8
9 3 9
10 1 10
21

while runlength2.txt should contain that:

22
1 20 1
1 20 1
1 20 1
1 20 1
1 20 1
1 20 1
22

You can also test your code on two larger pictures: cat.txt and pumpkin.txt.

Now take a moment to upload your pictures.py file to the moodle assignment corresponding to this exam.

(You can upload pictures.py several times, but only your final upload will be graded - don’t wait until the last moment to upload a preliminary version, in case you miss the cut-off!)

Part 2: Hiding a picture inside a file

In this second part we introduce a new layer of encoding based on a substitution key.
The idea is to replace the visual patterns of '*' and ' ' by letters according to a chosen key.

• When encoding, each '*' symbol (the “active” pixels) will be replaced by a random letter from the key (for instance any vowel if key = "aeiouy"),
  while each ' ' (blank) will be replaced by a random letter not in the key.
• When decoding, we do the opposite: every character belonging to the key is interpreted as a star '*', and others as spaces ' '.

This two-way process allows us to hide a pattern inside an apparently random text, and then recover the pattern using the same key.

Exercise 6: Coding alphabet

Write a function remove_key_from_alphabet that takes two arguments:

1. a string of disctinct characters called the alphabet (for example "abcde"), and
   
2. a string called the key containing certain letters to exclude.

This function must return a new string containing all the letters of the alphabet except those that appear in the key.

Copy the following function stub into your file and complete it:

def remove_key_from_alphabet(alphabet,key):
    """
    Removes the letters from the string alphabet that are in the string key, 
    and returns the resulting string.
    """
    pass # remove this line and replace with your own code

Testing

Now test your code by doing this in the console:

In [15]: remove_key_from_alphabet("abcde", "ab")
Out[15]: 'cde'

In [16]: remove_key_from_alphabet("abcde", "aaaijk")
Out[16]: 'bcde'

In [17]: remove_key_from_alphabet("abcde", "eb")
Out[17]: 'acd'

Now take a moment to upload your pictures.py file to the moodle assignment corresponding to this exam.

(You can upload pictures.py several times, but only your final upload will be graded - don’t wait until the last moment to upload a preliminary version, in case you miss the cut-off!)

Exercise 7: Random encoding

Since we need randomness do not forget to add import random to the beginning of your pictures.py file

Write a function generate_line(message, alphabet, key) that takes three arguments:

1. a string message composed only of ’*’ and ’ ’,
2. a string alphabet containing the allowed letters, and
3. a string key containing the special letters that will replace the ’*’ symbols.

This function must return a new string of the same length as message, where every character is replaced by a letter for the alphabet such that:

• every ’*’ is replaced by a random letter chosen from key;
• every ’ ’ is replaced by a random letter chosen outside key. We encourage you to use the helper function remove_key_from_alphabet(alphabet, key).

Copy the following function stub into your file and complete it:

def generate_line(message, alphabet, key):
    """
    Generates a random line matching the '*'/' ' pattern of `message`.
    '*' is replaced by a random letter from `key`,
    ' ' is replaced by a random letter from `alphabet`not in `key`.
    """
    pass # remove this line and replace with your own code

Hint: Use random.choice(s) to pick one letter randomly from a string s.

Testing

Now test your code by doing this in the console:

In [18]: generate_line("  **  **  **  ", "abcde", "ab")
Out[18]: 'ecaadcaaceaaee'

In [19]: generate_line("  **  **  **  ", "abcde", "ab")
Out[19]: 'cdbbceaaecbadc'

Note that since the function uses randomness, you are not expected to reproduce exactly the examples above. In the following examples, your output should be exactly the same:

In [20]: generate_line("  **  **  **  ", "ab", "a")
Out[20]: 'bbaabbaabbaabb'

In [21]: generate_line("*** *** *", "ae", "e")
Out[21]: 'eeeaeeeae'

Now take a moment to upload your pictures.py file to the moodle assignment corresponding to this exam.

(You can upload pictures.py several times, but only your final upload will be graded - don’t wait until the last moment to upload a preliminary version, in case you miss the cut-off!)

Exercise 8: Random encoding

Implement and test the function generate_file, that converts a picture made of spaces and stars into its random encoding representation.

Copy the following function stub into your file and complete it:

def generate_file(infilename, outfilename, alphabet, key):
    """
    Generates a file of random text lines matching a '*'/' ' pattern file.
    """
    pass # remove this line and replace with your own code

Hint: The lines you read from file will contain the endline caracter '\n' at the end. You can remove it by s.strip('\n').

Testing

Now test your code by doing this in the console:

In [22]: generate_file("diamond.txt", "random_diamond.txt", "abcde", "ab")

In [23]: letters = "abcdefghijklmnopqrstuvwxyz"
Out[24]: 'abcdefghijklmnopqrstuvwxyz'

In [25]: generate_file("letter.txt", "random_letter.txt", letters, "aeiouy")

You can open the produced files random_diamond.txt and random_letter.txt directly in Spyder. Note that since the function uses randomness, you are not expected to reproduce exactly the examples below, but the file random_diamond.txt should globally look like this:

dcdceccecececcdcccece
ededeccdedadeccdeecdd
cedededcdbbaccdddcced
ceecceccabdaaddededec
ecdccedaadccbbecdccec
cceecdedaadabeeeccdec
ddecccedcabbddcdcdeee
eddeeceeeeadcedcdcdec
eeddcdddedeceecddedec

(in particular, there should be 21 character in each line and no a’s and b’s in the first and last lines)

while random_letter.txt should be moreover like that:

fnzvztgwcxszswgcchxzzj
wdgxmnljdniabfqmhjzccc
vkmhhrrzbuaoupvkgnpkbk
hnmqrbtzyijcaegrcfpwqb
qvnxchvuevhmviogzsnsmd
fzmfrzoiyuuoiuaepfjhwh
pmlwxuyrbzmndtfiivzjkl
rlhveinpfbtxphrkeowqcp
vqdmqlntnbbgrjgpmhpwgg
                      

(in particular, there should be 22 character in each line and no vowels in the first and last lines)

When doing generate_file("diamond.txt", "random_diamond.txt", "ab", "a"), the result must be exactly:

bbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbabbbbbbbbbb
bbbbbbbbbaaabbbbbbbbb
bbbbbbbbaabaabbbbbbbb
bbbbbbbaabbbaabbbbbbb
bbbbbbbbaabaabbbbbbbb
bbbbbbbbbaaabbbbbbbbb
bbbbbbbbbbabbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbb

Now take a moment to upload your pictures.py file to the moodle assignment corresponding to this exam.

(You can upload pictures.py several times, but only your final upload will be graded - don’t wait until the last moment to upload a preliminary version, in case you miss the cut-off!)

Exercise 9: Decoding a line

Write a function convert_line_into_pattern that take two string argument line and key and that converts the string line into the string of same length where letters in key have been replaced by '*'and other letters by ' '.

Copy the following function stub into your file and complete it:

def convert_line_into_pattern(line, key):
    """
    Converts a line into '*' and ' ' depending on whether characters are in `key`.
    """
    pass # remove this line and replace with your own code

Testing

Now test your code by doing this in the console:

In [26]: convert_line_into_pattern("eeededdbadccbbdddccde", "ab")
Out[26]: '       **   **       '

In [27]: convert_line_into_pattern("fzmfrzoiyuuoiuaepfjhwh", "aeiouy")
Out[27]: '      **********      '

Now take a moment to upload your pictures.py file to the moodle assignment corresponding to this exam.

(You can upload pictures.py several times, but only your final upload will be graded - don’t wait until the last moment to upload a preliminary version, in case you miss the cut-off!)

Exercise 10: Decoding with the key

Implement and test the function decode_file, that converts a file of characters into a picture made of spaces and stars based on the string key.

Copy the following function stub into your file and complete it:

def decode_file(infilename, outfilename, key):
    """
    Converts characters in a file into a pattern of '*' and ' ', based on `key`.
    """
    pass # remove this line and replace with your own code

Hint: The lines you read from file will contain the endline caracter '\n' at the end. You can remove it by s.strip('\n').

Testing

Now test your code by doing this in the console:

In [28]: decode_file("encoding.txt", "decoding.txt", "ab")

You can open the produced file decoding.txt directly in Spyder. The file decoding.txt should be the same as diamond.txt, that is to say it should contain:

                     
          *          
         ***         
        ** **        
       **   **       
        ** **        
         ***         
          *          
                     

Now take a moment to upload your pictures.py file to the moodle assignment corresponding to this exam.

(You can upload pictures.py several times, but only your final upload will be graded - don’t wait until the last moment to upload a preliminary version, in case you miss the cut-off!)