Overview: In today’s digital landscape, email communication plays a crucial role in personal and professional exchanges. Validating email addresses ensures that user inputs are formatted correctly and can help prevent errors in registration systems. In this exercise, you will create a program that validates email addresses based on specific criteria.The input for this program will consist of multiple email addresses in a single line, separated by spaces. The program should first output the validity of each email.A sample input to the program: [email protected] [email protected] [email protected] [email protected] [email protected] Expected output: Valid Valid Valid Invalid ForbiddenTo illustrate the parts of an email, consider the address [email protected]. The part before the ”@” symbol (cmput274) is the local part of the email. The part to the right of the ”@” symbol (ualberta.ca) is the domain, which can be further divided into two components: the second-level domain (ualberta), and the top-level domain (TLD), represented by the extension (.ca).You will write a function called validate email(email) that takes a string input representing an email address and returns whether the email is ”Valid”, ”Invalid”, or ”Forbidden”. The following criteria should be used to classify the email addresses: • Valid: The local part contains only allowed characters (letters, digits, periods, and dashes). The email must contain exactly one ”@” symbol. The domain part must contain a period ”.” and the characters after the period (TLD) must be from a list of allowed domain suffixes (.com, .ca, .org, .net, .gov, .edu). • Invalid: The email address does not satisfy any of the above properties. • Forbidden: The email address is valid but belongs to specific forbidden second-level domains (@scam, @spam, @fakeemail, @trashmail, @pleasenotspam, @therealtaylorswift, @sendmoney). Examples:Input: john [email protected] Return: ”Invalid” (Reason: Invalid character ” ”) Input: [email protected] Return: ”Invalid” (Reason: Invalid domain suffix ”.co”) Input: [email protected] Return: ”Forbidden” (Reason: Forbidden second-level domain) Input: [email protected] Return: ”Valid”Marking Rubric: The code must solve the problem algorithmically. If there is any hardcoding (e.g., if email == “[email protected]”: return “Valid”) for the provided test cases, zero correctness marks will be given. This question will be marked out of 10 for correctness: • 30/30: Pass all 10 of the provided test inputs. • 21/30: Pass any 9 of the provided test inputs. • 12/30: Pass any 4 (or more) of the provided test inputs. • 6/30: Pass any of the provided test inputs.Overview: Strings are essential components in modern programming, acting as the primary means of handling and manipulating textual data. They are widely used in various applications, including user input processing, data representation, and communication between different software systems. Strings allow developers to create dynamic content, such as generating web pages or forming database queries, making them vital for web development and data management. Their flexibility and ease of use make them indispensable in a wide range of programming tasks, highlighting their importance in contemporary software development.In this question, your task is to demonstrate your ability to manipulate strings and perform data analysis on them. Your program will take one sentence as input and perform 3 tasks as follows: 1. Sentence reversal: Reverse the order of words in the input sentence, ensuring that each word retains its original form while the sequence is inverted.2. Duplicate removal: Remove any duplicate words from the reversed list from task 1, ensuring that each word appears only once. 3. Median calculation: Analyze the resulting list from task 2 to find the median word length.Tasks 2 and 3 will build on the output of their preceding tasks, which means that the results of task 1 will be used as the input for task 2, and so on. Input: Bears, beets, Battlestar Galactica. Expected output: Galactica Battlestar beets Bears Galactica Battlestar beets BearsInput: Me think, why waste time say lot word, when few word do trick? Expected output: trick do word few when word lot say time waste why think Me trick do word few when lot say time waste why think Me2.1 Sentence Reversal In this task, you will have to reverse the input sentence. To make the subsequent parts easier, you should remove all occurrences of a few characters from the input string. Write 2 functions, named clean input string(string) and reverse string(string). Their responsibilities are explained below.2.1.1 clean input string(string) This function will take the input string as a parameter and ”clean it up” so that the subsequent tasks are easier to execute. In order to clean up the input string, you will have to remove all occurrences of the following characters from the string: 1. . 2. , 3. ! 5 4. ? 5. ’Example: Input: The cat and the dog saw the cat jump over the fence while the cat chased the dog around the yard with the cat and the dog both running. Output: The cat and the dog saw the cat jump over the fence while the cat chased the dog around the yard with the cat and the dog both running2.1.2 reverse string(string) This function will take the “clean” input string (i.e., the output of the clean input string function) and reverse it.Example: Input: The cat and the dog saw the cat jump over the fence while the cat chased the dog around the yard with the cat and the dog both running Output: running both dog the and cat the with yard the around dog the chased cat the while fence the over jump cat the saw dog the and cat The 2.2 Duplicate removalIn this part, you will have to write a function named remove duplicates(string) which will take the reversed string from part 1 as a parameter, and remove all duplicate words from that string. You should keep the first occurrence of the word and remove all other occurrences. The comparison is case sensitive, so that means ”The” and ”the” are considered two unique words. But ”the” and ”the” are duplicate words.Example: Input: running both dog the and cat the with yard the around dog the chased cat the while fence the over jump cat the saw dog the and cat The Output: running both dog the and cat with yard around chased while fence over jump sawThe 2.3 Median calculation The median is the middle value of a set of numbers when they are arranged in order from smallest to largest. If the set has an odd number of values, the median is the middle number. If the set has an even number of values, the median is the average of the two middle numbers.You will have to write a function named calculate median length(string) which will take the string without any duplicates (from part 2) as a parameter, and calculate the median word length from that string. The output of this function has to be an integer. Therefore if the actual median is 3.5, then the output of this function should be 3.Example: Input: running both dog the and cat with yard around chased while fence over jump saw The Output: 4 Marking Rubric: This question will be marked out of 30 for correctness (pass test cases): • 30/30: Pass all 5 of the test cases • 24/30: Pass 4 of the test cases 6 • 18/30: Pass 3 of the test cases • 12/30: Pass 2 of the test cases • 6/30: Pass any of the test cases3 Writing and testing your solution For the programming questions, you should edit the provided files and add your solution. You can check your solution by running driver.py. You can see the output of your program in the Output/ folder, and any errors in the Error/ folder.Please do not change the driver file, only edit the solution file. You can run the driver in a terminal as follows (assuming your working directory is the assignment folder): $ cd a s si gnmen t 1 $ cd Que s ti on 1 $ python3 d r i v e r . py All t e s t s p a s sed ! $ cd . . / Que s ti on 2 $ python3 d r i v e r . py All t e s t s p a s sed ! $ Please add your name, student number, ccid, operating system and python version at the top of each solution file by replacing the provided comments.4 Submission Instructions Please submit a single file to eclass, called ccid.zip. Please create a folder with the name as your ccid, put your solutions in that folder, zip it and upload it. It is important for the files to have the same name as described below. c ci d / s ol u ti o n Q u e s ti o n 1 . py s ol u ti o n Q u e s ti o n 2 . py
Write Python code for a recursive function that outputs all permutations of [1, …, n] (the list of all numbers from 1 to n) and justify why it works.You should use this function prototype: d e f pe rmu t a ti on s ( n ) : Example output for n = 3: [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]Question 2 (15 points) In this problem, you will implement a stack using a single queue. A stack follows the Last In First Out (LIFO) principle, while a queue follows the First In First Out (FIFO) principle. The goal is to simulate stack behavior using queue operations.Note: Only use one queue to implement the stack. All operations should run in O(n) time, where n is the number of elements in the stack.Task: Implement a class StackUsingQueue with the following methods: c l a s s StackUsingQueue : d e f i n i t ( s e l f ) : ’ ’ ’ You can assume t h i s Queue c l a s s has the f o l l o w i n g methods : pop ( ) : r e t u r n the top o f the queue and pop i t top ( ) : r e t u r n the top o f the queue enqueue ( ) : add an elemen t t o the back o f the queue ’ ’ ’ s e l f . queue = Queue ( ) d e f push ( s e l f , elemen t ) : 1 ’ ’ ’ Add the elemen t t o the queue , and r o t a t e the elemen t t o the f r o n t . This sim ul a t e s pu shin g the elemen t onto the top o f the s t a c k . ’ ’ ’ p a s s d e f pop ( s e l f ) : ’ ’ ’ Remove the f r o n t elemen t . ’ ’ ’ p a s s d e f top ( s e l f ) : ’ ’ ’ Checking the top o f the s t a c k . ’ ’ ’ p a s s d e f i s em p t y ( s e l f ) : ’ ’ ’ Return True i f the queue i s empty . ’ ’ ’ p a s s d e f s i z e ( s e l f ) : ’ ’ ’ Return the number o f el em e n t s . ’ ’ ’ p a s s Example: s t a c k = StackUsingQueue ( ) s t a c k . push ( 1 ) s t a c k . push ( 2 ) s t a c k . push ( 3 ) p r i n t ( s t a c k . top ( ) ) # Output : 3 p r i n t ( s t a c k . pop ( ) ) # Output : 3 p r i n t ( s t a c k . top ( ) ) # Output : 2 s t a c k . push ( 4 ) p r i n t ( s t a c k . pop ( ) ) # Output : 4 p r i n t ( s t a c k . i s em p t y ( ) ) # Output : F al s eImagine a new programming language called FractalScript where arithmetic expressions can include recursively nested sub-expressions denoted by square brackets […]. The result of a sub-expression is squared first before being used in the outer expression.Examples: • Input: “[(2 + 3) * [4 – 1]]” Output: 2025 Explanation: This is a standard arithmetic expression, evaluating to (2 + 3) * (4 – 1) * (4 – 1) = 45. This is squared to give 2025 • Input: “[2 + 3]”Output: 25 Explanation: The sub-expression 2 + 3 evaluates to 5, which is then squared 25. • Input: “2 + [3 * 4]” Output: 146 Explanation: The sub-expression 3 * 4 evaluates to 12. This is squared to give 144, and then added to 2 to give 146. • Input: “[2 + 3 * [4 – 1]]” Output: 841 Explanation: [ 2 + 3 * [ 4 – 1] ] [ 2 + 3 * [ 3 ] ] [ 2 + 3 * 9 ] [ 29 ] 841The sub-expression 4 – 1 evaluates to 3, and is squared to give 9. Then 2 + 3 * 9, evaluates to 29, which is squared to give 841. • Input: “[1 + 2 * [3 – [4 / 2] ] ]” Output: 9 Explanation: [ 1 + 2 * [ 3 – [ 4 / 2 ] ] ] [ 1 + 2 * [ 3 – [ 2 ] ] ] [ 1 + 2 * [ 3 – 4 ] ] [ 1 + 2 * [ -1 ] ] [ 1 + 2 * 1 ] [ 3 ] 9• Input: “[[[1 + 2] + 3] + 4]” Output: 21904 Explanation: [ [ [ 1 + 2 ] + 3 ] + 4 ] [ [ [ 3 ] + 3 ] + 4 ] [ [ 9 + 3 ] + 4 ] [ [ 12 ] + 4 ] [ 144 + 4 ] [ 148 ] 3 21904 • Input: “2 * 3 + [4 – 1] * 5” Output: 51 Explanation: 2 * 3 + [ 4 – 1 ] * 5 2 * 3 + [ 3 ] * 5 2 * 3 + 9 * 5 6 + 45 51Write a Python function fractal eval that takes a string expr representing a valid FractalScript arithmetic expression and evaluates it. The expression may contain: • Positive integer operands• The binary operators +, -, *, and / (integer division) • Square brackets […] for recursive sub-expressions • Parentheses (…) for standard grouping and precedence Standard operator precedence rules apply, with […] having the highest precedence, followed by round brackets, / and *, then + and -.Hint: Operator precedence in an expression with no FractalScript subexpressions can be handled easily with Python’s eval function. You can use either recursion or a stack based method to evaluate fractal eval. We encourage you to try both ways. This question will be marked out of 35 for correctness: • 30/30: Pass all 7 of the provided test inputs. • 24/30: Pass any 5 of the provided test inputs. • 12/30: Pass any 3 (or more) of the provided test inputs. • 6/30: Pass any of the provided test inputs.Overview: Unix paths are used to specify the location of files and directories within a computer’s file system. These paths consist of a series of directories separated by forward slashes (/). The paths can also include special components: • “.” refers to the current directory • “..” signifies the parent directory of the current directory (e.g., the directory above the current one)• The first / of the path denotes the root directory • Consecutive forward slashes // are treated as a single slash / Task: In this question, you will implement a function simplify path(path) that simplifies a given Unix-style file path using a list to represent your stack.The function must process the path and return the shortest simplified path as a string that: • Always starts with a / character • Applies the special characters . or .. • Contains no consecutive slashes // • Removes any trailing / characters If the path does not begin with a /, then return Invalid Path. Examples: Input: /home//foo/../bar Return: /home/bar Input: /a/./b/../../c/ Return: /c Input: /../ Return: / Input: /a//b////c/d/././.. Return: /a/b/c Input: home/foo/./bar/../ Return: Invalid Path• Your stack implementation must utilize a list data structure • Built-in methods for path simplification (such as os.path) are strictly prohibited • Use of the .split() method is strictly prohibited • The input path will always be a valid string containing only lowercase letters, /, ., and .. • The input string path will have a length of: 1 ≤ len(path) ≤ 100Marking Rubric: The code must solve the problem algorithmically. If there is any hardcoding (e.g., if path == “/foo/bar/..”: return “/foo”) for the provided test cases, zero correctness marks will be given. This question will be marked out of 35 for correctness: • 30/30: Pass all 20 of the provided test inputs. • 24/30: Pass any 19 of the provided test inputs. • 12/30: Pass any 8 (or more) of the provided test inputs. • 6/30: Pass any of the provided test inputs.3 Writing and testing your solution For the programming questions, you should edit the provided files and add your solution. You can check your solution by running driver.py. You can see the output of your program in the Output/ folder, and any errors in the Error/ folder. Please do not change the driver file, only edit the solution file.You can run the driver in a terminal as follows (assuming your working directory is the assignment folder): $ cd a s si gnmen t 1 $ cd Que s ti on 1 $ python3 d r i v e r . py All t e s t s p a s sed ! $ Please add your name, student number, ccid, operating system and python version at the top of each solution file by replacing the provided comments.4 Submission Instructions (10 points) Please follow these submission instructions carefully. Correctly submitting all files is worth 10 points. In these files, you must replace ccid with your own ccid. Your ccid is the first part of your UAlberta email ([email protected]). Do not zip any of these files.Please submit the following files to eclass: • ccid writtenQuestions.pdf : Your answers to all written questions should be in this one pdf file. • ccid solutionQuestion1.py : Edit the provided file for question 1. After your solution passes all test cases (which you must test using the driver), rename the file to include your ccid, that is, ccid solutionQuestion1.py and submit it to eclass. • ccid solutionQuestion2.py : Edit the provided file for question 2. After your solution passes all test cases (which you must test using the driver), rename the file to include your ccid, that is, ccid solutionQuestion2.py and submit it to eclass.
Overview: The Iron Bank of Braavos has called in its debts, and as the Master of Coin for the realm, you must repay a sum of S gold dragons. You have unlimited access to a set of coin denominations minted by various houses across the Seven Kingdoms.Your goal is to try to gather coins that total exactly S gold dragons. You can use as many coins as needed from any denomination, including multiple coins of the same value. However, the Iron Bank values efficiency; they demand that you use the minimum number of coins to settle the debt. Input: The input consists of 2 lines. The first line contains a list of available denominations. The second line contains a single integer, S.1. Every coin denomination, di, is within the range: 1 ≤ di ≤ 103 2. 1 ≤ S ≤ 105 – the total sum you need to repay.Output: Output a single integer – the minimum number of coins required to accumulate exactly S gold dragons. Or, if you cannot make exactly the sum S, return -1. Example Input #1: 2 4 7 11 Example Output #1: 2 Example Input #2: 7 9 12 Example Output #2: -1 Example Input #3: 3 7 12 1 Example Output #3:Specifications: • Do not modify the main() function. Marking Rubric: This question will be marked out of 90 for correctness (pass test cases): • 90/90: Pass all 5 of the test cases • 72/90: Pass any 4 of the test cases • 54/90: Pass any 3 of the test cases • 36/90: Pass any 2 of the test cases • 18/90: Pass any of the test cases2 Writing and testing your solution For the programming questions, you should edit the provided files and add your solution. You can check your solution by running driver.py. You can see the output of your program in the Output/ folder, and any errors in the Error/ folder.Please do not change the driver file, only edit the solution file. You can run the driver in a terminal as follows (assuming your working directory is the assignment folder): $ cd a s si gnmen t 5 $ cd Que s ti on 1 $ python3 d r i v e r . py All t e s t s p a s sed ! $ Please add your name, student number, ccid, operating system and python version at the top of each solution file by replacing the provided comments.3 Submission Instructions ( 10 points ) Please follow these submission instructions carefully. Correctly submitting all files is worth 10 points. In these files, you must replace ccid with your own ccid. Your ccid is the first part of your UAlberta email ([email protected]). Do not zip any of these files. Please submit the following files to eclass: • ccid solutionQuestion1.py : Edit the provided file for question 1. After your solution passes all test cases (which you must test using the driver), rename the file to include your ccid, that is, ccid solutionQuestion1.py and submit it to eclass.
Simulating Priority Queue Using a Stack Write a function push with priority(stack, priority, element) that pushes elements onto a stack based on a given priority. Lower priority elements should always appear closer to the top.Your Answer: d e f p u s h w i t h p r i o r i t y ( s t ac k , p r i o r i t y , elemen t ) : # Temporary s t a c k t o h old el em e n t s u n t i l the r i g h t p o s i t i o n i s found temp s t ac k = [ ] # 1 ) Move el em e n t s t o temp s t ac k w hil e m ai n t ai ni n g p r i o r i t y o r d e r # 2 ) I n s e r t the new elemen t with i t s p r i o r i t y # 3 ) Move the el em e n t s back from temp s t ac k t o s t a c k t o m ain t ain t h e i r o r d e r# Example u s a ge s t a c k = [ ] p u s h w i t h p r i o r i t y ( s t ac k , 3 , ”A” ) p u s h w i t h p r i o r i t y ( s t ac k , 1 , ”B” ) p u s h w i t h p r i o r i t y ( s t ac k , 2 , ”C” ) p r i n t ( s t a c k ) # Output : [ ( 3 , ’A ’ ) , ( 2 , ’C ’ ) , ( 1 , ’B ’ ) ]In this question, you will perform several operations on a Binary Search Tree (BST). a) (10 points) Draw the binary search tree after inserting the following 12 elements into an empty BST in the given order [50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 65, 90] b) (5 points) Insert Element: After constructing the BST with the above elements, draw the updated tree after inserting the element 17 into the tree. c) (5 points) Delete Element: Draw the binary search tree after deleting the element 70 from the tree and describe how the tree restructures itself.Demonstrate the quick-sort algorithm step by step, using the last element of the current subarray as the pivot. Given the array: [8, −3, 7, −1, 10, 2, −5]Complete the following table by showing the left partition (L), right partition (G), and the pivot at each step. Perform quicksort recursively on the subarrays and show each intermediate result. Solution Template: Step Pivot Left Partition Right Partition Initial Array – – – 1 2 3 … Final Array – – – Table 1: Solution TemplateNotes for Students: • Use the solution template above to format your answers. • Use the last element of the current subarray as the pivot for each step.Task 2: [2 points] Complete the missing line in the following code fragment to correctly implement merge-sort’s merge function. d e f merge ( S1 , S2 , S ) : i = j = 0 w hil e i + j < l e n ( S ) : i f j == l e n ( S2 ) o r ( i < l e n ( S1 ) and S1 [ i ] < S2 [ j ] ) : S [ i+j ] = S1 [ i ] # copy i t h elemen t o f S1 a s nex t item o f S i += 1 e l s e : # Mi s sin g l i n e j += 1Task 3: [8 points] You are given a function that performs quick sort using extra storage to partition the array. Your task is to fill in the missing lines in the code to complete the quick sort implementation. Code: d e f q u i c k s o r t e x t r a s t o r a g e ( S , a , b ) : i f a >= b : r e t u r n pi v o t = S [ b ] # Choose the pi v o t # C re a te new a r r a y s f o r the p a r t i t i o n s l e f t p a r t i t i o n = [ ] r i g h t p a r t i t i o n = [ ] f o r i i n r an ge ( a , b ) : # I t e r a t e onl y u n t i l b ( e x cl u d e pi v o t ) i f S [ i ] < pi v o t : l e f t p a r t i t i o n . append ( S [ i ] ) e l s e : r i g h t p a r t i t i o n . append ( S [ i ] ) # S o r t l e f t p a r t i t i o n q u i c k s o r t e x t r a s t o r a g e ( l e f t p a r t i t i o n , 0 , l e n ( l e f t p a r t i t i o n ) − 1 ) # S o r t r i g h t p a r t i t i o n q u i c k s o r t e x t r a s t o r a g e ( r i g h t p a r t i t i o n , 0 , l e n ( r i g h t p a r t i t i o n ) − 1 ) # Mi s si n g l i n e s h e r e t o c o r r e c t l y merge the p a r t i t i o n s and pi v o t back i n t o the o r i g i n a l a r r a yHint: After the recursive calls to the left and right partitions, think about how you can reconstruct the original array using the sorted left partition, the pivot, and the sorted right partition. The original array must be updated with these sorted parts.Implement a Python function analyze character frequencies(text) that takes a string text as input and does the following: Count the frequency of each character in the text and store the character-frequency pairs in a dictionary.The function should process the text as follows: • Convert the text to lowercase. • Consider only alphanumeric characters (letters and digits). • Ignore whitespace and punctuation characters. • Store the character-frequency pairs in a dictionary where the keys are the characters and the values are their respective frequencies. Return a list of the characters sorted in descending order based on their frequencies. If multiple characters have the same frequency, sort them in alphabetical order.Instructions: • Implement the analyze character frequencies(text) function according to the given requirements. • You can assume that the input text contains only alphanumeric characters, whitespace, and punctuation characters.• The function should handle case-insensitivity when counting character frequencies. • If the input text is an empty string or contains only whitespace and punctuation characters, the function should return an empty list.Input: Knack for knick-knacks, the keen kangaroo quickly kicked the kooky koala into the knapsack by the kayak on the kooky creek. Output: [’k’, ’a’, ’e’, ’o’, ’n’, ’c’, ’t’, ’h’, ’y’, ’i’, ’r’, ’l’, ’s’, ’b’, ’d’, ’f’, ’g’, ’p’, ’q’, ’u’] Marking Rubric: This question will be marked out of 35 for correctness (pass test cases): • 35/35: Pass all 5 of the test cases • 21/35: Pass any 2 (or more) of the test cases • 7/35: Pass any of the test cases3 Submission Instructions (10 points) Please follow these submission instructions carefully. Correctly submitting all files is worth 10 points. In these files, you must replace ccid with your own ccid. Your ccid is the first part of your UAlberta email ([email protected]). Do not zip any of these files. Please submit the following files to eclass: • ccid writtenQuestions.pdf : Your answers to all written questions should be in this one pdf file.• ccid solutionQuestion1.py : Edit the provided file for question 1. After your solution passes all test cases (which you must test using the driver), rename the file to include your ccid, that is, ccid solutionQuestion1.py and submit it to eclass.
An important application of binary trees is to represent the structure of an arithmetic computation. Example Expression Tree: 6 x 3 + (4 – 1) + * 6 3 – 4 1 a) Sketch the following binary expression trees: 1. 3−2 0.5 × ((9 − 5) + 2) − (7 × 3 4 + 9) 2. ( 3 2 ) 5 × (N − M × 2M) − (7 × 12 + 9)b) Explain how the order of operations are executed in terms of the levels in an arithmetic expression tree. Hint: Think of the first and last operations executed in an arithmetic expression tree.Overview: Trees are an important non-linear data structure that allows us to express many different kinds of structural and hierarchical relationships. Although a binary tree is one of the more common types of trees you’d encounter, it is important to note that a tree’s nodes can have an arbitrary number of children.Your task here is simple: given an array-based representation of a general tree, construct a tree from the input using the provided TreeNode class. You will write the function read tree() that will read the general tree from standard input and return the root of the tree as a TreeNode object.The first line of the input will provide n and d. n represents the length of the array-based representation and d represents the maximum degree a node can have. Not all nodes will have d children and so the dash character – represents an empty child.The second line of the input is a list of n space-separated strings that represents the tree as an array. Each string represents a page/node in the tree and the dash character (-) represents an empty child and should be ignored.You will be provided a TreeNode class in a separate file treenode.py. This file will be imported in your solution and its notable methods are: • a = TreeNode(’A’): Constructs a TreeNode with a value of ’A’ and store it in a variable a. • a.get value() returns the value of the node A. • a.get children() returns a list of TreeNode objects that are the children of the node a. • a.add child(child) adds a TreeNode object, child, to the list of a’s children. • a.print tree() prints the tree to standard output. Each line in the output will have the following format: NODE -> CHILDA CHILDB CHILDC …Example Input #1: 12 3 W A B X C – – D E F G H Example Output of read tree().print tree(): W -> A B X A -> C B -> D E F X -> G H Example Tree #1: W A C B D E F X G H Example Input #2: 24 3 W A B C D E – F G H I J – X – – – – – – – – K L Example Output of read tree().print tree(): W -> A B C A -> D E D -> X B -> F G H F -> K L C -> I J Example Tree #2: W A D X E B F K L G H C I J• A node’s value can either be a single character (eg. A) or a sequence of characters (eg. AA, AB). • At least one node will have d children. 2 • Children should be added to a node in the order they appear in the input. • The dash character – indicates an empty child and should not be added as a node. • Do not modify the main() function. • Do not modify the provided treenode.py file. You also do not need to submit the treenode.py file.Marking Rubric: This question will be marked out of 35 for correctness (pass test cases): • 35/35: Pass all 10 of the test cases • 21/35: Pass any 6 (or more) of the test cases • 14/35: Pass any 3 (or more) of the test cases • 7/35: Pass any of the test casesOverview: In this question, your task will be to implement a few methods of the class LinkedList which implements the linked list data structure. Use the existing methods of the LinkedList class to help implement the required methods.You will be provided a LinkedList class. The class includes various methods you to help you complete the assignment: • llist = LinkedList(): Constructs a LinkedList object. Each linked list is constructed of Node() objects.• llist.head returns the pointer to the head node of the linked list. • llist.insertAtBegin(self, data) adds a node to the beginning of the linked list with a value of data. • llist.insertAtIndex(self, data, index) adds a node at index. Indexing starts from 0. • llist.insertAtEnd(self, data) adds a node to the end of the linked list with a value of data. • llist.updateNode(self, val, index) updates the node at index to the value val. • llist.sizeOfLL(self) returns the size of the linked list (number of nodes).You will be provided a Node class. The node class only contains two attributes and no methods. Node objects construct a linked list. • node = Node(): Constructs a Node object. • node.data returns the value stored at the current node. • node.next returns the pointer to the next node in the linked list. Hint: You can create new pointers to nodes of the linked list. For example, current node = self.head will create a new pointer to the head of the linked list object, which you can use to iterate through the linked list.Remove Duplicates Description: Implement the method remove duplicates() that removes all duplicate nodes from a singly linked list while preserving the original order of the first occurrence of each value. A node is considered a duplicate if its value matches any previously seen values in the linked list. Examples: llist = 3 -> 2 -> 0 -> -4 -> 2 result: 3 -> 2 -> 0 -> -4 llist = 1 -> 2 result: 1 -> 2 llist = 6 -> 5 -> 6 -> 7 result: 6 -> 5 -> 7 llist = 1 -> 1 -> 2 result: 1 -> 2 llist = 4 -> 3 -> 2 -> 3 -> 1 -> 2 result: 4 -> 3 -> 2 -> 1• The linked list can contain any number of duplicates • The first occurrence of each duplicate value should be preserved • 1 ≤ len(llist) ≤ 100 • The linked list nodes should remain in the same relative order after duplication removal (i.e., no sorting)• The linked list node values will consist of integers only • You cannot call the Node() constructor or the LinkedList() constructor to instantiate new objects. You must instead create new pointers to nodes in the linked list and reassign pointers in the linked list. • You can create any new methods in the linked list or node class.Merge Description: Implement the method merge(self, llist2) that merges two sorted singly linked lists together. The method must merge the nodes in place. This means that the reversal must be performed within the existing linked list structure without instantiating any new node or linked list objects. The result must add all the nodes from the llist2 object that is passed to the method into the linked list the method is called on. The resulting merged linked list must maintain the sorted order after merging. Examples: 4 llist1 = 1 -> 3 -> 5 llist2 = 2 -> 4 -> 6 Result: 1 -> 2 -> 3 -> 4 -> 5 -> 6 llist1 = 2 llist2 = 1 -> 3 Result: 1 -> 2 -> 3 llist1 = 1 -> 8 llist2 = 1 -> 4 -> 6 Result: 1 -> 1 -> 4 -> 6 -> 8Specifications: • If one list is longer than the other, append the remaining nodes of the longer list at the end. • Both linked lists will have at least one node. • Both linked lists are sorted in ascending order. • Both linked lists only contains integers for their data values. • You cannot call the Node() constructor or the LinkedList() constructor to instantiate new objects. You must instead create new pointers to nodes in the linked list and reassign pointers in the linked list.• You can create any new methods in the linked list or node class.Marking Rubric: This question will be marked out of 35 for correctness (pass test cases): • 35/35: Pass all 20 of the test cases • 21/35: Pass any 15 (or more) of the test cases • 14/35: Pass any 10 (or more) of the test cases • 7/35: Pass any of the test cases 3 Writing and testing your solution For the programming questions, you should edit the provided files and add your solution. You can check your solution by running driver.py. You can see the output of your program in the Output/ folder, and any errors in the Error/ folder.Please do not change the driver file, only edit the solution file. You can run the driver in a terminal as follows (assuming your working directory is the assignment folder): $ cd a s si gnmen t 1 $ cd Que s ti on 1 $ python3 d r i v e r . py All t e s t s p a s sed ! $ Please add your name, student number, ccid, operating system and python version at the top of each solution file by replacing the provided comments.4 Submission Instructions (10 points) Please follow these submission instructions carefully. Correctly submitting all files is worth 10 points. In these files, you must replace ccid with your own ccid. Your ccid is the first part of your UAlberta email ([email protected]). Do not zip any of these files. Please submit the following files to eclass: • ccid writtenQuestions.pdf : Your answers to all written questions should be in this one pdf file.• ccid solutionQuestion1.py : Edit the provided file for question 1. After your solution passes all test cases (which you must test using the driver), rename the file to include your ccid, that is, ccid solutionQuestion1.py and submit it to eclass. • ccid solutionQuestion2.py : Edit the provided file for question 2. After your solution passes all test cases (which you must test using the driver), rename the file to include your ccid, that is, ccid solutionQuestion2.py and submit it to eclass.
Goal: Understand how Binary Trees work; become familiar with tree traversals; practice using recursion. Download binaryTree.py from eClass. This file contains a fully implemented BinaryTree class for you to use with the following exercises. Also download and complete the lab’s worksheet from eClass, in preparation for Exercise 3 below.In this exercise, you will implement three recursive functions: preorder(), postorder() and inorder(), which print out the values of a binary tree using a preorder, postorder and inorder traversal, respectively.In this exercise, you will implement two functions using recursion: findMinKey() and findMaxKey(). The findMinKey() function should return the minimum element of a given binary tree, while the findMaxKey()function should return the maximum one. When the input is an empty tree, both functions should return None. You can assume that the values stored in tree nodes are integers or float numbers (which can be directly compared using , or ==).If all of the elements in a binary tree are unique, then the information from its inorder and preorder traversals can be used to reconstruct that unique binary tree. For example: If we know that the inorder traversal is [3,2,4,1,5] and the preorder traversal is [1,2,3,4,5], then we know that the binary tree should look like:Task 1: Download and complete the practice worksheet on eClass. Task 2: Implement the recursive function buildTree(inOrder, preOrder). Hint: inorder: [3,2,4, 1, 5] left subtree root key right subtreepreorder: [1, 2,3,4, 5] Remember that the first element in a preorder traversal should always be the value of the root node. At the same time, that root value divides the inorder traversal list into two parts: its left subtree and its right subtree. With this knowledge, we can find the start index and end index for each subtree, and then build the subtrees recursively.
Goal: Gain an in-depth understanding of the Selection Sort and Merge Sort algorithms, and practice using recursion. Exercise 0: Download and complete the two sorting practice worksheets on eClass to become more familiar with various sorting algorithms. Practice – Bubble Sort, Selection Sort, Insertion Sort Practice – Merge Sort, Quicksort You do not need to submit these practice sheets, but please be prepared to talk about them if you need help on this lab/topic.Exercise 1: In this exercise, you will implement two sorting algorithms: selection sort and merge sort. Implement both of the algorithms using recursion, and compute their time to sort different lists of data.Task 1: Selection Sort a. Implement a Selection Sort algorithm using recursion to sort a list of numbers in descending order. Start with the file, exercise_1.py, downloaded from eClass. DO NOT RENAME THIS FILE. b. Complete the function recursive_selection_sort() in this file. You may want to define your own additional functions to complete the task, but they must be called inside of recursive_selection_sort(). Your function should sort a list inplace, so it will not need to return the sorted list. c. Test your solution with the tests provided in test_selection_sort.py file. (i.e. just run it.) Make sure your sorting function passes all the tests.Task 2: Merge Sort a. Implement Merge Sort using recursion to sort a list of numbers in descending order. Do this by completing the function recursive_merge_sort()in exercise_1.py. You may want to define your own additional functions to complete the task, but these functions must be called inside recursive_merge_sort(). This function does NOT sort the list in-place, so remember to return the sorted list from the function.b. Test your solution with the tests provided in test_merge_sort.py file. Make sure your sorting function passes all the tests. Once you have successfully completed Task 1 and 2, run the exercise_1.py file. Its __main__ portion compares how long each sort function takes to sort lists of (a) randomly generated integers, (b) ascending integers, and (c) descending integers. This part is already written for you. Which sorting algorithm takes the least amount of time to sort each list? Why? Write your answer as a comment at the top of your exercise_1.py file.Exercise 2: In this exercise, you will sort a list of complex objects. Each object corresponds to a student, with private attributes: id, name, and mark (see file exercise_2.py). A number of Student objects will be created according to data stored in the text file, student_list.txt (provided), where each line of the input file corresponds to information for one student. The newly created Student objects will be stored in a built-in Python list. This list should be sorted according to student marks (ascending order). To accomplish this, you are asked to complete the following tasks:Tasks: Sorting Objects a. Complete the method __lt__(self, anotherStudent) to compare the receiver object with anotherStudent object. Specifically, you will determine if the mark of the receiver object is less than that of anotherStudent. Return either True or False. Note that this is a special method in Python, and will be called when you compare 2 Student objects using the < operator.b. Complete the function, recursive_merge_sort(), which will use recursive Merge Sort to sort a list of Students in ascending order by their mark. You can adapt your implementation of Merge Sort from Exercise 1. Use the < operator to compare two students’ marks for sorting. You may define your own functions to complete the task. However, they may only be called inside of the recursive_merge_sort() function. Remember that this method must return a new list containing the sorted Students because Merge Sort does not sort in-place.Once you have successfully completed these tasks, run exercise_2.py. Its output should look like the following (formatted as one long column, not 2 columns): Original data: – 129246, George Daniel, 89 – 139897, Amir Jahani, 76 – 139256, Sarah Kylo, 90 – 136898, Breanne Lipton, 82 – 140991, Robert George, 95 – 126775, Jeff Anderson, 84 – 136781, Xialing Liu, 86 – 145887, Ali Gendi, 77 – 140775, Mary Simon, 35 – 142886, Georgina Moore, 88 – 149122, Brian Johnson, 42 – 139887, Samuel Picard, 55 Sorted data: – 140775, Mary Simon, 35 – 149122, Brian Johnson, 42 – 139887, Samuel Picard, 55 – 139897, Amir Jahani, 76 – 145887, Ali Gendi, 77 – 136898, Breanne Lipton, 82 – 126775, Jeff Anderson, 84 – 136781, Xialing Liu, 86 – 142886, Georgina Moore, 88 – 129246, George Daniel, 89 – 139256, Sarah Kylo, 90 – 140991, Robert George, 95
Exercise 1: Write a recursive function mylen(some_list) that determines the length of a list, some_list, passed as an argument to this function. Call the function by writing something similar to the following: def main(): alist=[43,76,97,86] print(mylen(alist)) main() Sample Output:NOTES: 1) The function mylen should work with a list containing any kinds of objects. 2) Your function cannot call the built-in Python function len()!Exercise 2: Write a recursive function called intDivision(dividend, divisor) that uses recursive subtraction to find the integer result of dividend/divisor. Call the function by writing something similar to the following: def main(): n = int(input(‘Enter an integer dividend: ‘)) m = int(input(‘Enter an integer divisor: ‘)) print(‘Integer division’, n, ‘//’, m, ‘=’ intDivision(n,m)) main()Sample Output: Enter an integer dividend: 65 Enter an integer divisor: 12 Integer division 65 // 12 = 5NOTES: 1) Your function should verify the validity of the dividend and divisor inputs. Both should be positive integers; the dividend can also be 0, but the divisor cannot. Raise an exception if either of the inputs are invalid.2) HINT : Subtracting the divisor from the dividend will eventually yield a value that is less than the divisor. Knowing this, what should your base case be? OPTIONAL CHALLENGE: modify intDivision so that it can accept and handle negative dividends and divisors as well.Exercise 3: Write a recursive function that computes and returns the sum of digits of an integer. Call the function by writing something similar to the following: def main(): number = int(input(‘Enter a number:’)) print(sumdigits(number)) main() Sample Output: Enter a number: 78411 21NOTE: 1) Your function should raise an exception if the user does not provide a positive integer number.Exercise 4: Write a recursive function that displays the digits of an integer value in reverse order on the console. For example a call to reverseDisplay(12345) should display 54321. Call the function by writing something similar to the following: def main(): number = int(input(‘Enter a number:’)) reverseDisplay(number) main() Sample Output: Enter a number: 73625 52637NOTE: 1) Your function should raise an exception if the user does not provide a positive integer number. Lab continued with Exercise 5 on next page…Exercise 5: Consider the following non-recursive solution of binary search that finds and returns the position of the key in alist, or returns -1 if key is not in the list: def binary_search1(key,alist,lowerBound,upperBound): ”’ Finds and returns the position of key in alist, or returns -1 if key is not in the list – key is the target integer that we are looking for – alist is a list of integers, sorted in DECREASING order – lowerBound is the lowest index of alist – upperBound is the highest index of alist ”’ found = False while (not found and lowerBound alist[guessIndex]): upperBound = guessIndex – 1 else: lowerBound = guessIndex + 1 if (not found): guessIndex = -1 return guessIndex Sample calls to binary_search1: def main(): some_list = [9,7,5,3,1,-2,-8] print(binary_search1(9,some_list,0,len(some_list)-1)) print(binary_search1(-8,some_list,0,len(some_list)-1)) print(binary_search1(4,some_list,0,len(some_list)-1)) main() Sample Output: 0 6 -1Your task is to write a recursive binary search function called binary_search2 that will do the same task that is done by binary_search1 i.e. if binary_search1 in the above sample calls is replaced with binary_search2, it should produce the same output. The parameters for binary_search2 must be same as binary_search1.NOTES: 1) You can assume that the key will always be an integer number. 2) You can assume that alist only contains integers, sorted in decreasing order.
Goal: Learn about singly and doubly-linked lists, and learn to test your methods using assert statements rather than comparing to sample output.Exercise 1: In this task, you will complete the insert(pos, item) method for the singly-linked list. Recall that insert adds a new node (containing the item as its data) at the given position in the list. For example, if pos is 0, then the new node goes at the beginning (head) of the list. pos must be an integer, and for this exercise, cannot be negative.1. Download and save SLinkedList.py from eClass. There are 2 classes in the file: the SLinkedListNode class, and the SLinkedList class. The SLinkedListNode class is already completed for you, based on the implementation in the lecture. The SLinkedList class is partially completed – you must complete the implementation of the insert method, and use the code in the main function to test it.Hints: Think of the different cases you may encounter. What if you try to insert into an empty list? What if you try to insert at the head of a list containing one element, or many elements? What if you try to insert in the middle of a list containing many elements – is that different from inserting at the end? Draw out every unique case to see how to update the links without unintentionally losing elements to the garbage collector. Always leave your list in a consistent state.Sample Output: Original List: 6 elements A->4->2->77->6->Z-> After inserting the word start at position 0: 7 elements start->A->4->2->77->6->Z-> After inserting the word end at position 7: 8 elements start->A->4->2->77->6->Z->end-> After inserting middle at position 4: 9 elements start->A->4->2->middle->77->6->Z->end->Exercise 2: In this task, you will implement the following doubly-linked list methods: search(item) – returns True if the item is an element in the list; False otherwise. The item can be any object. Already completed for you. index(item) – returns the index of the item in the list (assuming that the head node is at index 0), or -1 if the item is not in the list. Already completed for you. insert(pos, item) – adds a new node (containing the item as its data) at the given position in the list. For example, if pos is 0, then the new node goes at the beginning (head) of the list. pos must be an integer, and for this exercise, cannot be negative. searchLarger(item) – returns the position of the first element that is larger than item, or -1 if there is no larger item. getSize() – returns the number of elements in the list. getItem(pos) – returns the item at the given position. An exception should be raised if the position is outside of the list. pos must be an integer, and it can be positive OR negative. __str__ – returns a string of the elements in the doubly-linked list, with one space in between each element.1) Download and save DLinkedList.py from eClass. This file contains the completed DLinkedListNode class, as implemented in the lectures. It also contains the unfinished DLinkedList class. Your task will be to complete and test the methods described above.Things to keep in mind: a) All attributes in DLinkedList should be PRIVATE. b) Tests for each method have been provided for you in DLinkedList.py. Run the tests when you complete EACH method.c) Draw out the linked list structure to help visualize which references need to be updated, and in which order (to prevent the garbage collector from removing unintended objects). Be sure to consider all relevant cases. For example, when removing an item, what happens when that item is in the head node, the tail node, or a middle node? When adding an item, is adding to an empty list the same as adding to a list with a single element already in it? Is it the same as adding to a list with many elements already in it?d) Make sure that the linked list always maintains a consistent state. Optional Exercise (highly recommended, but do not demo): Complete and test the additional methods for the doubly-linked list: add(item) – adds a new node (containing the item as its data) to the head of the list. remove(item) – removes the first element in the list that is equal to item. If the item is not in the list, the list is not changed and an exception should NOT be raised. This is a bit different from the implementation in the lecture. append(item) – adds a new node (containing the item as its data) to the tail of the list. pop1() – removes and returns the last item in the list. pop(pos) – removes and returns the item in the given position. An error should be raised if the position is outside of the list. pos must be an integer, and for this exercise, cannot be negative.
Goal: Learn about inheritance in object-oriented programming, and practice handling exceptions. For a simple tutorial on inheritance in Python, see: https://www.w3schools.com/python/python_inheritance.aspExercise 1: Inheritance is a fundamental concept in object-oriented programming. It allows us to define a new class that has all of the methods and properties of another class – just like a child inherits traits from a parent, the new subclass inherits properties and behaviours from its base class. It is also possible for the new subclass to have new properties and behaviours in addition to those it inherited, or to override some of the inherited properties and/or behaviours with its own unique ones.To create a subclass in Python, you create a new class definition as normal, and then add the name of the base class (the one you want to inherit from) in brackets after the new subclass name. For example, let’s define a Cake class and a BirthdayCake class, where the BirthdayCake class inherits all properties and behaviours from the Cake class and also has a unique behaviour of its own (putting birthday candles on top): class Cake: def __init__(self, flavour, frosted): self.flavour = flavour self.frosted = frosteddef bake(self, temp): print(‘Cake is baking at’, temp, ‘degrees Celsius.’) class BirthdayCake(Cake): def putOnCandles(self, numCandles): if numCandles > 0: print(numCandles, ‘candles lit on cake; ready to be blown out.’)You can create objects that are instances of the BirthdayCake class, just the same way as you do for any class in Python. For example: grandmasCake = BirthdayCake(‘chocolate’, ‘True’) grandmasCake.bake(180) grandmasCake.putOnCandles(90)When an instance of BirthdayCake is created, the flavour and whether it is frosted or not must be specified, just like for any cake. Also like any cake, it should be baked. But not all cakes have candles put on it – just birthday cakes.Every type of exception that we use in Python is a subclass of the built-in Exception class. In this exercise, you will make your own custom exception. 1. Download and save lab5_inheritance.py from eClass. Write a class definition to create a new type of exception. The class name should be TransitionError. a. This class should be a subclass of the Exception class. b. This class should have its own __init__ method to override the init method (and its attributes) that it inherited from the Exception class. This new method will have two parameters (besides the self parameter): beginning and final. Inside the method, you should assign beginning and final to the new attributes previousState and nextState, respectively. Inside the method, you will also create a third new attribute: msg, which is a string explaining that we cannot transition from the previousState to the nextState.c. This class should have a new method called printMsg(). It simply prints the value of the msg attribute.2. Test your TransitionError class by running the main function already written for you in lab5_inheritance.py. What is the difference between the second and third try statement? i.e. why does it print different results? Sample run: Checking first person…Pebbles Flintstone started life as a(n) baby and ended as a(n) adult This is the transition we expect as people grow old Checking second person… Benjamin Button started life as a(n) adult and ended as a(n) baby Transition error: Not normal to transition from adult to baby Checking second person again… General error Goodbye…Exercise 2: You are tasked with writing a program that reads in information about client bank accounts (where all of the clients, luckily, have unique names), and then allows the user to enter transactions (withdrawals or deposits) for any of those accounts. You will need to catch and handle specific exceptions, as described below.1. Create a new file, lab5_accounts.py. In this file, create a main() function that asks the user for the name of the file to read the account data from. If the file does not exist, your main function should handle the resulting OSError exception by printing an error message and exiting the entire program gracefully (i.e. without displaying the call stack and exception information). Sample run when non-existing filename is entered: Enter filename > sillyfile.txt File error: sillyfile.txt does not exist Exiting program…goodbye.If the file exists, main should open the file in read mode and then pass the resulting TextIOWrapper object (i.e. the file handler) as an argument to the readAccounts function (see step 2). The main function should then call the processAccounts function with the appropriate input argument (see step 3).2. Create a function called readAccounts(infile) to read all of the information in the account text file into a dictionary, one line at a time. Each line in the text file should contain a (unique) name, then a greater than symbol (>), then a decimal number representing the account’s opening balance. If the opening balance is not a number, this function should catch the ValueError exception that results when you try to convert a non-number to a float. As part of handling that exception, a warning message should be displayed (see sample run below).After catching the exception, the function should continue on to the next line in the file, without adding anything about the invalid account to the dictionary. Once all of the valid account information has been added to the dictionary, this function should return the dictionary.Sample run for invalid opening balance: Input file example: Bob>234.70 Mike Smith>Not_A_Float! Warning! Account for Mike Smith not added: illegal value for balance3. Create a function called processAccounts(accounts), where the accounts parameter is a dictionary. This function should ask the user to enter the name of a client, and the amount of money to deposit or withdraw from that client’s account. After each successful transaction, the amount of money left in the client’s account should be displayed. If the client name does not exist as a key in the dictionary, the resulting KeyError that is raised when you try to access the key should be handled by this function.For example, if Aladdin is entered by the user, and he is not in the dictionary of clients, the following message would be displayed and the user should be re-prompted to enter another client name: Warning! Account for Aladdin does not exist. Transaction cancelled.Once a valid client name has been entered, the user is asked to enter a transaction amount (positive for deposit, negative for withdrawal). This amount, if valid, will be added to the client’s opening balance and displayed. You should update the value in the dictionary, but you do not need to update the text file. If the user enters a value that cannot be converted to a float number, the resulting ValueError is caught by this function so that the following message is displayed: Warning! Incorrect amount. Transaction cancelled. After successfully handling the error, the function allows the user to continue entering client names and transaction amounts until s/he enters Stop.4. Download and save a copy of accounts.txt from eClass. Test that all exceptions described above are handled properly. Some of those exceptions (but not all) are shown in the sample run below. Sample Run for complete program: Enter filename > accounts.txt Warning! Account for Mike Smith not added: illegal value for balance Warning! Account for George not added: illegal value for balance Enter account name, or ‘Stop’ to exit: bob Warning! Account for bob does not exist. Transaction cancelled Enter account name, or ‘Stop’ to exit: Bob Enter transaction amount for Bob: 30 New balance for account Bob: 264.7 Enter account name, or ‘Stop’ to exit: Zoya Enter transaction amount for Zoya: hello Warning! Incorrect amount. Transaction cancelled Enter account name, or ‘Stop’ to exit: Anna Enter transaction amount for Anna: -20.78 New balance for account Anna: 3239.77 Enter account name, or ‘Stop’ to exit: Bob Enter transaction amount for Bob: 5.05 New balance for account Bob: 269.75 Enter account name, or ‘Stop’ to exit: Stop Exiting program…goodbye.
Goal: Learn about bounded queues and circular queuesExercise 1: 1. Download and save queues.py from eClass. This file contains the implementations for the Bounded Queue and the Circular Queue discussed in the lectures. It also contains the skeleton code for a number of tests to check various aspects of the Bounded Queue’s implementation. Uncomment and run/write the code for each test, one at a time, to check that you get the same sample output as below. Test 1: Complete the try statement. If the Bounded Queue’s dequeue() method is correct, an exception should be raised when you attempt to dequeue from the empty queue, bq. Handle it by printing out the argument of the exception. Change the exception’s argument string in the Bounded Queue’s dequeue() definition and rerun this test – is the new message displayed on the screen now? Test 2: Test the Bounded Queue’s enqueue() method by trying to add ‘bob’ to bq. When printing the contents of bq to the screen, are print(bq) and print(str(bq)) the same? Does the method isEmpty() return the expected result? Test 3: Run given code. When multiple items are added to the queue, does the queue store them in the correct order (test the repr() function)? Do the isFull() and size() methods give the expected results? Test 4: Write a try statement to attempt to add an item to the full bq. If the Bounded Queue’s enqueue() method is correct, it should raise an exception. Handle that exception in the main() by printing out the exception’s argument. Test 5: Run given code. Can an item be removed from a full bounded queue? Does the dequeue() method return the expected item, and are the contents of bq updated? Test 6: Run given code. Test the capacity() method. How is capacity different from size? Test 7: Try to access the private capacity attribute outside of the Bounded Queue class definition (i.e. in the main). What happens? Does the same thing happen if you try to access a non-private attribute outside of its class definition?Sample Output: My bounded queue is: Max=3 Is my bounded queue empty? True ———————————- Try to dequeue an empty bounded queue… Error: Queue is empty ———————————- bob bob Is my bounded queue empty? False ———————————- bob eva paul Max=3 Is my bounded queue full? True There are 3 elements in my bounded queue. ———————————- Try to enqueue a full bounded queue… Error: Queue is full ———————————- eva paul Max=3 bob was first in the bounded queue: eva paul There are 2 elements in my bounded queue. ———————————- Total capacity is: 3Exercise 2: In this task, you will compare the runtime of the dequeue() method in the Bounded Queue with the dequeue() method of the Circular Queue. In the Bounded Queue, the dequeue method removes the item at the front of the queue, and then shifts the remaining items in the list to the left (i.e. to fill in the hole created by removing that first item). For a Bounded Queue containing n items, what is the big-O time efficiency of the dequeue?In the Circular Queue, you just shift the head index when you dequeue an item – no shifting of the actual data elements is required. For a Circular Queue containing n items, what is the big-O time efficiency of the dequeue? Considering your answers to the above two questions, which queue’s dequeue do you predict will run faster?1. Create a new file, lab6.py. In this file, import both the Bounded and Circular Queues from queues.py (downloaded in Exercise 1 above). 2. In a main function, create a Bounded Queue object and enqueue 50,000 items into it. For example, you can enqueue the integers 1 to 50,000. 3. In the same main function, create a Circular Queue object and enqueue the same 50,000 items into it.4. Compute the time required to dequeue all items from the Bounded Queue, using the time module. The time module returns times in seconds. Hint on using the time module: import time start = time.time() # The statement(s) that you want to test end = time.time() time_interval = end – start5. Similarly, compute the time required to dequeue all items from the Circular Queue. 6. Print the dequeue() runtime for each queue to the screen, as shown in the sample output below.Sample Output For Bounded Queue, the total runtime of dequeuing 50,000 items is: 0.1325376033782959 seconds. For Circular Queue, the total runtime of dequeuing 50,000 items is: 0.042598724365234375 seconds.**NOTE** We need to enqueue many items in the Circular and Bounded Queues in order to get large enough runtimes to measure for both queues. If the runtime is too short, we will just see zeros returned as the runtime for both. Moreover, keep in mind that the actual runtime will be different on different computers, and slightly different between runs. How would you modify your code to find the average runtime of 5 trials each?7. Repeat steps 2-6, but for larger values of n. For example, n = 55,000 and then n= 60,000 and so on up to about n = 300,000. Copy your times for the different n values into a program like google sheets or excel to plot the time vs n for both the Bounded Queue and Circular Queue. Which plot is linear and which is quadratic – why? Do not run step 7 during your demo, but be prepared to show your plot to your TA during the demo.Challenge Exercise: (Optional extra practice) Write a program to simulate two waiting queues at a grocery store. One queue line is for normal customers, and the other line is for VIP customers. Normal customers can only wait in the Normal customers’ queue, and VIP customers can only wait in the VIP customers’ queue.Your program should start by asking the user if they want to add a customer to the queue, serve the next customer in the queue, or exit. If the user chooses to add a customer, the program asks the user to enter the name of the customer, followed by whether or not the customer is a VIP. If the customer is a VIP, then the customer’s name is added to the VIP queue; otherwise, the customer’s name is added to the Normal queue. After EACH add operation, the program prints the customer’s name and the queue (Normal or VIP) that the customer has been added to. The program also prints both queues after EACH add operation.After the add operation is completed, the user is asked to enter Add, Serve, or Exit again. Your program will continue to prompt the user repeatedly with these options and perform the task associated with these operations until the user enters Exit. Here is a partial sample output of the program that shows what is displayed after the add operation: Add, Serve, or Exit: Add Enter the name of the person to add: Fred Is the customer VIP? True Add Fred to the VIP line. Normal customers queue: ]] VIP customers queue: ]Fred] Add, Serve, or Exit: Add Enter the name of the person to add: Bob Is the customer VIP? False Add Bob to the normal line. Normal customers queue: ]Bob] VIP customers queue: ]Fred]If the user chooses to serve a customer, the program will check the VIP Queue first. If the VIP Queue is not empty, the customer at the front of the VIP queue will be served first. If the VIP Queue is empty, then the customer at the front of the Normal queue is served. After the serve operation, the program will print the name of the customer who has been served and the content of each queue.Here is a partial output from the program that shows what is displayed after the serve operation: Add, Serve, or Exit: Serve Fred has been served. Normal customers queue: ]Bob] VIP customers queue: ]] If the user wants to add a customer to a queue (Normal or VIP) that is full, the program should print one of the following error messages: Error: Normal customers queue is full or Error: VIP customers queue is full After such error messages are displayed, the program should continue to ask the user if they wish to Add, Serve, or Exit. If both Normal and VIP Queues are empty, and if the user requests a serve from the queue, then the program should print the following error message: Error: Queues are empty After the error message is displayed, the program should continue to ask the user if they wish to Add, Serve, or Exit.If the user enters the word Exit, the program should end by printing the word Quitting. Please note the following: You may restrict the capacity of each queue to 3 to simplify testing. You should try your code with a Bounded Queue first, and then (once your program is working) swap it out for the Circular Queue. Did you need to change your program at all? Sample Output: Add, Serve, or Exit: Add Enter the name of the person to add: Fred Is the customer VIP? True Add Fred to VIP line. Normal customers queue: ]] VIP customers queue: ]Fred] Add, Serve, or Exit: Add Enter the name of the person to add: Barney Is the customer VIP? False Add Barney to the normal line. Normal customers queue: ]Barney] VIP customers queue: ]Fred] Add, Serve, or Exit: Add Enter the name of the person to add: Wilma Is the customer VIP? False Add Wilma to the normal line. Normal customers queue: ]Barney,Wilma] VIP customers queue: ]Fred] Add, Serve, or Exit: Add Enter the name of the person to add: Pebbles Is the customer VIP? False Add Pebbles to the normal line. Normal customers queue: ]Barney,Wilma,Pebbles] VIP customers queue: ]Fred] Add, Serve, or Exit: Add Enter the name of the person to add: Flint Is the customer VIP? False Error: Normal customers queue is full Normal customers queue: ]Barney,Wilma,Pebbles] VIP customers queue: ]Fred] Add, Serve, or Exit: Serve Fred has been served. Normal customers queue: ]Barney,Wilma,Pebbles] VIP customers queue: ]] Add, Serve, or Exit: Serve Barney has been served. Normal customers queue: ]Wilma,Pebbles] VIP customers queue: ]] Add, Serve, or Exit: Serve Wilma has been served. Normal customers queue: ]Pebbles] VIP customers queue: ]] Add, Serve, or Exit: Serve Pebbles has been served. Normal customers queue: ]] VIP customers queue: ]] Add, Serve, or Exit: Serve Error: Queues are empty Normal customers queue: ]] VIP customers queue: ]] Add, Serve, or Exit: Exit Quitting
Goal: Become familiar with a new data structure: Stack. Exercise 1: You are tasked with creating a web browser simulator. Your web browser simulator should use two stacks: one to enable the back button functionality, and one to enable the forward button functionality. Your simulator will not actually display any webpages, but just the URL address of the current page that the user is on. (See sample run at the end of this exercise.) When the user wishes to enter a new webpage address, s/he signals this by entering ‘=’. When the user wishes to go back, ‘’ is entered. The user can quit by entering ‘q’ when prompted.1. Complete the worksheet at the end of this lab to show the contents of the back Stack and forward Stack after every valid entry in the sample output. DO NOT submit your worksheet on eClass, but be prepared to show this to your TA during any help or demo sessions.2. Download and save stack.py from eClass. This file contains implementation #2 of the Stack covered in the lectures. DO NOT modify or submit stack.py. 3. Download and save a copy of lab4_browser.py from eClass. (Be sure that you save it in the same directory as stack.py.) This file contains a COMPLETED main() function which controls the flow of operation of a web browser simulation. In the following steps, you will complete the functions that this main() function calls.4. Complete getAction(). This function prompts the user to enter either a ‘=’ (to enter a new website address), ‘’ (forward button), or ‘q’ to quit the browser simulation. If the user enters something other than these 4 characters, an error message is displayed before re-prompting for a valid entry. This function has no inputs. This function returns the valid character entered by the user (str). *Reminder: Be sure to write a docstring for each of your functions.5. Complete goToNewSite(). This function is called when the user enters ‘=’ during getAction(). This function prompts the user to enter a new website address, and returns that address as a string. It also updates the two stacks, as appropriate. (Hint: experiment with how the back and forward buttons work on a real web browser like Firefox or Chrome. After a new address is entered, can you still go forward?) Note that you do not need to explicitly return the two stacks because the Stack (as we implemented it) is a mutable object – so bck and fwd are actually just aliases for the stacks called back and forward in your main function. The inputs for this function are the current website (str), a reference to the Stack holding the webpage addresses to go back to, and a reference to the Stack holding the webpage addresses to go forward to.6. Complete goBack(). This function is called when the user enters ‘’ during getAction(). An error message is displayed if there are no webpages stored in the forward history, and the current site is returned (str). Otherwise, the next website is retrieved (and returned as a string), and the two stacks are updated as appropriate. The inputs for this function are the current website (str), a reference to the Stack holding the webpage addresses to go back to, and a reference to the Stack holding the webpage addresses to go forward to.Sample run: Currently viewing www.cs.ualberta.ca Enter = to enter a URL, < to go back, > to go forward, q to quit: 123 Invalid entry. Enter = to enter a URL, < to go back, > to go forward, q to quit: > Cannot go forward. Currently viewing www.cs.ualberta.ca Enter = to enter a URL, < to go back, > to go forward, q to quit: to go forward, q to quit: = URL: www.google.ca Currently viewing www.google.ca Enter = to enter a URL, < to go back, > to go forward, q to quit: to go forward, q to quit: > Currently viewing www.google.ca Enter = to enter a URL, < to go back, > to go forward, q to quit: = URL: docs.python.org Currently viewing docs.python.org Enter = to enter a URL, < to go back, > to go forward, q to quit: to go forward, q to quit: to go forward, q to quit: = URL: www.beartracks.ualberta.ca Currently viewing www.beartracks.ualberta.ca Enter = to enter a URL, < to go back, > to go forward, q to quit: > Cannot go forward. Currently viewing www.beartracks.ualberta.ca Enter = to enter a URL, < to go back, > to go forward, q to quit: to go forward, q to quit: > Currently viewing www.beartracks.ualberta.ca Enter = to enter a URL, < to go back, > to go forward, q to quit: q Browser closing…goodbye.Worksheet to Match Sample Run: The first 3 steps are already done to get you started… Step 1: Web browser opened; home page displayed current back forward Cannot go forward, cannot go back. No change to current. Step 2: Go to new site; www.google.ca displayed current back forward Step 3: Go back to previous page; www.cs.ualberta.ca displayed current back forward Complete the rest (draw extra boxes for Stack elements if needed)… Step 4: Go forward to next page; www.google.ca displayed current back forward www.cs.ualberta.ca www.google.ca www.cs.ualberta.ca www.google.ca www.cs.ualberta.ca (empty) (empty) (empty) (empty) www.google.ca Step 5: Go to new site; docs.python.org displayed current back forward Step 6: Go back to previous page; www.google.ca displayed current back forward Step 7: Go back to previous page; www.cs.ualberta.ca displayed current back forwardStep 8: Go to new site; www.beartracks.ualberta.ca displayed current back forward Step 9: Try to go forward, but can’t; www.beartracks.ualberta.ca displayed current back forward docs.python.org www.google.ca www.cs.ualberta.ca www.beartracks.ualberta.ca www.beartracks.ualberta.ca Step 10: Go back to previous page; www.cs.ualberta.ca displayed current back forwardStep 11: Go forward to next page; www.beartracks.ualberta.ca displayed current back forward www.cs.ualberta.ca www.beartracks.ualberta.ca
Goal: Review classes/objects, importA magic square is an n by n grid of cells filled with unique positive integers (all greater than 0) arranged so that all lines in the square (horizontals, verticals, diagonals) add up to the same sum.For example, these are magic squares: 10 3 8 5 7 9 6 11 4 But these are NOT magic squares: 10 13 8 5 7 9 6 11 4A colleague has written a program to read in data for various squares to check if they are magic squares. She wrote it assuming that there was a MagicSquare class that has the methods described in Part 1 below. However, that class isn’t finished yet: drawSquare and isMagic are incomplete. It is up to you to finish the class and test it all, so that an instance of it can then be used in your colleague’s program.Part 1: Download and save a copy of lab3_MagicSquare.py. This file contains the skeleton code for a class called MagicSquare, which you will complete. 1. The __init__(self, n) method has been completed for you. Notice that this method initializes two attributes: square and size. The size attribute defines how many rows (and columns) are in the square. The square attribute represents a square with n*n empty cells – it is a list of 16 3 2 13 5 10 11 8 9 6 7 12 4 15 14 1 10 10 8 5 7 9 6 11 4 10 8 5 7 9 6 11 4 21 21 21 21 21 21 21 21 21 31 21 21 21 31 21 21 34 34 34 34 34 34 34 34 34 34 Square is not complete (one cell is not filled). Cell contents are not unique (notice 10 is present twice).lists, where each internal list represents a row in the square. The value 0 is used to represent an empty square. Run the test provided (i.e. by running lab3_MagicSquare.py) to test this method before moving on: self.square should be [[0, 0, 0], [0, 0, 0], [0, 0, 0]]2. The cellIsEmpty(row, col) method has been completed for you. This method checks the contents of the square at the given row index (integer) and column index (integer). If the cell at that square is “empty”, the method returns True. Otherwise, the method returns False. Test this method before moving on. You can pick any cell in the 3×3 test square.3. Complete the drawSquare method so that it displays the current contents of the square, along with the column indices on top of the square, and the row indices to the left of the square. If the content of a given cell is 0, a period (‘.’) should be displayed.To simplify the formatting, you can assume that only the digits 1-99 can be used as values in the cells, and you should center the contents of each cell in a field width of 4 places (see sample output below). You may also assume that the biggest square that will be tested is 10*10, so you only need to worry about single digit indices. Test your method before moving on: When self.square is [[0, 0, 0], [0, 0, 0], [0, 0, 0]], the following should be printed:0 1 2 +————–+ 0 | . | . | . | +————–+ 1 | . | . | . | +————–+ 2 | . | . | . | +————–+4. The update(row, col, num) method has been completed for you. This method checks if the cell at the provided row index (integer) and column index (integer) is “empty”. This method also checks that num (integer) does not already exist in another cell in the square. If both of these conditions are met, the contents of the cell are updated to hold the unique num, and the method returns True. If the cell is not empty or the number already exists in another cell, the contents of the cell are not changed, and the method returns False. Test this method before moving on by inserting a 10 in row 0, column 0 (just like in the first diagram at the beginning of this lab description). What happens when you try to enter a new number in that same cell?5. The isFull() method has been completed for you. This method returns True if there are no “empty” cells, False otherwise. Test this method. Which cases should you consider? 6. Complete the isMagic() method. This method returns True if the square is complete, only contains unique numbers, and all lines sum up to the same value. Otherwise, it returns False. Test this method. Which cases should you consider? Demo your completed class to your TA, along with your tests. Be ready to explain which aspects you tested and why.Part 2: 1. Once you have fully tested your MagicSquare class, download your colleague’s program (lab3.py) from eClass and save it in the same folder as your lab3_MagicSquare.py. Also download and save all of the square_i.txt files in the same folder. Run lab3.py. *Notice that all of the testing code that you included under if __name__ == ‘__main__’: in lab3_MagicSquare.py does not execute when you run lab3.py.Sample Output for Part 2: Reading from square_1.txt… 0 1 2 3 +——————-+ 0 | 16 | 3 | 2 | 13 | +——————-+ 1 | 5 | 10 | 11 | 8 | +——————-+ 2 | 9 | 6 | 7 | 12 | +——————-+ 3 | 4 | 15 | 14 | 1 | +——————-+ This square is MAGIC ========================= Reading from square_2.txt… 0 1 2 +————–+ 0 | 2 | 7 | 6 | +————–+ 1 | 9 | 5 | 1 | +————–+ 2 | 4 | 3 | 8 | +————–+ This square is MAGIC ========================= Reading from square_3.txt… 0 1 2 3 4 +————————+ 0 | 17 | 24 | 1 | 8 | 15 | +————————+ 1 | 23 | 5 | 7 | 14 | 16 | +————————+ 2 | 4 | 6 | 13 | 20 | 22 | +————————+ 3 | 10 | 12 | 19 | 21 | 3 | +————————+ 4 | 11 | 18 | 25 | 2 | 9 | +————————+ This square is MAGIC ========================= Reading from square_4.txt… 0 1 2 3 4 +————————+ 0 | 17 | . | 1 | 8 | 15 | +————————+ 1 | 23 | 5 | 7 | 14 | 16 | +————————+ 2 | 4 | 6 | 13 | 20 | 22 | +————————+ 3 | 10 | 12 | 19 | 21 | 3 | +————————+ 4 | 11 | 18 | 25 | 2 | 9 | +————————+ Nothing magic about this square ========================= Reading from square_5.txt… 0 1 2 +————–+ 0 | 2 | 7 | 6 | +————–+ 1 | 9 | 5 | 1 | +————–+ 2 | 4 | 3 | . | +————–+ Nothing magic about this square ========================= Reading from square_6.txt… 0 1 +———+ 0 | 3 | 6 | +———+ 1 | 9 | 4 | +———+ Nothing magic about this square =========================
Goal: Review file I/O, basic input data validation, and defining functions that return values. Learn how to include docstrings for each function you write. Learn about another encryption method, and more about the Unicode table.Useful functions: chr(), ord() * Note: you don’t need to use these functions in your solution, but you may still be asked how they work during your demo. Look up details about how to use chr() and ord() in the Python 3 online documentation: https://docs.python.org/3/index.html. Look up the Unicode table: https://unicode-table.com/en/ Look up examples of Python docstrings: https://www.geeksforgeeks.org/python-docstrings/The Caesar cipher is a simple encryption method that works by substituting each letter in a word (or message) with a letter that is a specific number of letters ahead of it in the alphabet. That specific number is called the cipher key, and both the encrypter and decrypter must know the value of the cipher key in order to successfully exchange secret (encoded) messages.Example: If the cipher key is 5, then the letter ‘a’ in a clear message will be encoded as the letter ‘f’ in the encrypted message. Using the same cipher key, the letter ‘v’ in a clear message will be encoded as the letter ‘a’ (because we wrap around to the beginning of the alphabet when we reach the end).In order to decrypt a message encoded with a Caesar cipher, simply perform the encryption process in reverse. Example: If the cipher key is 5, then the letter ‘a’ in the encoded message becomes the letter ‘v’ in the decoded message. For more details about the Caesar cipher, please watch the optional online video “Encryption & Public Keys Explained”: https://www.youtube.com/watch?v=mEFko9nf5UUIn this lab, you will create a new Python program (lab2.py). In that program, you will ask the user for the name of a text file. You should check that this file ends with a “.txt” extension. If it does not, print an error message on the screen and continue to ask the user for the name of a text file until a valid one is provided. This is the only validation you need to do for the file name – you can assume that the .txt file exists in the same directory as your Python file. This should all be done in a function called getInputFile(), which returns the valid name of the text file as a string.When provided with a valid text file name, you can assume that the file will contain exactly two lines. The first line will consist of a positive integer: this is the cipher key. The second line will consist of a series of encrypted words, where each word is encoded using the Caesar cipher described above. You are tasked with decrypting the message, and printing the clear message (all in lower case letters) to the screen. For example, if you have a cipher key of 1, the encrypted message IfmmP XpsMe becomes hello world. This should all be done in a function called decrypt(filename).Things to keep in mind: 1. Both lines in the text file may or may not have leading and/or trailing whitespace that you should strip away before processing the data. 2. There are an unknown number of encrypted words in the text file, and these words are separated by inconsistent whitespace (e.g. tabs, single space, multiple spaces). Your decrypted message should separate each word by a single space. You can include a single space after the last word in your decrypted message.3. You can assume that the encrypted words will only contain letters (i.e. no numbers, punctuation, or symbols), but these letters could be uppercase or lowercase. Your decrypted message should only contain lowercase letters. 4. The cipher key can be greater than 26.5. Letters should wrap around, so that if you have a cipher key of 1, the encrypted message qjaab becomes pizza.Be sure to include a docstring at the top of each of your function definitions. In Python, docstrings are located on the line directly after def function_name(param1, …): and is indented one level. The docstring may be one line or many lines, but must be enclosed by triple quotes (“””). Each docstring should describe the purpose of the function, the function parameters, and what the function returns. Test your docstrings by calling help(getInputFile) and help(decrypt) in your main function.Partial Sample Run 1 (does not show output from help calls): Enter the input filename: secretMessage1 Invalid filename extension. Please re-enter the input filename: secretMessage1.jpg Invalid filename extension. Please re-enter the input filename: secretMessage1.txtThe decrypted message is: congratulations Partial Sample Run 2 (does not show output from help calls): Enter the input filename: secretMessage2.txt The decrypted message is: i came i saw i conqueredTesting: Download the files called secretMessage1.txt and secretMessage2.txt from eClass, and save it in the same directory as your lab2.py. When you test your code using these files, your output should match what is shown in the above sample runs. However, the sample runs only test some of the functionality of your getInputFile and decrypt functions. Once you are satisfied that your program meets these minimum requirements, modify these files or create your own text files to test all 5 points under “things to keep in mind.” Try to be efficient in your testing (i.e. don’t test the same thing multiple times unless you’re testing it in a different way), and consider any “edge” cases. DO NOT submit your .txt test files on eClass, but be prepared to show them to your TA during your demo.Challenge Problem (optional – not for marks, but may help with future exercises): Once you’ve created (and tested) your getInputFile and decrypt functions, try writing an encrypt() function. This function will ask the user for the name of a text file – this file may or may not exist yet, but it must have a “.txt” extension. If the file already exists, the contents of it will be overwritten during the encryption; otherwise, a new file will be created. The user should be asked to enter a message that s/he would like to be encrypted – this message may consist of multiple words, but you can assume that it only consists of letters and spaces (i.e. no numbers, punctuation, or special characters). The user will then be asked to provide a cipher key.Your program should validate that the user has entered an integer number for this key. (Hint: lookup string methods isalpha(), isalnum(), isdecimal(), isdigit(), and isnumeric() – can you use any of those to help?) If it is not a whole number, an error message should be printed, and the user should be re-prompted to enter a valid integer cipher key. Finally, encrypt() should encode the entered message using the Caesar cipher method and the entered cipher key. The cipher key should be printed to line 1 of the text file, and the encoded message should be printed in all CAPITAL letters to line 2 of the text file.You may want to create additional functions to support your encrypt function. You can also rename/modify functions that you created in the non-optional decryption part of this lab, if appropriate – just be sure to test any changes you make to ensure that your decryption still works.
Goal: Review the properties and methods associated with Python lists, tuples, and sets. Review dictionaries, string formatting. Useful list methods/operators: append(), count(), index(), insert(), pop(), remove(), sort(), in, + Useful tuple methods/operators: index(), in, + Useful set methods/operators: add(), discard(), remove(), &, | Useful dictionary methods: items(), keys(), values() Useful string methods and operators: format(), lower(), upper(), [:] There are many more methods, operators, and functions that you can look up in the lecture slides or in the Python 3 online documentation: https://docs.python.org/3/index.html Another reference that may be helpful for understanding how to use format() is: https://www.programiz.com/python-programming/methods/string/formatExercise 1 Problem: Given a list of integers, follow the steps below to remove all occurrences of the smallest odd number from it. In the process, gain a deeper understanding of whether a list is mutable or immutable, and gain practice manipulating lists in Python. 1. Create a new Python file (lab1.py). In that file, create the following list: numbers = [11, 25, 32, 4, 67, 18, 50, 11, 4, 11]2. Create an empty list, oddNumbers. Print the identity and contents of this list to the screen. (Hint: Look up how id(object) works in the Python 3 online documentation.) 3. Write a loop that finds all of the odd integers in numbers, and appends each odd integer to oddNumbers. (Hint: can you use the modulo operator to determine if an integer is odd?) Once finished, print the identity and contents of oddNumbers to the screen. Has the identity of oddNumbers changed? Is a Python list mutable or immutable?4. Sort oddNumbers in descending (decreasing) order. Once sorted, use the pop method to remove the smallest and largest odd integers from oddNumbers. (Hint: where are the smallest and largest numbers in the sorted list?) Print the values of the smallest and largest numbers to the screen; also print the identity and contents of oddNumbers to the screen.5. Print the length of numbers to the screen. Remove all occurrences of the smallest odd number from numbers. (Hint: use the value you found in step 4 above.) Print the new contents and length of numbers to the screen.Exercise 1: Sample Output (your object IDs will be different) The contents of object 55986456 are [] The contents of object 55986456 have been updated to [11, 25, 67, 11, 11] The smallest odd number, 11, has been removed from the list of odd numbers. The largest odd number, 67, has been removed from the list of odd numbers. The contents of object 55986456 have been updated to [25, 11, 11] There are 10 numbers in the original list. After removing the smallest odd number, there are 7 numbers in the list: [25, 32, 4, 67, 18, 50, 4]Exercise 2 Problem: Follow the steps below to create a program that determines the amount of precipitation that fell in Edmonton in a user-specified month in 2020. In the process, practice working with tuples, and gain a deeper understanding of whether a tuple is mutable or immutable. 1. Create the following tuple: months = (‘JAN’, ‘FEB’, ‘MAR’, ‘APR’, ‘MAY’, ‘JUN’, ‘JUL’, ‘AUG’, ‘SEP’, ‘OCT’) Print the identity and contents of this tuple to the screen. 2. Add the tuple (‘NOV’, ‘DEC’) to months. Print the identity and content of months to the screen. Has the identity of months changed? Is a Python tuple mutable or immutable?3. Create the following list, which contains the monthly amounts of precipitation (in mm) that fell in Edmonton in 2020, ordered by month (i.e. 15.5mm fell in Jan, 24.8mm fell in Dec): precipitation2020 = [15.5, 12.1, 18.5, 15.6, 10.7, 62.2, 41.4, 58.3, 15.7, 15.3, 24.8]4. The precipitation amount for July was accidentally left out of the above list. Insert its value (67.8mm) at index 6. (Hint: use the list’s insert method to do this.) The precipitation amounts in precipitation2020 should now align with the months in months (i.e. the data is what we call parallel).5. Find the index (i.e. position) that ‘MAY’ is at in months. Using the same index number, look up and print the amount of precipitation that fell in May 2020 to the screen. We can do this because we’ve manually arranged our data in our tuple and list to be parallel. What would happen if we sorted the precipitation so that it was in ascending order (don’t actually do this) – would the parallel relationship between the tuple and list still exist? Are these parallel containers the best way to form relationship pairs, or is there another built-in Python data structure that would be better to use?6. Ask the user to enter the name of a month. If the user’s entry matches one of the strings in months exactly, print the amount of precipitation that fell in that month to the screen. Otherwise, tell the user that you cannot find information for the month entered.Exercise 2: Sample Output The contents of object 70948160 are (‘JAN’, ‘FEB’, ‘MAR’, ‘APR’, ‘MAY’, ‘JUN’, ‘JUL’, ‘AUG’, ‘SEP’, ‘OCT’) The contents of object 62484192 are (‘JAN’, ‘FEB’, ‘MAR’, ‘APR’, ‘MAY’, ‘JUN’, ‘JUL’, ‘AUG’, ‘SEP’, ‘OCT’, ‘NOV’, ‘DEC’) 10.7mm fell in May 2020. Please enter a month: JUL 67.8mm fell in JUL 2020.Exercise 3 Problem: Pets R Us has asked you to create a program that helps customers with their purchase decision. Follow the steps below to compare the store’s inventory against the pets which a customer wishes to buy. In the process, practice using sets, and test whether sets are immutable or mutable. 1. Create the following set of animals sold in Pets R Us: animals = {‘dog’, ‘cat’, ‘fish’, ‘snake’} Print the identity and contents of this set to the screen. Do the contents print in the expected order? Do you think that they will always print in this order, even on other computers? 2. Pets R Us has decided to stop selling snakes, and sell birds instead. Update animals to reflect this. Once updated, print the identity and contents of animals to the screen. Has the identity of animals changed? Is a Python set mutable or immutable?3. Alice is interested in buying either a dog, a cat, a rabbit, or a hamster. Create a set to represent the pets that Alice would like. 4. Find the intersection of pets between the ones that the store sells and the ones that Alice would like to buy. Print that set to the screen.Exercise 3: Sample Output The contents of object 51131256 are {‘fish’, ‘cat’, ‘snake’, ‘dog’} The contents of object 51131256 are {‘fish’, ‘cat’, ‘bird’, ‘dog’} Alice could buy {‘cat’, ‘dog’} from Pets R Us.Exercise 4 Problem: Follow the steps below to create a program for Bluebell Greenhouses that prints a purchase receipt. In the process, practice using dictionaries and formatting strings. 1. Bluebell Greenhouses sells the following Spring flower bulbs:Flower Bulb Name Price Per Bulb daffodil $ 0.35 tulip $ 0.33 crocus $ 0.25 hyacinth $ 0.75 bluebell $ 0.50 Create a dictionary that stores this information: bulbsForSale = {‘daffodil’: 0.35, ‘tulip’: 0.33, ‘crocus’: 0.25, ‘hyacinth’: 0.75, ‘bluebell’: 0.50}2. Mary has a standing order with Bluebell Greenhouses for 50 daffodil bulbs and 100 tulip bulbs every year. Create a new dictionary that stores information about Mary’s order. Which data should be the keys (must be unique), and which should be the values?3. Demand for tulips this year has dramatically outpaced demand. As a result, the price of tulip bulbs has increased by 25%. Update the price of tulip bulbs in the appropriate dictionary. (Have your program calculate this and round the price per bulb to 2 decimal places. Do not calculate yourself and hardcode the new value in.)4. This year, Mary would also like to try planting hyacinths. Add 30 hyacinth bulbs to the dictionary that is storing her order. 5. Display Mary’s purchase order for this year on the screen. Each line should be formatted as follows: bulb code * number of bulbs = $ subtotal field width: 5 field width: 4 field width: 6 left-aligned right-aligned right-aligned 2 decimal placesThe code for each bulb name is the first three letters of its name, all in capital letters. The lines should be printed so that the bulb codes are in alphabetical order.6. Calculate the total number of bulbs that Mary purchased this year, as well as the total cost of her order. Include this information at the bottom of her purchase order. Format the total cost float value so that it is right-aligned in a field width of 6, with 2 decimal places.single space Exercise 4: Sample Output You have purchased the following bulbs: DAF * 50 = $ 17.50 HYA * 30 = $ 22.50 TUL * 100 = $ 41.00 Thank you for purchasing 180 bulbs from Bluebell Greenhouses. Your total comes to $ 81.00.
Part 1: In this first part of the assignment, you will implement an enrollment table to store the data for students registering in a course. The maximum capacity for the course is 50 students. The maximum number of slots in the table is 51 but no more students than 50 will be added to the table at any time. You will implement and test the following two classes to register the first 50 students in the course by adding their records to the enrollment table. These classes are: StudentNode class and EnrollTable class that you will put in enrollStudent.py.StudentNode class The StudentNode class should have the following method: StudentNode(id, faculty, first, last) – creates a new student node instance. The __init__ method takes four strings as input parameters: the student id, faculty, first name, and last name. You will also implement setter and getter methods as follows – setID(id) – sets the student id to the given id. setFac(faculty) – sets the faculty abbreviation to the given faculty. setFirstName(first) – sets the student’s first name to the given first name. setLastName(last) – sets the student’s last name to the given last name. setNext(next) – sets next as the next node. setPrev(previous) – sets previous as the previous node. getID() – returns the student id as a string. getFac() – returns the faculty abbreviation as a string. getFirstName() – returns a string representing the student’s first name. getLastName() – returns a string representing the student’s last name. getNext() – returns the next node. getPrev() – returns the previous node.The enrollment table will be implemented as a python list with references to a singly linked chain off each of its slots. Its maximum capacity is 51. The enrollment table is initially empty with the references to the singly linked chains initially set to None when no students are enrolled yet in the course. An example of how this data structure looks like is provided in the picture below except that the nodes of the singly linked chains are not showing the student node data but only showing an item inside them; they show however the links to the next nodes. Links to previous nodes in StudentNode instances should be set to None. Also, the maximum capacity of the table in the below example is not shown while the data structure that you will implement has a maximum capacity of 51.EnrollTable(capacity) – creates a new empty enrollment table, basically a python list with a number of slots equal to the given capacity, and each slot is initialized to None. The table size should be set to 0. To compute the index of the table slot in which a new student node object will be inserted, you will implement the following method: cmputIndex(studentID) – this method takes a given student id string as a parameter and returns an integer that will represent the index in which a new student node will be inserted in the enrollment table.This method will split the student id string such that each two characters in the string represent one number made up of two digits. Since each id is made up of six digits, there will be three numbers which the method will sum up after squaring the third number. For example, if the student id is the string “123456”, the method will split the string into 3 two-digit numbers, raise the last number to the power of 2, and then sum up these three values as follows: 12 + 34 + (56)2 . The sum of these is 3182. The method then returns the remainder of the division of the sum by the maximum table capacity, i.e., sum % capacity.In this example with student id “123456”, the method will return 3182 % 51 = 20. So, 20 will be the index in which the new student node will be inserted in the enrollment table. Note: it is possible that the way this index is computed can result in a scenario in which many student nodes will be inserted at the same index in the enrollment table while some slots in the table might remain empty with a reference to None, as shown in the table example above in the picture.insert(item) – this method inserts a given item, a student node object, in the enrollment table. This method does not return anything. To determine where to insert a new student in the table, this method will first call the cmputIndex() method to compute the index of the table slot in which the given item can be inserted. The insert() method will then traverse the singly linked chain referenced at the table slot with this index and insert the new student node in the singly linked chain in ascending order by student id starting from the head of the singly linked chain, if the linked chain is not empty. But if the chain is empty, this new student node will be added as the first node in the chain. Once the new student node is inserted in the table, the table size is incremented by 1.remove(studentID) – this method removes from the enrollment table the node for the relevant student corresponding with the given student id. This method is called when a student drops out from the course. This method should first call the cmputIndex() method to compute the index of the table slot where the given student data may be found. This method will then traverse the singly linked chain referenced from this table slot at this index to find and remove the node for the given student id. This method returns True if the student has been successfully dropped from the course or False otherwise. Once the student node with the given studentID has been removed from the table, the table size is decremented by 1.isEnrolled(studentID) – this method searches the enrollment table given a student id, and returns True if the corresponding student is found in the table, and False otherwise. This method should first call the cmputIndex() method to compute the index of the table in which the student with the given id may be found. If no singly linked chain is referenced off this table index, the method should return False. Otherwise, the method should traverse the singly linked chain referenced by the table slot at this index.Considering that the chains are sorted by ascending order of student id, the linear search should stop once this student id is found or once a student id larger than the given id is found in the chain. In the latter scenario, it means that the student with the given id is not found and the method will return False. size() – this method returns the size of the enrollment table.isEmpty() – this method returns True if the table is empty, i.e., size is 0, and False otherwise. __str__() – returns the string representation of the enrollment table. The printout of the table contents should be between square brackets, separated by commas, and includes the index in which a record is stored and the student id, faculty and first and last names. Multiple records at the same index in the enrollment table can be printed following this index and separated by commas.In this second part of the assignment, you will implement and test a priority queue for students that want to register in the course after the course has reached its maximum enrollment capacity. These students will be placed in a priority queue based on the faculty they are registered in.Create and test a PriorityQueue class in enrollStudent.py. You will implement this priority queue using a doubly linked chain data structure. The highest priority nodes will be dequeued from the front of the queue and the lowest priority nodes will be enqueued to the rear of the queue.Priority is based on the student’s faculty. Students with the highest priority are dequeued from the front of the queue. Faculty names and their corresponding priority values can be stored as key-value pairs in a Python dictionary. The priority is represented with an integer number and the faculty abbreviation as a string in the dictionary. The priority can be looked up based on the faculty abbreviation and ranges from 0 to 4, with 4 being the highest priority and 0 being the lowest priority.The faculties are SCI, ENG, BUS, ART, EDU and their priority values are 4, 3, 2, 1, and 0, respectively. For example, if the priority queue is initially empty and a student needs to be enqueued, this student can be added to the empty queue regardless of their faculty priority.If a second student from SCI needs to be enqueued, this second student is enqueued at the front of the queue if the first student was not from SCI. The second student is enqueued to the rear of the queue if the first student was also from SCI. Then, if a third student needs to be enqueued, the position in which this third student is inserted into the priority queue depends on their faculty priority. If their faculty has lower priority than any other student in the queue, then the third student is enqueued at the rear of the queue. If their faculty priority is lower than that of the student at the front of the queue and higher than that of the student at the rear of the queue, then the third student node is inserted between the two already existing nodes in the chain.However, if all students that need to be enqueued have the same faculty priority (e.g., all students are from ENG), then they are all enqueued based on a first come first serve order.The following illustration of the priority queue with a doubly linked chain representation shows three enqueued students. The highest priority student “Joe” who is from SCI is at the front of the queue and will be dequeued first, when space becomes available in the course, to be then added to the enrollment table. The lowest priority student “Mary” who is from ART, is at the head of the rear of the queue and will be dequeued last if space becomes available in the course. The student from ENG, “Dan”, has a lower priority than Joe but a higher priority than Mary.So, the node containing Dan’s data is inserted between the two already existing nodes in the chain such that you will have to linearly traverse the chain that represents your priority queue to determine the position in which a new student node will be inserted based on their faculty priority.123456 SCI Joe Smith 136457 ENG Dan Coles 126458 ART Mary Hoehn3 Priority QueueMethods that you will implement in the PriorityQueue class: PriorityQueue() – the __init__ method creates an empty doubly linked chain with both head and tail having references to None, and the size of the priority queue should be set to 0.enqueue(item) – enqueues a new student node to the rear of the queue or traverses the queue to determine the position in which the new node will be inserted based on the faculty priority of the given item, i.e., the student node. This method updates the priority queue size by incrementing it by 1. This method does not return anything. dequeue() – dequeues and returns the highest priority student node from the front of the queue and updates the size of the priority queue by decrementing it by 1. An Exception is raised (with an appropriate argument) if dequeueing from an empty queue. size() – returns the number of students in the priority queue.isEmpty() – returns True if the priority queue is empty, if its size is 0, or False otherwise. __str__() – returns the string representation of the priority queue. The printout of the queue contents should be between square brackets, separated by commas, with the highest priority students’ records printed out first including their student id, faculty and first and last names. Test your PriorityQueue class thoroughly. You may want to use assertions to verify the behavior of your class implementation. Place these tests under if __name__ == “__main__”: in enrollStudent.py for the marker to see.Write a main program in assignment3.py to do the following: Prompt the user to either register or drop students from the course. The user can enter either ‘R’ or ‘D’ or ‘Q’ for registering or dropping or to exit the program, respectively. Any other responses are invalid, and should cause your program to re-prompt for a valid entry. Your program will prompt the user to enter the file name containing the input student data, and if the file cannot be read for any reason, continue to re-prompt until a valid filename is provided.Your program will then read the input students data from the file. Each line in the file represents one student record. Each student record includes the student id, faculty, and the student’s first and last names separated by white space. You will need to read each line in the input file, i.e., each student record, as a string and split it into four different string tokens to separately obtain the student id, faculty, and first and last names. If a line in the text file contains invalid data or formatting, the entire program should exit gracefully with a warning message indicating which line of the text file that the program failed on.If the user enters ‘R’ at the prompt, your program will prompt for the filename of the file containing the students to be registered and will read this file, create a student node for each record in the file, and populate the enrollment table accordingly. If the file contains more than 50 records, i.e., the number of records exceeds the capacity of the enrollment table, the records after line 50 will be placed in the priority queue.Once all the students have been registered, the program will then print out the contents of the enrollment table between square brackets and separated by commas. The printout should include the index in whicheach record is stored followed by the student record. The output should be written to a file named “enrolled.txt”. This output file shows the current status of enrollment at any point in time but not the history of enrollment from previous program runs, i.e., you do not need to append to this file. The program should also print out the contents of the priority queue or empty square brackets if the queue is empty. The output should be appended to a file named “waitlist.txt” to keep track of the history of the waiting list, i.e., the priority queue as it gets shorter or longer.If the user enters ‘D’ at the prompt, your program will prompt for the filename of the file containing the records of the students to be dropped from the course. Your program will read this file and search the enrollment table for student nodes given the student ids provided in this file. Each time a student is dropped from the course, i.e., a spot becomes available in the enrollment table, your program should then dequeue the highest priority student from the priority queue and enroll this student in the course by adding this student node to the enrollment table. If the file contains a valid record for a student who is not currently enrolled in the course, a warning message should be displayed (see sample output below) and this student should be ignored.After dropping students and registering new students from the priority queue, the program will then print the contents of the updated priority queue or empty square brackets if the queue is empty. The output is appended to the file named “waitlist.txt”.If the user enters ‘Q’ at the prompt, your program will finish after displaying a goodbye message. Sample outputs for registering a subset of six students: Would you like to register or drop students [R/D]: R Please enter a filename for student records: sample_reg.txt Sample outputs in enrolled.txt: [0: 129051 ART Paul Johnston, 1: 124912 SCI Ahmed Salem, 4: 124592 ENG Jeanne Desjardins, 20: 123456 SCI Mary Soleiman, 37: 126013 SCI Faruk Hosney, 42: 124830 EDU Jane Osborne] Sample outputs in waitlist.txt: []Sample outputs for registering two students at same table index: Would you like to register or drop students [R/D]: R Please enter a filename for student records: sample_reg_sameIndex.txt Sample outputs in enrolled.txt: [0: 129051 SCI Jake Sun, 188451 ART Charlotte Williams] Sample outputs in waitlist.txt: []Sample outputs after registering fifty students from the input.txt file: Would you like to register or drop students [R/D]: D Please enter a filename for student records: sample_drop.txt WARNING: Christie Fee (ID: 168258) is not currently enrolled and cannot be dropped. Sample outputs in waitlist.txt: [177829 ENG Benjamin Schneider, 181844 ENG Antoine Ledophin, 183286 ENG Marina Alfred, 186798 ENG Louis Windsor, 176812 BUS John Deacon, 185792 BUS Maha Bushara, 173812 ART Nevine Salib, 176681 ART Aimee Sauver, 187987 ART Samuel Nathaneal, 183476 EDU Jonathan Beck]Assessment: In addition to making sure that your code runs properly, we will also check that you follow good programming practices. For example, divide the problem into smaller sub-problems, and write functions/methods to solve those sub-problems so that each function/method has a single purpose; use the most appropriate data structures for your algorithm; use concise but descriptive variable names; define constants instead of hardcoding literal values throughout your code; include meaningful comments to document your code, as well as docstrings for all methods and functions; and be sure to acknowledge any collaborators/references in a header comment at the top of your Python files. Be sure to assert that all inputs to all methods are valid.Restrictions for this assignment are that you cannot use break/continue, and you cannot import any modules other than your enrollStudent module. Doing so will result in deductions. Rubric: Code quality and adherence to specifications: 20% StudentNode class and tests: 15% EnrollTable class and tests: 25% PriorityQueue class and tests: 25% Main program: 15%Submission Instructions: All of your code should be contained in TWO Python files: enrollStudent.py and assignment3.py. Make sure that you include your name (as author) in a header comment at the top of all files, along with an acknowledgement of any collaborators/references. Please submit your TWO python files via eClass before the due date/time. Do not include any other files in your submission. Note that late submissions will not be accepted. You can make as many submissions as you would like before the deadline – only your last submission will be marked. So submit early, and submit often.
You are tasked with creating a one-player tile-matching game, played with one standard “double-six” set of dominoes. A domino is a tile with two ends, where each end has 0 to 6 dots on it. For example, a domino with 3 dots on one end and 4 dots on the other end is shown below: A standard double-six domino set contains the 28 unique dominoes illustrated below:The game will start with all 28 dominoes face down in a grid with 7 columns and 4 rows. (i.e. by face down, we mean that the player can only see the back of the domino, not the side with all of the dots.)The player will choose a domino from the grid and turn it over. The player will then attempt to play the domino by adding it to the top of one of three stacks of dominoes in the play area. If a stack is empty (i.e. it does not currently contain any dominoes), any domino can be added to it and the player can decide on the orientation of the domino (i.e. which end is at the top and which end is at the bottom). If a stack has at least one domino currently in it, a new domino can only be added to the top of the stack if one of its ends has the same number of dots as the top end of the domino that is currently on the top of the domino stack. In that case, the domino must be added to the stack so that the end of the domino with the matching number of dots is oriented to the bottom (i.e. touching the side with the matching number of dots on the domino already on the stack), as illustrated below:This domino can be added to the top of Stack 0 or Stack 2, but not Stack 1. Stack 0 Stack 1 Stack 2 or (before domino is played) (after domino is played)The player continues to draw dominoes from the grid and adding them to a stack in the play area until one of the stacks reaches a height of 6 dominoes (win) or the player cannot play the domino on any of the 3 stacks in the play area (lose).Create a Python file called domino175.py. Inside this file, create and test a Domino class according to the description below. Note that the following methods form the public interface for this class – you must complete them all as specified, and cannot add additional methods to the public interface. However, you can include additional private helper methods that are only called within this class, if you wish.Domino(dotsA, dotsB) – creates a domino, where the number of dots on each end of the domino are described by the integers dotsA and dotsB. After asserting that the input parameters are valid, dotsA and dotsB should be used to initialize two private attributes: top and bottom. Both of these attributes are integers, and the top is the end with the most dots on it. A third private attribute, faceDown, should also be created which indicates if the tile is facing down (True) or facing up (False). A domino should be facing up when it is first created.setTop(dots) – updates which end of the Domino is at the top, according to the dots parameter. The integer dots must match one of the existing ends of the Domino instance (otherwise an AssertionError is raised). Nothing is returned.turnOver() – updates the Domino instance so that if it was facing up, it will now be facing down. Similarly, if it was facing down, it will now be facing up. Nothing is returned. getTop() – returns the integer number of dots on the top end of the Domino instance. getBottom() – returns the integer number of dots on the bottom end of the Domino instance. isFaceDown() – returns the Boolean value indicating whether the Domino instance is facing down (True) or up (False).__str__() – returns the string representation of the Domino instance. The format of this string should be ‘[bottom number of dots|top number of dots]’ if it is facing up. For example, a domino with 3 dots on the bottom and 4 dots on top will return the string ‘[3|4]’. Any domino that is facing down will have question marks, ‘?’, instead of the numbers: ‘[?|?]’ Test your Domino class thoroughly before moving on. You may wish to use assertions to verify expected behaviour, like in Lab 7 (Linked Lists), though you don’t have to. Place these tests under if __name__ == “__main__”: in domino175.py for the marker to see.Create and test a DominoDeck class in domino175.py, according to the description below. Note that the following methods form the public interface for this class – you must complete them all as specified, and cannot add additional methods to the public interface. However, you can include additional private helper methods that are only called within this class, if you wish.DominoDeck() – creates an empty deck of dominoes, capable of holding the 28 dominoes in a standard “double-six” set. Notice that this deck acts very much like a queue, where we deal the front domino and add new dominoes to the rear of the deck. In the __init__ method, create a single private attribute that is the most time-efficient queue with a maximum capacity that we covered in the lectures.You should import the queues.py file provided with Lab 6 to accomplish this. (You do not need to submit the queues.py file since your marker will also have access to that file.) populate(useFile) – modifies the deck by adding new dominoes face up to the rear of the deck.Nothing is returned. If useFile is True, the user should be prompted to provide the name of an input text file. If any problem occurs when opening the file, an error message should be displayed and the user should be re-prompted to provide the name of another input text file, until the file can be opened successfully. (See output_testWin.txt.) The input text file should contain information about the dominoes that will be added to the deck, in the same order as indicated in the file. (i.e. The first line of the text file corresponds to the first domino that should be added to the deck.)Each valid line of the text file will contain an integer, followed by a forward slash (‘/’), followed by another integer, where the integers represent the number of dots on each end of the domino. (See the sample testWin.txt provided.) You cannot assume that all lines in the file will be valid, and you cannot assume that there will be information for exactly 28 dominoes in the file. If there is invalid data in the file or not 28 dominoes, you should raise an Exception with the argument “Cannot populate deck: invalid data in xx” (where xx is replaced with the filename), ensure the deck is empty, and close the file before leaving this method. If there is information about exactly 28 valid dominoes in the file, you can assume that those dominoes will form a full “double-six” set which should be added to the deck, in the same order that they appear in the file. If useFile is False, a complete “double-six” set of dominoes should be created, shuffled, and used to populate the deck. If useFile is not True or False, an AssertionError should be raised with the argument “Cannot populate deck: invalid argument provided.” Nothing should be added to the deck in this case. deal() – modifies the deck by removing the domino from the front of the deck, and returns that front domino, face down. Raise an Exception if the deck is empty, with the argument ‘Cannot deal domino from empty deck’. This method should have an O(1) time efficiency. isEmpty() – returns a Boolean value indicating whether there are no dominoes in the deck (True) or if there is at least one domino in the deck (False). size() – returns the integer number of dominoes currently in the deck.__str__() – returns the string representation of all of the dominoes in the deck. You can decide how this string should be formatted, but make it clear which is the front domino and be sure to show the number of dots on each domino (i.e. do not just show all dominoes as face down) Test your DominoDeck class thoroughly before moving on. Again, place these tests under if __name__ == “__main__”: in domino175.py for the marker to see.Create and test a DominoStack class in domino175.py, according to the description below. Note that the following methods form the public interface for this class – you must complete them all as specified, and cannot add additional methods to the public interface. However, you can include additional private helper methods that are only called within this class, if you wish.DominoStack() – creates an empty stack that will ultimately hold Domino instances. Nothing is returned. Note that you may use inheritance (in which case you should include the code for the Stack class that you are inheriting from in the domino175.py file), or you can implement from scratch – either approach is equally acceptable for this assignment.peek() – returns the number of dots on the top of the Domino that is at the top of the stack. Raises an Exception with the argument “Error: cannot peek into an empty stack” if the stack does not contain any dominoes. isEmpty() – returns a Boolean value indicating whether there are no dominoes on the stack (True) or if there is at least one domino on the stack (False). size() – returns the integer number of dominoes currently on the stack.push(domino) – adds the provided domino onto the top of the DominoStack if the DominoStack is empty, or if the number of dots on the top of the Domino currently on the top of the stack matches the number of dots on one side of the provided domino. If the last case, add the provided domino so that its bottom matches the top of the domino below it. Raise an AssertionError with the argument “Can only push Dominoes onto the DominoStack” if the provided domino is not an instance of the Domino class. If the domino cannot be added to the top of the stack (i.e. the stack has a domino on its top whose top dots do not match the dots on either side of the provided domino), raise an Exception with the argument “Cannot play xx on stack”, where xx is the string representation of the domino, face up. This method should have an O(1) time efficiency.__str__() – returns the string representation of the DominoStack instance. Specifically, it should return the string representations of any Dominoes on the stack, separated by a single dash (‘-‘). The bottom of the stack should be at the beginning of the returned string, the top should be at the end. Test your DominoStack class thoroughly before moving on. Again, place these tests under if __name__ == “__main__”: in domino175.py for the marker to see. You now have a domino175 module that you can use for many different domino game programs! Create a Python file called assignment2.py. Inside this file, create and test a Table class according to the description below. Note that the following methods form the public interface for this class – you must complete them all as specified, and cannot add additional methods to the public interface. However, you can include additional private helper methods that are only called within this class, if you wish. Table() – creates a new empty domino game table. This table should have one deck (a DominoDeck) that is originally empty. This table will also have an empty grid, capable of holding 4 rows with 7 columns of dominoes. Finally, this table will have a playing area that consists of 3 DominoStacks, which are initially empty. All of these should be stored in private attributes. Nothing is returned.dealGrid(useFile) – fills the deck with dominoes from a file (if useFile is True) or from a standard “double-six” set (if useFile is False). Any exceptions raised while filling the deck should be propagated and the grid should not be populated. If the deck was filled successfully, dominoes are dealt from the deck and added face down to the grid, starting in the upper left corner and moving right until the first row is complete, then moving onto the second row (left to right), third row (left to right), and fourth row (left to right). Nothing is returned.select(row, col) – after asserting that row and col are valid, removes the domino at the specified row, column position from the grid and replaces it with the string ‘***’ (3 asterisks). If there is no domino at the specified location (e.g. if it is already the string ‘***’), raise an Exception with the argument “There is no domino at row xx, column yy”, where xx is the specified row and yy is the specified column. Returns the removed domino face up.playDomino(domino, stackNum) – after asserting that domino is a Domino and stackNum is a valid integer, tries to add the provided domino to the top of the stack indicated by stackNum, and displays a message describing this action (see sample output). If successfully added, displays “Success!” on the screen and returns True; otherwise, displays the resulting error message and returns False. isWinner() – returns True if one of the stacks contains at least 6 dominoes, False otherwise. getNumStacks() – returns the integer number of stacks in the playing area. getNumRows() – returns the integer number of rows in the grid of dominoes. getNumColumns() – returns the integer number of columns in the grid of dominoes.revealGrid() – displays the face up version of all dominoes that are currently in the grid, for the player to see. Be sure that all dominoes in the grid are face down again before leaving this method. Nothing is returned. __str__() – returns the string representation of the grid and playing stacks on the table. See sample output for formatting. Be sure to test this Table class thoroughly before moving on. However, you do not need to include these tests for the marker to see.In assignment2.py, prompt the user to select whether s/he wishes to play in Test Mode or Game Mode. Continue to re-prompt until the user enters a valid choice. Create an instance of your Table class. Initialize your table so that its deck is populated from a file if in test mode, or from a shuffled standard “double-six” set if in game mode. If the deck is invalid, the game should end with an explanatory message (see sample output_invalidDeck1.txt).When in test mode: Before play begins, display all of the dominoes (face up) in your grid. This will make it easy for you to check that you are selecting the correct dominoes as you continue your tests. For the rest of the time in this mode, be sure that you display your grid with the dominoes face down.Select the domino in the upper left corner of the grid. Attempt to play that domino on a stack, starting with stack 0. If it cannot be played on stack 0, try to play it on stack 1. If it cannot be played on stack 1, try to play it on stack 2. If it cannot be played on stack 2, the player loses. Continue selecting dominoes from the grid and trying to play them on the stacks (as described above). When selecting from the grid, move left to right, then down to the next row, left to right, and so on until the game is over or there are no more dominoes left to select from the grid.At the end display whether the game was won (if one of the stacks has 6 dominoes in it) or lost (could not play a domino). When in game mode: Display “Under Construction” on the screen and end the game.Task 6: main program (OPTIONAL – not for marks, but gives you a more interesting game to play): When in game mode: Prompt the user to enter the row and column of the domino s/he would like to select from the grid. If it is a valid location, prompt the user to enter the stack number that s/he would like to try to play the domino on. If it is an empty stack, ask the player which end of the domino should be at the top of the stack, and add the domino according to that specification.Gracefully handle any errors that result when the player selects an invalid location from the grid, or tries to place a domino on an invalid stack, and continue playing the game until the player wins (has a stack with 6 dominoes on it) or loses (cannot play a domino on any of the stacks).Sample Output Refer to the provided sample output files for formatting and exact message displays. Assessment In addition to making sure that your code runs properly, we will also check that you follow good programming practices. For example, divide the problem into smaller sub-problems, and write functions/methods to solve those sub-problems so that each function/method has a single purpose; use the most appropriate data structures for your algorithm; use concise but descriptive variable names; define constants instead of hardcoding literal values throughout your code; include meaningful comments to document your code, as well as docstrings for all methods and functions; and be sure to acknowledge any collaborators/references in a header comment at the top of your Python files. Restrictions for this assignment are that you cannot use break/continue, and you cannot import any modules other than the random module, the stack module (from Lab 5), the queues module (from Lab 6), and your domino175 module. Doing so will result in deductions.Rubric: ● Code quality and adherence to specifications: 20% ● Domino class and tests: 10% ● DominoDeck class and tests: 15% ● DominoStack class and tests: 15% ● Table class: 25% ● Main automated game: 15%Submission Instructions ● All of your code should be contained in TWO Python files: domino175.py and assignment2.py. ● Make sure that you include your name (as author) in a header comment at the top of all files, along with an acknowledgement of any collaborators/references. ● Please submit your TWO python files via eClass before the due date/time. ● Do not include any other files in your submission. ● Note that late submissions will not be accepted. You can make as many submissions as you would like before the deadline – only your last submission will be marked. So submit early, and submit often.
Goal: refresher of Python and hands-on experience with file input/output, built-in data structures, and string manipulation.The owners of a number of small businesses have teamed up to offer a shared delivery service for their customers. Their customers can order items online from any of their stores during the week, and then on Saturday, the store owners will work together to assemble the items and have them delivered as a single package to each customer’s home. This approach should cut down on delivery costs for the store owners, while providing a great service for their customers.You have been hired to create a Python program that will take all of the orders placed for all of the stores each week, and summarize the information into an easy to read table that tells the store owners how many drivers will be needed to deliver all of the packages for that week. They will need a driver for each zone of the city where at least one delivery needs to be made, with a maximum of 10 deliveries per driver. So, for example, if there are 13 deliveries that need to made to the West zone of the city, 2 drivers will be needed for that zone.The store owners also want to keep track of the cost of this new delivery service. Assuming they will pay their drivers $12 for every package that they deliver, your program should calculate the total delivery cost for the week. Your program should also calculate the percentage that this delivery cost is of the total amount purchased by all of the customers for the week. Both of these values should be displayed in the summary table.In addition to calculating the above information, your program should also be able to create an invoice summarizing all of the items that will be delivered to a given address. Note that many different people living at the same address may have made orders on different days during the week, but all items that are to be delivered to the same address should be put together in a single delivery package.Input You will be provided with THREE text files. These text files will be updated every week (on Saturday), so your program must be able to read in the most up-to-date information every time it is run. The first text file is called products.txt, and it contains information about all of the products that all of the stores offer for purchase online. Specifically, each line contains a unique product ID, followed by a description of the product, followed by the product’s price in cents (so it is a whole number). All of these items are separated by a semicolon (“;”), as can be seen in the sample products.txt provided with the assignment description.The second text file is called orders.txt, and it contains information about all of the items purchased during the current week. Specifically, each line contains information about one product that has been purchased: the date of the purchase (yyyy-mm-dd). e.g. 2021-01-18 represents January 18th, 2021. the customer’s name. the customer’s complete address, with the postal code at the very end. The format of a postal code is 3 characters, followed by a single space, followed by 3 characters. e.g. T6G 2E8. You can assume that all postal codes provided in orders.txt are correct and valid. the product ID of the item purchased. the number of those items that were purchased.All pieces of information are separated by a percent sign (“%”), as can be seen in the sample orders.txt provided with the assignment description. The third text file is called zones.txt, and it contains information about which areas of the city (as indicated by the first 3 characters of the postal codes) are included in each delivery zone. Each line will contain the name of the zone, followed by a “#”, followed by the 3-character starting sequence of all postal codes that belong to that zone. If there are multiple 3-character postal code starting sequences for that zone, they will all be listed on the same line, separated by a comma (“,”). For example, there are five postal code starting sequences in the South-East zone of Edmonton, and would be listed as: South-East#T6A,T6B,T6C,T6E,T6PPlease keep in mind that as this delivery service becomes more popular, the team of small business owners may decide to split the current zones up into smaller delivery zones or expand their delivery to areas outside the city. So your program must read in the latest information from zones.txt each week (i.e. every time the program is run).Output Menu: Your program should output a menu which allows the user to keep selecting options until s/he chooses to quit the program. It should look exactly like this: ********************************************** Welcome to the Small Business Delivery Program ********************************************** What would you like to do? 1. Display DELIVERY SUMMARY TABLE for this week 2. Display and save DELIVERY ORDER for specific address 3. Quit > The only valid options for the user to enter are the numbers 1, 2, or 3. If the user enters an invalid choice, your program should display an error message and then re-prompt the user to enter a valid choice. It should continue to re-prompt until a valid choice is entered. For example: ********************************************** Welcome to the Small Business Delivery Program ********************************************** What would you like to do? 1. Display DELIVERY SUMMARY TABLE for this week 2. Display and save DELIVERY ORDER for specific address 3. Quit > 4 Sorry, invalid entry. Please enter a choice from 1 to 3. > abc Sorry, invalid entry. Please enter a choice from 1 to 3. > Option 1: When the user chooses option 1, the delivery summary table should be displayed, and should look like this sample output: ********************************************** Welcome to the Small Business Delivery Program ********************************************** What would you like to do? 1. Display DELIVERY SUMMARY TABLE for this week 2. Display and save DELIVERY ORDER for specific address 3. Quit > 1 +—————+————+———–+ | Delivery Zone | Deliveries | Drivers | +—————+————+———–+ | Millwoods | 2 | 1 | | North-West | 10 | 1 | | South-East | 5 | 1 | | West | 13 | 2 | +—————+————+———–+ | Total drivers needed 5 | | Total delivery cost $ 360.00 | | Delivery cost/purchases 14.0% | +—————————————-+ Only zones that have at least one delivery should be included in the table. The delivery zones should be displayed in alphabetical order.The table should be formatted exactly as in the sample output. Specifically, pay attention to the column widths, text alignments, and borders. For example, the Delivery Zone column is left aligned, the Deliveries column is center aligned, and the Drivers column is center aligned. In the bottom section of the table, you can safely assume that the total delivery cost will never be greater than $99,999.99, and you will always want to show the delivery cost/purchases as a percentage rounded to one decimal (right aligned). After the table has been displayed, the main menu is displayed again for the user to make another choice.Option 2: When the user chooses option 2, s/he is prompted to enter a complete address. If it does not match an address from orders.txt exactly, an error message is displayed and the main menu is displayed again for the user to make another choice. ********************************************** Welcome to the Small Business Delivery Program ********************************************** What would you like to do? 1. Display DELIVERY SUMMARY TABLE for this week 2. Display and save DELIVERY ORDER for specific address 3. Quit > 2 Address: 123 doesn’t exist Invalid address. ********************************************** Welcome to the Small Business Delivery Program ********************************************** What would you like to do? 1. Display DELIVERY SUMMARY TABLE for this week 2. Display and save DELIVERY ORDER for specific address 3. Quit > If a valid address is entered, a delivery order listing all items in the package delivered to that address is displayed on the screen AND saved to a text file called invoice.txt. ********************************************** Welcome to the Small Business Delivery Program ********************************************** What would you like to do? 1. Display DELIVERY SUMMARY TABLE for this week 2. Display and save DELIVERY ORDER for specific address 3. Quit > 2 Address: 13420-114 Ave T5M 2Y5 Delivery for: 13420-114 Ave T5M 2Y5 ============================================= Date Item Price —— ————————– ——— JAN 17 002 x Sunflower seeds $ 10.38 JAN 17 001 x Lettuce seeds $ 3.29 JAN 17 001 x Cherry tomato seeds $ 4.29 JAN 17 001 x Yellowfin zucchini * $ 5.49 JAN 19 001 x Pumpkin seeds $ 3.29 JAN 20 003 x Garden tools (5-pc) $ 77.97 ——— $ 104.71The format of the delivery order should be exactly as shown above. In particular, note that the address is redisplayed (right-aligned) at the top of the delivery order. If the address is longer than 30 characters, only the first 29 characters are displayed followed by an asterisk (“*”).The items should be sorted in order of delivery date. (If multiple items were ordered on the same date, the relative order of those items does not matter.) The first column contains the date. The date should be displayed as the first three letters of the month (all capitalized) followed by a single space and the two-digit day. All together, this should always occupy a field width of 6 (as shown). The second column contains the number of items ordered, along with the description. The number of items will not exceed 999, and should be right aligned in a field width of 3 with leading zeros. If the item description is longer than 20 characters, only the first 19 characters should be displayed, followed by an asterisk (“*”). The third column contains the total price charged for that line item. You can assume that the price will not exceed $99,999.99. At the very bottom of the delivery order, the total amount paid for the package delivered should be listed, aligned under the third column. You can assume that the total will not exceed $99,999.99. Note that the user can select option 2 before selecting option 1. After the delivery order has been displayed, the main menu is displayed again for the user to make another choice.Option 3: When the user chooses option 3, a thank you message will be display and the program will end: ********************************************** Welcome to the Small Business Delivery Program ********************************************** What would you like to do? 1. Display DELIVERY SUMMARY TABLE for this week 2. Display and save DELIVERY ORDER for specific address 3. Quit > 3 Thank you for using the Small Business Delivery Program! Goodbye.Testing Use the sample input text files to test your code. However, keep in mind that the markers will test your code with DIFFERENT input data in the input text files. So you should also test your code by adding at least one new product to products.txt, one new zone to zones.txt, and additional purchases in orders.txt.Assessment In addition to making sure that your code runs properly, we will also check that you follow good programming practices. For example, divide the problem into smaller sub-problems, and write functions to solve those sub-problems so that each function has a single purpose; use the most appropriate data structures for your algorithm; use concise but descriptive variable names; define constants instead of hardcoding literal values throughout your code; include meaningful comments and docstrings to document your code; and be sure to acknowledge any collaborators/references in a header comment at the top of your Python file.Restrictions for this assignment: you cannot use break/continue, and you cannot import any modules. Doing so will result in deductions. Rubric Code quality and adherence to the specifications: 20% File handling (input/output) and use of appropriate data structures: 15% Program control and input validation: 10% Option 1: 35% Option 2: 20%Hints for getting started Figure out your algorithms BEFORE trying to write your code. Break tables down into single lines of strings. There’s a lot of different data here that forms various relationships – dictionaries will be your friend when solving this problem. When doing calculations with money amounts, keep the amounts in cents (i.e. whole numbers) until the very end – i.e. only convert to dollars when you are about to display the amount on the screen. If you convert to float values too early, you may get unexpected results when you try to add or subtract them. This is because computers can’t represent the decimal portion of float numbers exactly, just a close approximation.Submission Instructions Please follow these instructions to correctly submit your solution: All of your code should be contained in a single Python file: assignment1.py. Make sure that you include your name (as author) in a header comment at the top of assignment1.py, along with an acknowledgement of any collaborators/references. Please submit your assignment1.py file via eClass before the due date/time. Do not include any other files in your submission. Note that late submissions will not be accepted. You can make as many submissions as you would like before the deadline – only your last submission will be marked. So submit early, and submit often.
