MCD4710 – Introduction to Algorithms and Programming Assignment 1 (8%) Due: Thursday, November 28, 2019, 5:00 pm – Week 6 Objectives The objectives of this assignment are: To gain experience in designing algorithms for a given problem description and implementing those algorithms in Python. To demonstrate your understanding on: o How to decompose code into functions in Python. o How to read from text files using Python. o How to manipulate lists using basic operations. Submission Procedure Your assignment will not be accepted unless it meets these requirements: 1. Your name and student ID must be included at the start of every file in your submission. 2. Save your files into a zip file called YourStudentID.zip 3. Submit your zip file containing your entire submission to Moodle. Late Submission Late submission will have 5% deduction of the total assignment marks per day (including weekends). Assignments submitted 7 days after the due date will not be accepted. Important Notes Please ensure that you have read and understood the university’s procedure on plagiarism and collusion available at https://www.monashcollege.edu.au/__data/assets/pdf_file/0005/1266845/Student-Academic- Integrity-Diplomas-Procedure.pdf . You will be required to agree to these policies when you submit your assignment. Your code will be checked against other students’ work and code available online by advanced plagiarism detection systems. Make sure your work is your own. Do not take the risk. Your program will be checked against a number of test cases. Do not forget to include comments in your code explaining your algorithm. If your implementation has bugs, you may still get some marks based on how close your algorithm is to the correct algorithm. This is made difficult if code is poorly documented. Where it would simplify the problem you may not use built-in Python functions or libraries (e.g. using list.sort() or sorted()). Remember that this is an assignment focusing on algorithms and programming. MCD4710 – Introduction to Algorithms and Programming Assignment code interview Each student will be interviewed during a lab session regarding their submission to gauge your personal understanding of your Assignment code. The purpose of this is to ensure that you have completed the code yourself and that you understand the code submitted. Your assignment mark will be scaled according to the responses provided. Interview Rubric 0 The student cannot answer even the simplest of questions. There is no sign of preparation. They probably have not seen the code before. 0.25 There is some evidence the student has seen the code. The answer to a least one question contained some correct points. However, it is clear they cannot engage in a knowledgeable discussion about the code. 0.5 The student seems underprepared. Answers are long-winded and only partly correct. They seem to be trying to work out the code as they read it. They seem to be trying to remember something they were told but now can’t remember. However, they clearly know something about the code. With prompting, they fail to improve on a partial or incorrect answer. 0.75 The student seems reasonably well prepared. Questions are answered correctly for the most part but the speed and/or confidence they are answered with is not 100%. With prompting, they can add a partially correct answer or correct an incorrect answer. 1 The student is fully prepared. All questions were answered quickly and confidently. It is absolutely clear that the student has performed all of the coding themselves. Marking Criteria This assignment contributes to 8% of your final mark. • Part A: Representation and display (15 marks) • Part B: Helper functions (25 marks) • Part C: Generating random board (30 marks) • Part D: Decomposition, Variable names and code Documentation (10 marks) Total: 80 marks MCD4710 – Introduction to Algorithms and Programming Magnets Puzzle The puzzle game Magnets involves placing a set of magnet blocks in pre-arranged empty slots on a board to satisfy a set of constraints. Figure 1 – Example: Unsolved Board with empty slots Figure 2 – Example: Solved board all slots are filled with magnet blocks. Each slot can contain either a non-magnetic blank block (indicated by two ‘X’s), or a magnet block with a positive (+) pole and a negative (-) pole. The numbers along the left and top sides of the board show the number of required positive poles (+) in a particular row or column. Similarly, the numbers along the right and bottom show the number of negative poles (-) that are necessary in a particular row or column. (See Fig. 2) Rows and columns without a number at one or both ends can have any number of positive (+) or negative (-) poles. In addition, a puzzle solution must satisfy the constraint that horizontally and vertically adjacent squares in neighbouring blocks cannot have the same poles (See Fig. 3). Diagonally joined squares are not limited this way as shown in Fig. 4. Figure 3 – Examples of Invalid Magnet Block Placements Figure 4 – Examples of Valid Magnet Block Placements MCD4710 – Introduction to Algorithms and Programming Part A: Representation and display (15 marks) Magnets will require the following data structures: positivesColumn, negativesColumn, positivesRow and negativesRow lists, which indicate the number of relevant poles. The positive (+) poles must be shown along the top and left edges and the negative (–) poles must be shown on the bottom and right edges. Values of -1 indicate that the corresponding row or column is unconstrained and can have any number of positive (+) or negative (–) poles. Slots represent an empty space that can accommodate magnetic or blank blocks. Squares represent a single square on the board i.e. half a slot or half a block. All blocks and slots consist of two squares. orientations, represents a list of lists with all pre-arranged slots on an board. Orientations’ lists represent a single row on the board and it will contain one of the following characters, ‘T’, ‘B’, ‘L’, ‘R’. A vertical slot will contain the letters ‘T’ and ‘B’ that represent the top and bottom of the slot. A horizontal slot will contain the letters ‘L’ and ‘R’ that represent the left and right sides of the slot. M and N represent the size of the board i.e. M rows * N columns. See the example below: M = 6 # number of rows N = 5 # number of columns positivesColumn = [3, 1, 2, -1, -1] negativesColumn = [-1, -1, -1, -1, 2] positivesRow = [-1, 1, -1, -1, 2, 2] negativesRow = [-1, 2, 1, -1, 2, 2] orientations =[[‘L’, ‘R’, ‘L’, ‘R’, ‘T’], [‘T’, ‘T’, ‘L’, ‘R’, ‘B’], [‘B’, ‘B’, ‘L’, ‘R’, ‘T’], [‘T’, ‘T’, ‘L’, ‘R’, ‘B’], [‘B’, ‘B’, ‘L’, ‘R’, ‘T’], [‘L’, ‘R’, ‘L’, ‘R’, ‘B’]] Example 1 – Sample variables for input parameters Note: These values are not restricted to the example given above and they could be any number. Your code should be able to handle any board configuration within the appropriate constraints. For simplicity, you can restrict your testing to the following board sizes: M N 4 3 4 5 6 5 6 7 Task 1: Initial setup (5 marks) Write the function readBoard(fileName) which takes as input the name of a file in which the board is stored and returns positivesColumn, negativesColumn, positivesRow , negativesRow , orientations, and workingBoard as shown in Example 1 in the previous section. workingBoard represents a partial solution to the board as a list of lists (see Example 3 in Part A – Task 2), where each square contains one of the following characters ‘+’, ‘-‘, ‘X’, and ‘E’. ‘E’ represents the empty squares and ‘X’ represents blank (non-magnetic) blocks. MCD4710 – Introduction to Algorithms and Programming The following shows a sample file: 6 5 3 1 2 -1 -1 -1 -1 -1 -1 2 -1 1 -1 -1 2 2
-1 2 1 -1 2 2 LRLRT TTLRB BBLRT TTLRB BBLRT LRLRB +-XXE XXEEE XXEE+ +EXX- -EEEX +-+-X Example 2 – Sample File This file must have the following format: Lines 1 and 2: Represent M and N respectively Lines 3 to 6: Represent positivesColumn, negativesColumn, positivesRow and negativesRow, respectively. Lines 7 to (7+M-1): Represent the orientations M Remaining lines: Represent the workingBoard Task 2: Display (10 marks) Extend your program to print a board on the screen using the function printBoard(positivesColumn, negativesColumn, positivesRow , negativesRow , orientations, workingBoard). This function prints the content of the workingBoard to the screen except it will print a blank space for any square that contains ‘E’. The numbers in positivesColumn, negativesColumn, positivesRow and negativesRow are also printed if they are not equal to -1. An example of workingBoard and the expected output of printBoard is given below. Your board visualisation must follow the formatting of the example below: M = 6 # number of rows N = 5 # number of columns positivesColumn = [3, 1, 2, -1, -1] negativesColumn = [-1, -1, -1, -1, 2] positivesRow = [-1, 1, -1, -1, 2, 2] negativesRow = [-1, 2, 1, -1, 2, 2] orientations =[[‘L’, ‘R’, ‘L’, ‘R’, ‘T’], [‘T’, ‘T’, ‘L’, ‘R’, ‘B’], [‘B’, ‘B’, ‘L’, ‘R’, ‘T’], [‘T’, ‘T’, ‘L’, ‘R’, ‘B’], [‘B’, ‘B’, ‘L’, ‘R’, ‘T’], [‘L’, ‘R’, ‘L’, ‘R’, ‘B’]] MCD4710 – Introduction to Algorithms and Programming workingBoard =[[‘+’, ‘-‘, ‘X’, ‘X’, ‘E’], [‘X’, ‘X’, ‘E’, ‘E’, ‘E’], [‘X’, ‘X’, ‘E’, ‘E’, ‘+’], [‘+’, ‘E’, ‘X’, ‘X’, ‘-‘], [‘-‘, ‘E’, ‘E’, ‘E’, ‘X’], [‘+’, ‘-‘, ‘+’, ‘-‘, ‘X’]] printBoard(positivesColumn, negativesColumn, positivesRow , negativesRow , orientations, workingBoard) + | 3 | 1 | 2 | | | —|—|—|—|—|—|— | + – | X X | | —|—|—|—|—| |— 1 | X | X | | |2 —| | |—|—|—|— | X | X | | + |1 —|—|—|—|—| |— | + | | X X | – | —| | |—|—|—|— 2 | – | | | X |2 —|—|—|—|—| |— 2 | + – | + – | X |2 —|—|—|—|—|—|— | | | | | 2 | – Example 3- Sample output for printBoard function Similarly, you can use the task 1’s readBoard function to achieve the same result: positivesColumn, negativesColumn, positivesRow , negativesRow , orientations, workingBoard = readBoard(“sampleFile1.txt”) printBoard(positivesColumn, negativesColumn, positivesRow , negativesRow , orientations, workingBoard) + | 3 | 1 | 2 | | | —|—|—|—|—|—|— | + – | X X | | —|—|—|—|—| |— 1 | X | X | | |2 —| | |—|—|—|— | X | X | | + |1 —|—|—|—|—| |— | + | | X X | – | —| | |—|—|—|— 2 | – | | | X |2 —|—|—|—|—| |— 2 | + – | + – | X |2 —|—|—|—|—|—|— | | | | | 2 | – Example 4- Sample output for printBoard function using readBoard function first Similar to MCD4710 – Introduction to Algorithms and Programming Part B: Helper functions (25 marks) In this part, you will code several helper functions that you will need later. Task 1: Safe placing (10 marks) Write the function canPlacePole(row, col, pole, workingBoard) to check if it is safe to place one given magnetic block’s pole for a particular coordinates. This function checks the surrounding squares and it will return a Boolean value. (See Figures 3 and 4 for more details.) row and col represent the coordinates of a given pole. pole is a single character representation for the given polarity (i.e. ‘+’ or ‘-‘) of one magnetic block’s end. If the surrounding squares in workingBoard allow the placement of the given pole of a magnetic block then the function will return True otherwise it will return False. See the examples below: >>> print(canPlacePole(1, 1, ‘+’, workingBoard)) False Example 4 – Example use of canPlacePole function for an existing workingBoard, positive (+) pole, row=1 and col=1 >>> print(canPlacePole(2, 3, ‘-’, workingBoard)) True Example 5- Example use of canPlacePole function for another existing workingBoard, negative (-) pole, row=2 and col=3 Hint: You can assume that square for the given coordinates is empty. Task 2: Block orientation (5 marks) Write the function getBlockOrientation(row, col, orientations) to get the orientation of a given slot as well as the coordinates of the other end of the slot, based on the given coordinates of a square and the orientations. row and col represent the coordinates of a given square. orientations, represents a list of lists with all pre- arranged slots on the board. The function will return “TB” for top-bottom (vertical) blocks and “LR” for left- right (horizontal) blocks, it will also return the coordinates of the opposite end for that block. It must follow this exact order: resultOrientation, oppositeRow, and oppositeCol. Note: The response for the slot’s orientation can only be “TB” or “LR”. >>> resultOrientation, oppositeRow, oppositeCol = getBlockOrientation (1, 1, orientations) >>> print (resultOrientation, oppositeRow, oppositeCol) ‘TB’ 0 1 Example 6- Example use of getBlockOrientation function with an existing orientations board, row=1, and col=1 Response Square Original Square MCD4710 – Introduction to Algorithms and Programming Task 3: Pole Count (5 marks) Write the function poleCount(rowOrCol, index, pole, workingBoard) to find the total number of positive (+) poles or negative (-) poles in a particular row or column. rowOrCol can only be ‘r’ or ‘c’ to indicate whether to check a given row or column, index indicates the index number for the row or column that function will check. Note: it must starts from zero. pole can only be ‘+’ or ‘-‘ to indicate which magnetic pole the function will be looking for; and consistent as before workingBoard represents a partial solution to the board as a list of lists. Example behaviour of this function is demonstrated below: + | 3 | 1 | 2 | | | —|—|—|—|—|—|— | + – | X X | | —|—|—|—|—| |— 1 | X | X | | |2 —| | |—|—|—|— | X | X | | + |1 —|—|—|—|—| |— | + | | X X | – | —| | |—|—|—|— 2 | – | | | X |2 —|—|—|—|—| |— 2 | + – | + – | X |2 —|—|—|—|—|—|— | | | | | 2 | – >>> workingBoard = [ [‘+’, ‘-‘, ‘X’, ‘X’, ‘E’], [‘X’, ‘X’, ‘E’, ‘E’, ‘E’], [‘X’, ‘X’, ‘E’, ‘E’, ‘+’], [‘+’, ‘E’, ‘X’, ‘X’, ‘-‘], [‘-‘, ‘E’, ‘E’, ‘E’, ‘X’], [‘+’, ‘-‘, ‘+’, ‘-‘, ‘X’] ] >>> print(poleCount (‘r’,5,’+’, workingBoard)) 2 >>> print(poleCount (‘r’,4,’-‘, workingBoard)) 1 >>> print(poleCount (‘c’,4,’-‘, workingBoard)) 1 Example 7 – examples of poleCount function MCD4710 – Introduction to Algorithms and Programming Task 4: Random Magnetic Pole Distribution (5 marks) Write the function randomPoleFlip(alist, percentage, flipValue) to randomly swaps a percentage of elements from alist (which can represent one of positivesColumn, negativesColumn, positivesRow, or negativesRow) with the flipValue. The number of elements that needs to be flipped is defined by the floor of percentage times the length of the aList. alist=[1,2,3,4,5,6,7,8,9,10] randomPoleFlip(alist,0.5,-1) print(alist) [1, -1, -1, 4, 5, 6, -1, -1, 9, -1] Example 8 – In the example above, 50% of the elements are flipped to -1. alist=[1,2,3,4,5,6,7,8,9,10] randomPoleFlip(alist,0.35,-1) print(alist) [-1, 2, -1, 4, 5, 6, 7, 8, 9, -1] Example 9 – In the example above, 3 elements are flipped because the function uses floor of 0.35
* len(alist). MCD4710 – Introduction to Algorithms and Programming Part C: Board Generation Functions (30 marks) Task 1: Orientations generation (10 marks) In this part you will write the function orientationsGenerator(M,N) to randomly generate the orientations as a list of lists for a board of size M x N. The procedure of generating the orientations is as follows: (Please note: M must be an even number, otherwise this procedure cannot be done). 1. The function starts with generating an M by N board with all orientations set as vertical blocks. See example below: [[‘T’, ‘T’, ‘T’, ‘T’, ‘T’], [‘B’, ‘B’, ‘B’, ‘B’, ‘B’], [‘T’, ‘T’, ‘T’, ‘T’, ‘T’], [‘B’, ‘B’, ‘B’, ‘B’, ‘B’]] Example 10 – step 1 orientations list when M=4 and N=5 2. The function continues by picking a random block: a. If it is a LR block, check the block that is immediately above it. If it is also an LR block and it is perfectly aligned with the picked block then change both blocks to become TB blocks. If it is not possible to do this with the top block, then try with the bottom block. b. If it is a TB block, check the block that is immediately to its left. If it is also a TB block and it is perfectly aligned with the picked block then change both blocks to become LR blocks. If it is not possible to do this with the left block, then try with the right block. c. If the blocks are not of the same type or not aligned then you will go to the next step. 3. Repeat the process at least 1000 times to make certain it is sufficiently random. See the figure below of how this procedure is done. Figure 5 – Orientations Generation Sample Process 4. Return orientations as a list of lists When this block is selected randomly it will be skipped since no TB block is adjacent to it. MCD4710 – Introduction to Algorithms and Programming Example behaviour of this function is demonstrated below (note the result are random): M=4 N=5 print(orientationsGenerator(M, N)) [[‘T’, ‘L’, ‘R’, ‘T’, ‘T’], [‘B’, ‘T’, ‘T’, ‘B’, ‘B’], [‘T’, ‘B’, ‘B’, ‘T’, ‘T’], [‘B’, ‘L’, ‘R’, ‘B’, ‘B’]] M=6 N=5 print(orientationsGenerator(M, N)) [[‘L’, ‘R’, ‘T’, ‘L’, ‘R’], [‘L’, ‘R’, ‘B’, ‘L’, ‘R’], [‘L’, ‘R’, ‘L’, ‘R’, ‘T’], [‘L’, ‘R’, ‘T’, ‘T’, ‘B’], [‘T’, ‘T’, ‘B’, ‘B’, ‘T’], [‘B’, ‘B’, ‘L’, ‘R’, ‘B’]] Example 11 – Two example outputs of orientationsGenerator functions Hint: You can use the printBoard function from Part A from a better display of the orientations. Task 2: Filling board with magnets (10 marks) Write the function fillWithMagnets(orientations), that creates a board that is full of magnet blocks. You need to use the helper functions from PART B and the process must follow the following steps: 1. Create an empty workingBoard. 2. It will then scan each row of orientations from top left corner row by row to the bottom right corner to fill the corresponding slots in the board with magnet blocks. Check if there is an existing pole present in the square that is being checked. If there is a block present, skip to the next square. Otherwise: 2.1. For an LR block: I. You need to check if it is safe to place a positive (+) pole in the left (‘L’) square of the block. If safe, place it and then negative (–) pole in the right (‘R’) square of the same block. II. Otherwise place the negative (-) pole in the left square and the positive (+) pole in the right square of the same block. 2.2. For a TB block: I. You need to check if it is safe to place a positive (+) pole in the top (‘T’) part of the block. If safe, place the positive (+) pole in top square and the negative (–) pole in bottom (‘B’) square of the same block. II. Otherwise place the negative (-) pole in top square and the positive (+) pole in the bottom square of the same block. Note: Here you must check individual squares (i.e. single end of a block). You need to use your canPlacePole and getBlockOrientation functions from PART B. 3. Return the resulting workingBoard MCD4710 – Introduction to Algorithms and Programming The behaviour of this function is as following: positivesColumn = [-1, -1, -1, -1, -1] negativesColumn = [-1, -1, -1, -1, -1] positivesRow = [-1, -1, -1, -1, -1] negativesRow = [-1, -1, -1, -1, -1] orientations = [ [‘L’, ‘R’, ‘L’, ‘R’, ‘T’], [‘T’, ‘T’, ‘L’, ‘R’, ‘B’], [‘B’, ‘B’, ‘L’, ‘R’, ‘T’], [‘T’, ‘T’, ‘L’, ‘R’, ‘B’], [‘B’, ‘B’, ‘L’, ‘R’, ‘T’], [‘L’, ‘R’, ‘L’, ‘R’, ‘B’] ] workingBoard= fillWithMagnets(orientations) printBoard(positivesColumn, negativesColumn, positivesRow , negativesRow , orientations, workingBoard) + | | | | | | —|—|—|—|—|—|— | + – | + – | + | —|—|—|—|—| |— | – | + | – + | – | —| | |—|—|—|— | + | – | + – | + | —|—|—|—|—| |— | – | + | – + | – | —| | |—|—|—|— | + | – | + – | + | —|—|—|—|—| |— | – + | – + | – | —|—|—|—|—|—|— | | | | | | – Example 12 – Example use of fillWithMagnets function Task 3: Generating random new board (10 marks) Write the function randomNewBoard (M,N). This function uses the previous functions to create a new random boardand and returns positivesColumn, negativesColumn, positivesRow, negativesRow , workingBoard, and orientations. The procedure of generating a random board must follow these steps: 1. Generate the orientations board of size M x N randomly. Note: use orientationsGenerator function for this. 2. Fill the board with magnet blocks. Note: use fillWithMagnets function for this. 3. Randomly replace 30% of the blocks with blank blocks (‘X’ blocks) 4. Generate the resulting positivesColumn, negativesColumn, positivesRow, and negativesRow lists. Note: use poleCount function for this. 5. Replace 50% of the numbers in each of positivesColumn, negativesColumn, positivesRow, and negativesRow lists with -1. Note: use randomPoleFlip function for this. MCD4710 – Introduction to Algorithms and Programming Example behaviour of this function is as below: M = 6 N = 5 positivesColumn, negativesColumn, positivesRow, and negativesRow, workingBoard, orientations = randomNewBoard (M,N) printBoard(positivesColumn, negativesColumn, positivesRow , negativesRow , orientations, workingBoard) + | 1 | | | 3 | 2 | —|—|—|—|—|—|— | X X | + | – + | —|—|—| |—|—|— 2 | – | + | – | + – | —| | |—|—|—|— | + | – | + | – + |2 —|—|—| |—|—|— | X X | – | + – | —|—|—|—|—|—|— 1 | X | – | + | X X |1 —| | | |—|—|— 2 | X | + | – | + – |2 —|—|—|—|—|—|— | | | 3 | 2 | 3 | – Example 13 – Example use of randomNewBoard function (note: The generated board will change with every run) Part D: Decomposition, Variable names and code Documentation (10 marks) Marks will be allocated for good use of variable names, code documentation and proper decomposition.
