PYTHON 3.5

Write a program to decode messages! Your program will read from a file, containing information about the code and the encoded message, and your program will decode it, and display the decoded message to the console. For example, a small example le is the following:

 10 1110:  1100:! 1010:, 1011:H 1101:d 1111:e 01:l 100:o 000:r 001:w 101111110101100101011100011000000111011100 

The rset line of the file is the number of unique characters in the message. In this example, there are characters. The next lines of the file are the code-lines. In the example, there are code-lines, where the code (a sequence of 0 and 1 is followed by a character. Observe that the code is separated from its character by a colon :, and that the character is delimited by the quote character. The last line of the file is the message.

Heres the coded message and the decoded result, aligned in a way to make it easy to see:

1011 1111 01 01 100 1010 1110 001 100 000 01 1101 1100 Hello, world!

Note very carefully, because it is important, that the codes have different lengths. For example, the code for l has length , whereas the code for H has length . Also note that the code for l is 01, and 01 never starts the code for any other character. Go look! In general, the complete code for a character never appears as the initial sequence for any other character.

This observation is necessary for decoding. To decode the message, we pull digits one by one from the front of the coded message, and check whether the digits weve pulled forms one of the codes. If so, we put the codes character in the output string. If not, we take another digit from the coded message. The decoding process is to build up potential codes from the message one digit at a time, until we nd an actual code, and then we start over again with one digit from the coded message.

A short example of the decoding process, starting from the front:

We start with the first digit in the coded message, 1. Observe that there is no character whose com-

plete code is 1.

Then we take another digit giving us 10, but 10 is not a complete code for any character.

We take another digit, giving us 101, but its still not a complete code (though there are characters whose code starts with 101).

When we take the th digit, we get 1011, there is no ambiguity: the only possibility is that 1011 is the code for character H. There is no other character whose code starts with the code for H. We put H in our output string.

We restart the decoding at digit , with 1. More complicated examples will have much more interesting codes, with far more than digits per char-

Your task is to read the file, and decode the message, using the codes provided in the le. A collection of example les is posted to Moodle.

Hints:

Read all the lines in the le.

Split each code line using the string method split(:), since the : separates the code from the character. You may assume that the message will not contain the : (colon) character.

Create a dictionary with the code as the key, and the character as the value.

Use the dictionary to decode the message. Check if your potential code is in the dictionary using if

code in codes.

FILE BELOW:

21 00:' ' 111101:',' 11001:'-' 11011:'.' 111011:'H' 111001:'S' 111111:'T' 111000:'W' 1011:'a' 111110:'d' 010:'e' 111100:'h' 111010:'i' 10101:'l' 1001:'m' 11000:'n' 0111:'o' 11010:'r' 1000:'s' 0110:'t' 10100:'y' 1111111111001011011000111010100000101100101010101001011111000000110110100100101111010010011010000111110010101111010001110001011011010000111110001101100110011100100111001110110011101101111010110010101000