Assignment 2 COMP 208 Winter 2020
posted: Wednesday, February 5, 2020
due: Wednesday, February 19, 2020 at 23:59
Primary Learning Objectives
By the end of this assignment, students should be able to…
• Repeat code using a while loop in order to perform user input validation as well as other common operations.
• Use lists in Python to maintain multiple user inputs and calculate properties of sequences.
• Index and slice strings.
• Use a dictionary to maintain a relationship between keys and values in a given context.
Submission instructions
• This file should have been accompanied by a .zip file called Assignment2.zip. Unzip this file to produce a directory called Assignment2 containing four Python code files. You will write the solutions to this assignment in these four files.
• When ready to submit, zip up the Assignment2 folder and submit the resulting Assign- ment2.zip file to myCourses. Before zipping, make sure that the folder is still named As- signment2 and that the four Python code files inside are still named as follows:
– sequence.py
– parentheses.py – encryption.py – dungeon.py
Any deviation from these requirements will result in deduction of points.
• You can submit multiple times on myCourses, so don’t worry if you realize that your current submission contains an error.
• Submit early, submit often! (Computer crashes do occur, and myCourses may be overloaded during rush hours.)
Coding instructions
• You must include your name and McGill ID number at the top of each Python code file
that you implement and submit. By doing so, you are certifying that the code file is entirely 1
your own, and represents the result of your sole effort.
• You are expected to put comments in each file, on average 1 comment for every 5-6 lines,
to explain what the code is doing. Failure to do so will result in deduction of points.
• You are expected to use descriptive names for variables whenever possible. Do not use variable names like x, y or z (unless you are dealing with a mathematical function like f(x)). Instead, use names like user input, sum of numbers, or average value. Failure to give your variables descriptive names will result in deduction of points.
• Some questions will ask you to define a function of a given name. The function you define must have the same name as given. Further, every question will have examples to show the output that your program is required to produce. Make sure that the output of your program exactly matches the output of the examples. (Input values are highlighted in gray, as they should be input by the user.) Failure to exactly match function names and output will result in deduction of points.
• If you have prior programming knowledge, you may know how to do a question using more advanced concepts. Although it may be more efficient to use such advanced concepts, it defeats the purpose of the assignment as we are testing on specific language constructs. Therefore, please only use concepts discussed in class up to and including February 5 (the day Assignment 2 was posted). Solutions that use Python concepts seen after February 5 will be penalized (excluding nested loops, which are permitted). Further, third-party modules are not permitted.
Policies
• Late assignments will be accepted up to 2 days (48 hours) after the due date and will be penalized by 10 points per day. Note that submitting one minute late is the same as submitting 23 hours late. We will deduct 10 points for any student who submits or resubmits after the due date irrespective of the reason, be it wrong file submitted, wrong file format submitted or any other reason. This policy will hold regardless of whether or not the student can provide proof that the assignment was indeed “done” on time.
• If your program does not work at all, e.g., gives an error and does not produce any output, zero points will be given for that question. If your program executes without errors but produces incorrect output, partial marks may be awarded based on the correctness of the code.
• If anything is unclear, it is up to you to seek clarification by either directly asking a TA during office hours or making a post on the myCourses discussion board.
• Work submitted in this course must represent your own efforts. Assignments must be done individually; you must not work in groups. Do not ask friends or tutors to do this assignment for you. You must not copy any other person’s work in any manner (electronically or other- wise), nor give a copy of your work to any other person. Code similarity detection software will be run on all assignments.
2
Question 1 [15 points]
This question will ask you to do an exercise involving lists. You are asked to write a function fetch that takes in a list of positive, non-zero integers, and returns the smallest integer not in the list. For example, the smallest positive integer not in the list [1, 5, 2] is 3, so the function should return 3. You must also write a function get input from user that creates a list based on user input, which we will use to create the list for the first function.
The two functions should be implemented as follows:
Name: fetch
Parameters: A list ‘numbers’ of positive, non-zero integer values.
Return value: The smallest positive integer not in the list. If an empty list is given, return the value 1.
Name: get list from input
Parameters: No parameters
Return value: A list of positive, non-zero integers entered by the user.
What it should do: Ask the user to enter a number(s) with the prompt ‘Enter number(s): ’, then convert their entered numbers to integer and store them in a list. Keep asking the user to enter numbers until they enter the word ‘done’, at which point you should return the list of all numbers entered. The user may enter just one number on a line, or they could enter a series of comma-separated numbers, in which case each of the numbers must be added to the list. If the user enters any values less than 1, do not add them to the list. For example, if the user enters ”4,5,-2” on one line, 4 and 5 should be added to the list, but -2 should not. You can assume the user will not enter any spaces, and only enter digits from 0-9 without any letters or special characters.
Filename
You must write this program in a file called sequence.py. In the file, the two functions are already
defined for you, and at the bottom of the file there are calls to the functions.
Examples (as executed in Thonny)
Example 1:
>>> %Run sequence.py Enter number(s): done 1
3
Example 2:
Example 3:
Example 4:
Example 5:
>>> %Run sequence.py
Enter number(s):
Enter number(s):
1
0
done
>>> %Run sequence.py
Enter number(s):
Enter number(s):
2
1
done
>>> %Run sequence.py
Enter number(s):
Enter number(s):
Enter number(s):
Enter number(s):
3
1
5
2
done
>>> %Run sequence.py
Enter number(s):
Enter number(s):
Enter number(s):
Enter number(s):
Enter number(s):
5
1
2
3
4
done
Example 6:
>>> %Run sequence.py
Enter number(s):
Enter number(s):
Enter number(s):
Enter number(s):
9
1,5,2 3,7,6
4,8
done
4
Question 2 [25 points]
Mr. Parr N. Thesis is having a problem with his parentheses. When writing, he replaces all his commas with an opening parenthesis ‘(’, and then inserts a closing parenthesis ‘)’ at the end of the sentence. For example, instead of writing ‘Hello, World!’ he writes ‘Hello( World!)’. He does this for every comma in the sentence. For example, the sentence ‘Me, myself, and I’ would become ‘Me( myself( and I))’, and the sentence ‘The first five letters of the alphabet are a, b, c, and d.’ would become ‘The first five letters of the alphabet are a( b( c( and d.)))’
In order to understand Mr. Thesis’ writings, we will write code to help translate his sentences by replacing the parentheses with commas in the appropriate positions. We will do this by writing four functions as follows. (Note that there are other ways to do this question, but you must implement each of these functions as described; we will be testing each of your functions individually. Further, like in all other questions, you can only use concepts seen in class up to and including February 5. That is, you may not use the string methods replace, index, find, rindex, rfind, partition or rpartition methods for this question.)
Name: find first
Parameters: A string s and character letter
Return value: The first index of the character letter in the string s. (Hint: Loop over the string’s indices, starting at 0.) If the character letter is not present in s, return the value None.
Name: find last
Parameters: A string s and character letter
Return value: The last index of the character letter in the string s. (Hint: Use your code from find first but start at the last index.) If the character letter is not in s, return None.
Name: get comma phrase
Parameters: A string s containing at least one opening ‘(’ and one closing parenthesis ‘)’
Return value: The string s with the first opening parenthesis replaced by a comma, and the last closing parenthesis deleted. (Hint: Use the functions above to get the indices of the two parentheses, then use string slicing to get the parts of the string that are between the parentheses (3 parts in total), and put the parts back together with a comma inserted in the appropriate location.)
Name: get comma string
Parameters: A string s
Return value: The string s with all opening parentheses replaced by commas and all closing paren- theses deleted. (Hint: The function get comma phrase returns a new string with the first and last parenthesis of the string deleted. If there are several sets of opening and closing parentheses in the string, then how many times should you call the function? A while loop will be useful (but you should figure out when to stop looping).)
5
Filename
You must write this program in a file called parentheses.py. In the file, the four functions are already defined for you, and at the bottom of the file there is some test code already present. It asks the user to type in a string, then prints out the result of the get comma string function.
Examples (as executed in Thonny)
Example 1:
Example 2:
Example 3:
Example 4:
>>> %Run parentheses.py Enter text: Hello( World) Hello, World
>>> %Run parentheses.py
Enter text: Me( myself( and I)) Me, myself, and I
>>> %Run parentheses.py
Enter text: The first five letters of the alphabet are a( b( c( and d.))) The first five letters of the alphabet are a, b, c, and d.
>>> %Run parentheses.py
Enter text: No commas in this sentence! No commas in this sentence!
6
Question 3 [40 points]
In cryptography, a simple substitution cypher is a method of encryption in which each letter of a phrase is replaced by a different letter or sequence of letters. The phrase can then be decrypted by performing the inverse of the substitution.
In this question, we will implement a simple substitution cypher in which a character (letter, number, or special symbol) is substituted by a two-digit number between 00 and 99 (inclusive). For example, the letter ‘a’ could be encrypted to become the number ‘06’, or the special symbol ‘!’ could become the number ‘57’.
We will use a dictionary to store the mapping between each character and its corresponding en- crypted form. That is, the keys of the dictionary will be the regular characters (letters, numbers and special symbols), and the values will be the encrypted forms of the characters (the two-digit numbers between 00 and 99).
Your code should implement the following five functions for this question.
Name: create cypher dictionary Parameters: No parameters.
Return value: A dictionary where each key is a regular character and each value is a random two-digit number between 00 and 99, inclusive.
What it should do: At the top of the code provided to you, the string LETTERS is defined. This string contains all the letters, numbers and special symbols that should be keys in the dictionary. You will have to loop over this string, and generate a two-digit random number between 00 and 99 for each character. The two-digit numbers will be the values in the dictionary; each character (key) will have one two-digit number (value). Note that the numbers 0, 1, 2, …, 9 should not be values; instead, they should be the numbers 00, 01, 02, …, 09. Further, note that each character should have a unique random number. That is, if the character ‘a’ maps to the value ‘57’, no other character should map to the value ‘57’. (You will need to use some sort of loop to keep generating new random numbers until a unique one is found.)
Name: encrypt Parameters: A string s.
Return value: The encrypted version of the string s. Each character of the original string s should be replaced by its corresponding two-digit number in the cypher dictionary.
Name: decrypt
Parameters: A string s.
Return value: The decrypted version of the string s. Each two-digit number of the encrypted string s should be replaced by its correponding character in the cypher dictionary. Note that here, we have the encrypted form (value in the dictionary), and are looking to find the regular character (key
7
in the dictionary). To do this, we will need to use the reverse lookup function as seen in class. This function has been provided to you in the included encryption.py file.
∗∗∗
We will write two further functions to increase the strength of our encryption. One function will repeatedly encrypt the string multiple times. The other function will attempt to decrypt the string, without knowing the number of times it was encrypted (thus defeating the point of the stronger encryption).
Name: encrypt multiple times
Parameters: A string s and integer value n for the number of times to encrypt the string.
Return value: The string s encrypted n times. I.e., the string will be encrypted a first time, with each character turned into its two-digit representation. Then, the encrypted string will be re- encrypted, with each digit turned into its two-digit representation. (The length of the string will thus double after every encryption.) (Hint: You will have to call your encrypt function multiple times.)
Name: decrypt multiple times
Parameters: A string s.
Return value: The decrypted version of the string s. As we do not know how many times to decrypt the string, we will keep calling decrypt on the string until the string contains a common word in the English language. A list of common words, COMMON WORDS, has been provided for you in the encryption.py file. If, after decrypting once, the string contains any word in this list, then you should immediately return the decrypted string. Otherwise, continue calling decrypt on the string until it does contain one of the common words. (We will assume that the fully decrypted string will always contain at least one common word.)
∗∗∗
Finally, at the end of the file encryption.py, you will notice some code already written for you. This code asks the user to input a string, then calls the various functions and prints what they return (to produce the examples seen below). You must alter this code so that if the user enters a string that does not contain any of the words in the COMMON WORDS list, then the program should output ”Invalid input.” and not execute the rest of the code. Otherwise, the program should continue with the rest of the code. (Hint: Think back to Assignment 1 and if/else branches.)
Filename
You must write this program in a file called encryption.py.
8
Examples (as executed in Thonny)
Example 1:
Example 2:
>>> %Run encryption.py
Enter text to encrypt: abcdef Invalid input.
>>> %Run encryption.py
Enter text to encrypt: The quick brown fox jumps over the lazy dog.
Encrypted string: 0766546138001892056159999714256163973761640073940161973354996⌋
→ 169665461919809956156975155
Decrypted string: The quick brown fox jumps over the lazy dog.
Encrypted x2 string: 3417626247536227487834342778713634476227477171717117275336⌋
→ 476227624871174817622762533434174871533427622771174848475371716227627162624 ⌋
→ 7536227712771783471714762274762711747274747
Decrypted x2 string: The quick brown fox jumps over the lazy dog.
Example 3:
>>> %Run encryption.py
Enter text to encrypt:
→ No, not again. I… why does it say paper jam when there is no paper jam? Encrypted string:
→ 129746612597696198519818255561705555556114669561569754016118696101989561949 ⌋
→ 89454996164987361146654256169665499546118016125976194989454996164987390 Decrypted string: No, not again. I… why does it say paper jam when there is
→ no paper jam? Encrypted x2 string:
→ 273671175362622736477117627162277178472771782778364747476227173447474747474 ⌋
→ 762272753626271476227476271174753342762272778627162273427717871476227715371 ⌋
→ 787153475371716227625371781748622727536262475336476227627162624753717147536 ⌋
→ 2272778342762273647711762277153717871534753717162276253717817487134
Decrypted x2 string: No, not again. I… why does it say paper jam when there
→ is no paper jam?
9
Question 4 [20 points]
You have just started your new job as a puzzle engineer at Sierra Studios. Your first task is to create a simple ‘escape the room’ type game in the Python programming language.
An ‘escape the room’ game is defined as follows. When the program runs, a description of a room with no exits will be given to the user (listing objects and people in the room). The user will then be given a chance to type in a command to interact with the objects and/or people in some way (e.g., ‘examine the table’ or ‘talk to Bob’). Interacting in this manner will give responses containing hints as to how to escape the room. For example, after examining the table and talking with Bob, the user might discover they have to flip the lightswitch in order for a secret door to open. Then, if the user enters ‘flip the lightswitch’, they will win and the game will be over.
Your ‘escape room’ implementation must contain at least the following elements:
• A function escape room that returns True only when the player has escaped the room suc- cessfully. (E.g., in the above example, True would be returned if the user enters the phrase ‘flip the lightswitch’.)
• The function should start by printing a description of the room, including the objects you can examine and people you can talk to.
• Commands should be stored in a dictionary, with each key being a command and each value being the message to print when that command is entered.
• Inside a loop, the user should be asked to enter a command, and then the corresponding message in the dictionary should be printed. If the command is not present in the dictionary, ”Invalid command.” should be printed. The command should be turned into lowercase, so if the user uses capitals in an otherwise valid command, the command will still work.
• Two special commands, not stored in the dictionary, should also be available for the user. One is the command ‘commands’, which should display to the user all commands present in the dictionary. The other command will be the special command that lets the user escape the room (e.g., ‘flip the lightswitch’ in the example above). This command should print a message like ‘You have found the secret door!’ and then return True. Try to make this command easy to guess, or allow multiple ways for the user to express it (e.g., ‘enter 0 in keypad’ might also be expressed as ‘press 0’ or ‘enter 0’ or ‘press key 0’).
• There should be at least one object in the room for the user to examine, and when the user types ‘examine [object]’, a hint should be given about how to escape the room. This object should be listed in the description. Note that it does not have to be an object, but at minimum something that can be examined (e.g., texture of the walls of the room, rug on the floor, etc).
• There should be at least one named person in the room for the user to talk to, and when the user types ‘talk to [person]’, a hint should be given about how to escape the room. This person should be listed in the description. Note that it does not have to be a person, but minimally something that can give and/or receive input (e.g., computer, intercom, keypad, etc).
• At the top of your code file, give your escape room a name by defining the ROOM NAME variable, 10
and write your name in the AUTHOR variable. (These will have no use for your code, but we will use them in grading.)
Any submission meeting these requirements will get full marks, but you are encouraged to go beyond them, either in terms of creativity of descriptions, complexity of puzzles, or technical sophistication. The most impressive submissions (as judged by our TAs) will be shown in class and/or stitched together into a combined work.
Filename
You must write this program in a file called dungeon.py. Some code is already provided to
you.
Examples (as executed in Thonny)
Example 1:
>>> %Run dungeon.py
You find yourself in a dark room. A candle lies on a small table in front of
→ you, providing a small amount of light. You cannot see any door or exit.
→ However, there is what seems to be a keypad on one of the walls.
> EXAMINE CANDLE
The candle is tall and thin. You decide to pick it up to examine the rest of
→ the room more closely. You think you can make out half of a mathematical
→ equation on the walls: e to the power i times pi…
> examine keypad
It is a standard keypad, with digits from 0-9. Looking closely, you think you
→ can make out half of a mathematical equation scratched into the wall above
→ it: + 1…
> smash keypad
Invalid command.
> Commands
Commands are: examine candle, examine keypad > enter 0 in keypad
A secret door opens!
11
Example 2:
>>> %Run dungeon.py
You have walked deep into a cave, looking for treasure, when suddenly you
→ wander down a dead-end and hear the tumble of rocks from behind you. You
→ are trapped! In front of you, the rock face is smooth and glistening with
→ moisture. Moss of many different hues grows on the surface. There is an
→ eerie silence, punctuated only by the drops of water from the ceiling into
→ a small pond next to you. What do you do?
> commands
examine moss
examine pond
> examine moss
You examine the moss closely. Most of the moss are hues of green, but there is
→ one very small area where it is bright purple. You suddenly realize this
→ purple moss is displayed in the shape of a key hole. Perhaps if you had a
→ key, you could use it here.
> examine pond
You kneel down and peer into the pond. In the reflection of the water, you see
→ yourself with a key in your hand.
→ key in your pocket. Startled, you
→ there is a key there! If only you
> put key in keyhole
A secret door opens in the rock wall!
Your reflection then smiles and puts the
stand up and feel inside your pocket —
knew where to use it.
12