Files

Assignment05.pdf a5_q1_template.py a5_q2_template.py encoded_maps.zip decoded_map1_ans.txt

Coursemology

Assignment 5: Dictionary Note

Questions

1. Treasure Map 1.1 Secret Message 1.2 Decoding a Map 1.3 Find Treasure

2. Ancestry Tree 2.1 Are You My Ancestor? 2.2 Are They Related?

[20 marks] [20 marks] [20 marks]

[20 marks] [20 marks]

Unzip all files in encoded_maps.zip in the same folder as template Python files. Question 1: Treasure Map

1.1 Secret Message [20 marks]

On a quest for treasure, you chance upon a weird, seemingly encrypted message. What could it mean?

 esbtr dgh abzqg! vhe ghz yzqtcjxx qx qt btgesjz cbxepj! 

Thankfully, you always have your handy guide dictionary with you.

guide={ 'a': 'm', 'b': 'a', 'c': 'c', 'd': 'y', 'e': 't', 'f': 'v', 'g': 'o', 'h': 'u', 'i': 'x', 'j': 'e', 'k': 'j', 'l': 'w', 'm': 'f', 'n': 'z', 'o': 'd', 'p': 'l', 'q': 'i', 'r': 'k', 's': 'h', 't': 'n', 'u': 'g', 'v': 'b', 'w': 'q', 'x': 's', 'y': 'p', 'z': 'r'

Translating each letter in the encrypted message using the guide dictionary, you get the final message:

 esbtr dgh abzqg! vhe ghz yzqtcjxx qx qt btgesjz cbxepj! 

 thank you mario! but our princess is in another castle! 

To ease the discussion, we will use the following terminologies:

: The original message before encrypting. : The encrypted message (i.e., message after encrypting).

: The process of encrypting message into cipher.

: The process of reversing the encryption to get the message from the cipher (a.k.a. decipher).

message

cipher

encryption

decryption

2

continue on the next page...

1 2 3 4 5 6}

Question

Write the function decrypt(cipher, guide) that performs decryption on the cipher using the guide. Your function should be able to decrypt any cipher using any guide dictionary and return

the original message. As such, the guide dictionary should not be hardcoded using the above example. Characters in the cipher that are not found in the guide dictionary can be taken as-is without any substitution. You are guaranteed that there will be no capital letters in the cipher.

Assumptions

The keys and values in guide are single characters. Restrictions

The dictionary guide should not be modified. Sample Run #1

1 2

1.2 Decoding a Map

[20 marks]

>>> print(decrypt("esbtr dgh abzqg! vhe ghz yzqtcjxx qx qt btgesjz cbxepj!", guide)) 

thank you mario! but our princess is in another castle! 

After a long and arduous journey, you finally obtain the treasure map. However, much to your disappointment, the treasure map is encrypted as well.

 ZZ1DDZDDD1DZD1ZZZ1ZD111223222B;+;44411DZ11DZ Z1D1ZZD1111ZZ111ZDD1ZD04CFF0B+BB0220Z1DDZ1ZD Z1ZZ11DDZZZ1ZZD1DZDZ1Z400F22+;+200202Z111Z11 1ZD1ZZZ1DD11DZ1Z1Z11Z24F22222B;BB40F2111DDZD 1DDZZZZZ1DDDZ1DDD1D1120402444+BBB44C2DZD1ZDD 

You now turn to a different guide dictionary.

map_guide = { 'D': 'W', '1': 'W', 'Z': 'W', 'C': 'T', '3': 'T', 'F': 'T', '0': '.', '2': '.', '4': '.', 'B': '^', '+': '^', ';': '^', 'Q': 'E', '7': 'E', '8': 'E', 'X': 'M', 'P': 'M', '!': 'M', '(': ':', ')': ':', '9': ':', '*': ' ', '|': ' ', '#': ' ' 

With the dictionary, you should be able to decipher the above encrypted map into something like this:

 WWWWWWWWWWWWWWWWWWWWWWW..T...^^^^...WWWWWWWW WWWWWWWWWWWWWWWWWWWWWW..TTT.^^^^....WWWWWWWW WWWWWWWWWWWWWWWWWWWWWW...T..^^^......WWWWWWW WWWWWWWWWWWWWWWWWWWWW..T.....^^^^..T.WWWWWWW WWWWWWWWWWWWWWWWWWWWW........^^^^..T.WWWWWWW 

You should have gotten the hint on where the treasure is from the last test case in Question 1.1. Your task is to decrypt the map and then find the treasure.

3

continue on the next page...

Question

You may think that decrypting the map is the same job as Question 1.1 but you are wrong. This time, you need to read the map from a file by yourself and then return a map as a list (list) of string (str). Your task is to write a function such that mapfile is a file containing the encrypted map and is the guide dictionary similar to Question 1.1. The function should read the data from mapfile and use guide to decrypt the map. The function should return a list (list) of string (str) where each line corresponds to each line on the map after being decrypted. You should not include the newline character (i.e., " " , note this is treated as a single character in Python and not two characters) in your result.

Figure 1: A possible directory structure containing a5_q1_template.py and encoded_map1.txt.

For instance, after decode_map('encoded_map1.txt', map_guide) , you should read the en- coded file encoded_map1.txt and return a map below. Note that the map below is printed using the given print_map function. For your code to work, encoded_map1.txt has to be in the same directory as a5_q1_template.py.

 WWWWWWWWWWWWWWWWWWWWWWW.TTT..^^^^...WWWWWWWW WWWWWWWWWWWWWWWWWWWWWW...T..^^^^....WWWWWWWW WWWWWWWWWWWWWWWWWWWWWW......^^^......WWWWWWW WWWWWWWWWWWWWWWWWWWWW..T.....^^^^..T.WWWWWWW WWWWWWWWWWWWWWWWWWWWW........^^^^..T.WWWWWWW WWWWWWWWWWWWWWWWWWWW........^^^....T.WWWWWWW WWWWWWWWWWWWWWWWWWWW........^^^......WWWWWWW WWWWWWWWWWWWWWWWWWWWWW.....^^^^.....WWWWWWWW WWWWWWWWWWWWWWWWWWWWWW.....^^^......WWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW....^^......WWWWWWWWW WWWWWWWWWWWWWWWWWWWWWW......^.....WWWWWWWWWW WWWWWWWWWWWWWWWWWWWWW............WWWWWWWWWWW WWWWWWWWWWWWWWWWWWWW....T......WWWWWWWWWWWWW WWWWW...WWWWWWWWWWWWW..T.T.....WWWWWWWWWWWWW WWWW..TTT.WWWWWWWWWWW...T.....WWWWWWWWWWWWWW WWWWW.......WWWWWWWWWWW......WWWWWWWWWWWWWWW WWWWWWWW...T.WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWW....WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWW.T.WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWW.WWWWWWWWWW.....WWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWW....T..WWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW.TTT..WWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW..T..WWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWW...WWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW W: WATER 

 T: TREE .: GRASS 

If you have problem viewing the map above, you can view the file decoded_map1_ans.txt from Coursemology instead.

decode_map(mapfile, guide) 

guide

4

continue on the next page...

Assumptions

The keys and values in guide are single characters. Restrictions

The dictionary guide should not be modified. 1.3 Find Treasure [20 marks]

Once you managed to decipher the map, you are now ready to find the missing treasure! The hint from Question 1.1 tells you that the treasure is in the middle of five (5) trees that are planted in a cross shape like the one highlighted below:

WWWWWWWWWWWWWWWWWWWWWW......^.....WWWWWWWWWW WWWWWWWWWWWWWWWWWWWWW............WWWWWWWWWWW WWWWWWWWWWWWWWWWWWWW....T......WWWWWWWWWWWWW WWWWW...WWWWWWWWWWWWW..T.T.....WWWWWWWWWWWWW WWWW..TTT.WWWWWWWWWWW...T.....WWWWWWWWWWWWWW WWWWW.......WWWWWWWWWWW......WWWWWWWWWWWWWWW WWWWWWWW...T.WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWW....WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWW.T.WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWW.WWWWWWWWWW.....WWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWW....T..WWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW.TTT..WWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWW..T..WWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWW...WWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW

Question

Write a function find_treasure(decodedmap) that reads in a list (list) of string (str) called decodedmap that contains the decoded map and returns the coordinate of the treasure as a tuple

(tuple). Your function should work for any arbitrary map. Note

The indexes for the row and column for the map start from 0. The top left corner of the map has the coordinate (0,0). You may assume that the map will have only one treasure location.

Sample Run #1

1 >>> print(find_treasure('decoded_map1.txt')) 2 (21, 25)