- May 15, 2020

莫纳什大学FIT1045Assignment3课业解析题意：分为三个Task。 Task1：这是一个排序任务，将每个数列集合的第一个作为枢轴，将原集合划分成小于、等于、大于枢轴的分布。要求是只在原始集合上面进行改变，且只有O（n）的复杂度。

Task2：任务是制作一个数独游戏，分为五个步骤。1.读取游戏网格文件，进行输出。2.根据数独规则检查插入位置是否有效。3.在第r行进行输入，如果r行中已经有了这个数字，则返回原始的网格游戏网格，否则返回插入了该值的网格（可能会有多个位置能插入该数字）。4.向网格中输入数字，输出所有匹配的结果。5.输入文本形式保存的游戏，输出正确的数独结果。

Task3：1.一条街道上相邻的住户不会同时购买商品，找到这条街上的最大的营业额。2.按照汉堡包的设定，判断一个输入是不是真的汉堡包。 解析：任务一可以设置几个指针表示三种数应该插入的位置，这样遍历一次数组就能够让它们处在正确的位置。任务二需要处理一个多维数组，判断同一行同一列的数字是否相同，同时还有一个文件读入的问题，将保存在文本中的数独游戏载入后输出正确的数独结果。任务三第一问可以采取动态规划，第二问是一个字符匹配的问题，任务可以考虑是三种括号的匹配问题（左括号只能匹配对应括号的右括号）。 涉及知识点：数组、字符处理。更多可加微信讨论微信号Ssss_970521pdf

FIT1045 Algorithms and programming in Python, S2-2019Assignment 3 (value 20%)Due: Sunday 20th October 2019, 11:55 pm.ObjectivesThe objectives of this assignment are:• To demonstrate the ability to implement algorithms using basic data structures and operations on them.• To gain experience in designing an algorithm for a given problem description and implementing thatalgorithm in Python.• To demonstrate an understanding of complexity, and to the ability to implement algorithms of a givencomplexity.Submission Procedure1. Save your files into a zip file called yourStudentID yourFirstName yourLastName.zip2. Submit your zip file containing your solution to Moodle.3. Your assignment will not be accepted unless it is a readable zip file.Important Note: Please ensure that you have read and understood the university’s policies on plagiarismand collusion available at http://www.monash.edu.au/students/policies/academic-integrity.html. Youwill be required to agree to these policies when you submit your assignment.A common mistake students make is to use Google to find solutions to the questions. Once you have seen asolution it is often difficult to come up with your own version. The best way to avoid making this mistake isto avoid using Google. You have been given all the tools you need in workshops. If you find you are stuck, feelfree to ask for assistance on Moodle, ensuring that you do not post your code.Marks: This assignment will be marked both by the correctness of your code and by an interview withyour lab demonstrator, to assess your understanding. This means that although the quality of your code(commenting, decomposition, good variable names etc.) will not be marked directly, it will help to write cleancode so that it is easier for you to understand and explain.This assignment has a total of 20 marks and contributes to 20% of your final mark. For each day an assignmentis late, the maximum achievable mark is reduced by 20% of the total. For example, if the assignment is late by3 days (including weekends), the highest achievable mark is 70% of 20, which is 14. Assignments submitted 7days after the due date will normally not be accepted.Detailed marking guides can be found at the end of each task. Marks are subtracted when you are unable toexplain your code via a code walk-through in the assessment interview. Readable code is the basis of aconvincing code walk-through.1Task 1: Ternary Sorts (4 Marks)Create a Python module called ternary.py. Within this module implement the following task. You may notimport any other libraries or modules.Task: Ternary Partition (4 Marks)Write a function ternary partition(lst) that partitions an unsorted list into three sections: smaller thanpivot, equal to pivot, larger than pivot.Input: an unsorted list containing one or more integers.Output: a pair of integers, where the first integer is the index of the final position of the pivot, and the secondinteger is the index of the first element that is larger than the pivot. The pivot should be the element inthe 0th position in the original list. To receive full marks the original list must be partitioned; however,the list is not returned.Examplesa) Let lst1=[3]. Calling ternary partition(lst1) returns (0,1), as after calling function lst1=[3], thusthe pivot section starts at 0 and ends at 1 (exclusive).b) Let lst2=[3,2,2,5,6,3,1,3]. Calling ternary partition(lst2) returns (3,6), as after calling functionlst2==[2,2,1,3,3,3,5,6] (or an approximation of this depending on the specifics of the implementation),thus the pivot section starts at 3 and ends at 6 (exclusive).c) Let lst3=[1,2,3]. Calling ternary partition(lst3) returns (0,1), as after calling function lst3==[1,2,3](or an approximation of this depending on the specifics of the implementation), thus the pivot section startsat 0 and ends at 1 (exclusive).To receive full marks, this function must have a complexity of O(N), where N=len(lst). This means sortingthe list then finding the pivot’s location in the list is not a viable solution.Marking Guide (total 4 marks)Marks are given for the correct behavior of ternary partition:(a) 1 mark for an implementation that does not change the original list and without a complexity of O(N);(b) 3 marks for an implementation that does not change the original list and has a best and worst-casecomplexity of O(N);(c) 4 marks for an implementation that changes the given list to reflect the partitioning (the list is changed’in place’) and that has a best and worst-case complexity of O(N).Note: marks will be deducted for including print statements or for including function calls outside of functiondefinitions.2Task 2: Sudoku (10 Marks)Sudoku is a logic-based combinatorial number-placement puzzle. The objective is to fill a x2 ∗ x2 grid withdigits so that each column, each row, and each of the x × x subgrids that compose the grid contain all of thedigits from 1 to x2. (For instance, a 9 ∗ 9 grid would contain nine 3 ∗ 3 subgrids.) The puzzle setter provides apartially completed grid, which for a well-posed puzzle has a single solution.1(a) An exemplary Sudoku puzzle … (b) … and its solutionCreate a Python module called sudoku.py. Within this module implement the following five tasks. You areencouraged to decompose the given tasks into additional functions. You may import deepcopy from copy. Youmay not import any other libraries or modules.To assist with your implementation of the following tasks, you may use the following function subgrid values.This function takes a n×n sudoku grid, a row coordinate, and a column coordinate, and returns a list containingthe n values of the subgrid that the item at the coordinates belongs to.def subgrid_values(grid, row, col):val = []#get dimension of inner boxn = int(len(grid)**(0.5))#get starting row and starting colr = (row//n)*nc = (col//n)*nfor i in range(r, r+n):for j in range(c, c+n):val.append(grid[i][j])return valPart A: Get Grid (1 Mark)Write a function grid from file(file name) that reads in a file containing a sudoku grid and returns thecontents of the file as a Python-readable table.Input: a file name file name, where the file contains n lines, and each line contains n entries separated bycommas. Each entry will either be a positive integer, or the letter ‘x’.Output: a table represented as a nested list, where each entry in the orignal file is an element in the table,and all numbers have been converted to integers.Examplesa) Calling grid from file(‘gridA.txt’) returns:[ [‘x’,‘x’,1,‘x’],[4,‘x’,‘x’,‘x’],[‘x’,‘x’,‘x’,2],[‘x’,3,‘x’,‘x’] ]b) Calling grid from file(‘gridB.txt’) returns:1Description adapted from Wikipedia. Read more here: https://en.wikipedia.org/wiki/Sudoku.3[ [1,‘x’,9,‘x’,‘x’,‘x’,‘x’,6,‘x’],[8,4,‘x’,‘x’,1,‘x’,‘x’,7,5],[‘x’,‘x’,2,‘x’,‘x’,3,‘x’,‘x’,4],[‘x’,‘x’,8,3,2,1,‘x’,4,7],[‘x’,‘x’,5,‘x’,‘x’,‘x’,6,‘x’,‘x’],[4,2,‘x’,6,9,5,8,‘x’,‘x’],[7,‘x’,‘x’,1,‘x’,‘x’,4,‘x’,‘x’],[6,9,‘x’,‘x’,8,‘x’,‘x’,5,3],[‘x’,5,‘x’,‘x’,‘x’,‘x’,7,‘x’,9] ]Part B: Valid Entry (1 Mark)Write a function valid entry(grid, num, r, c) that determines whether a particular value can be enteredat a particular location in a valid grid, while maintaining validity.Input: a nested list grid, that represents an n × n sudoku grid; each item in the inner list is either an integer(example 13), or the string ‘x’; a positive integer num, where 0 < num ≤ n; and two non-negative integersr and c that represent the row and column that num will be inserted, where 0 ≤ r; c < n. You may assumegrid[r][c]==‘x’.Output: a boolean True if the insertion is valid; otherwise False. For the insertion to be valid, it must resultin a grid that does not contain duplicate numbers in any row, any column, or any subgrid.Examplesgrid = [ [1,‘x’,‘x’,‘x’],[‘x’,‘x’,‘x’,‘x’],[‘x’,‘x’,1,‘x’],[‘x’,‘x’,‘x’,‘x’] ]a) Calling valid entry(grid, 1,1,3) returns True.b) Calling valid entry(grid, 1,0,3) returns False, because there would be two 1s in row 0.c) Calling valid entry(grid, 1,1,2) returns False, because there would be two 1s in column 2.d) Calling valid entry(grid, 1,3,3) returns False, because there would be two 1s in the bottom left 2 ∗ 2subgrid.Part C: Enter Number In Row (2 Marks)Write a function grids augmented in row(grid,num,r) that returns the complete list of valid augmentedgrids, where each grid contains num in row r.Input: a nested list grid, that represents a valid n × n sudoku grid; each item in the inner list is either aninteger (example 27), or the string ‘x’; a positive integer num, where 0 < num ≤ n; and a non-negativeinteger r, where 0 ≤ r < n.Output: a nested list containing all augmented sudoku grids such that each grid is valid, and each gridcontains num in row r. If num is in row r in the original grid, return a list containing the original grid. Ifthere is no way to augment the given grid to create a valid grid where num is in row r, return an emptylist.Remember that you may import deepcopy from copy.Exampleslite_grid = [ [1,‘x’,‘x’,‘x’],[‘x’,‘x’,‘x’,‘x’],[‘x’,‘x’,‘x’,‘x’],[‘x’,2,‘x’,‘x’] ]full_grid = [ [2,‘x’,‘x’,‘x’],[‘x’,3,2,4],[‘x’,‘x’,4,2],4[1,2,3,‘x’] ]grid_A = [ [‘x’,‘x’,1,‘x’],[4,‘x’,‘x’,‘x’],[‘x’,‘x’,‘x’,2],[‘x’,3,‘x’,‘x’] ]a) Calling grids augmented in row(lite grid,1,0) returns:[#note there is already a 1 in row 0, so returns list containing original grid[ [1,‘x’,‘x’,‘x’],[‘x’,‘x’,‘x’,‘x’],[‘x’,‘x’,‘x’,‘x’],[‘x’,2,‘x’,‘x’] ]]b) Calling grids augmented in row(lite grid,1,1) returns:[[ [1,‘x’,‘x’,‘x’],[‘x’,‘x’,1,‘x’], #note there is now a 1 in row 1[‘x’,‘x’,‘x’,‘x’],[‘x’,2,‘x’,‘x’] ],[ [1,‘x’,‘x’,‘x’],[‘x’,‘x’,‘x’,1], #note there is now a 1 in row 1[‘x’,‘x’,‘x’,‘x’],[‘x’,2,‘x’,‘x’] ]]c) Calling grids augmented in row(full grid,1,1) returns [], because there is no valid way to insert a 1 inrow 1 of full grid.d) Calling grids augmented in row(grid A,1,2) returns:[[ [‘x’,‘x’,1,‘x’],[4,‘x’,‘x’,‘x’],[1,‘x’,‘x’,2], #note there is now a 1 in row 2[‘x’,3,‘x’,‘x’] ] ,[ [‘x’,‘x’,1,‘x’],[4,‘x’,‘x’,‘x’],[‘x’,1,‘x’,2], #note there is now a 1 in row 2[‘x’,3,‘x’,‘x’] ]]Part D: Enter Number (3 Marks)Write a function grids augmented with number(grid,num) that returns a list of valid n × n grids, where eachgrid contains n nums. (I.e. if given a 9 ∗ 9 grid, and num = 3, each grid returned must contain nine 3’s.)Input: a nested list grid, that represents a valid n × n sudoku grid; each item in the inner list is either aninteger (example 13), or the string ‘x’; and a positive integer num, where 0 < num ≤ n.Output: a nested list containing all valid sudoku grids where each grid contains n nums. If there is no way toaugment the given grid to create a valid sudoku grid containing n nums, return an empty list.5Examplesa) Calling grids augmented with number(lite grid,1) returns:[#note there are now 1s in every row, column, and inner square in both grids[ [1,‘x’,‘x’,‘x’],[‘x’,‘x’,1,‘x’],[‘x’,1,‘x’,‘x’],[‘x’,2,‘x’,1] ] ,[ [1,‘x’,‘x’,‘x’],[‘x’,‘x’,‘x’,1],[‘x’,1,‘x’,‘x’],[‘x’,2,1,‘x’] ]]b) Calling grids augmented with number(full grid,1) returns [], because there is no valid way to modifyfull grid so that it contains four 1s.c) Calling grids augmented with number(grid A,1) returns:[[ [‘x’,‘x’,1,‘x’],[4,1,‘x’,‘x’],[1,‘x’,‘x’,2],[‘x’,3,‘x’,1] ]]Part E: Solve Sudoku (3 Marks)Write a function solve sudoku(file name) that finds the solution for the given sudoku.Input: a file name file name, where the file contains n lines, and each line contains n entries separated bycommas. Each entry will either be a positive integer, or the letter ‘x’.Output: a nested list representing a completed sudoku grid. You may assume the file given will always containexactly one valid solution.Note: you may find the functions that you are required to write in parts C and D useful in solving part E;however, you may find it more natural to solve part E using an alternative approach. If this is the case, notethat you are not required to use parts C and D for your solution to part E.Examplesa) Calling solve sudoku(‘gridA.txt’) returns:[ [3,2,1,4],[4,1,2,3],[1,4,3,2],[2,3,4,1] ]b) Calling solve sudoku(‘gridB.txt’) returns:[ [1, 3, 9, 5, 7, 4, 2, 6, 8],[8, 4, 6, 9, 1, 2, 3, 7, 5],[5, 7, 2, 8, 6, 3, 9, 1, 4],[9, 6, 8, 3, 2, 1, 5, 4, 7],[3, 1, 5, 7, 4, 8, 6, 9, 2],[4, 2, 7, 6, 9, 5, 8, 3, 1],[7, 8, 3, 1, 5, 9, 4, 2, 6],[6, 9, 4, 2, 8, 7, 1, 5, 3],[2, 5, 1, 4, 3, 6, 7, 8, 9] ]6Marking Guide (total 10 marks)Marks are given for the correct behavior of the different functions:(a) 1 mark for grid from file.(b) 1 mark for valid entry.(c) 2 marks for grids augmented in row.(d) 3 marks for grids augmented with number.(e) 3 marks for solve sudoku.Note: marks will be deducted for including print statements or for including function calls outside of functiondefinitions.7Task 3: Jobs (6 Marks)Create a Python module called jobs.py. Within this module implement the following two tasks. You may notimport any other libraries or modules.Part A: Salesperson (3 Marks)You are an unscrupulous salesperson who sells devices that allow a household to use their neighbours’ wi-fi forfree. Due to the nature of the product you sell, it is never possible to sell to neighbours. Every day you find anew street at which to sell your devices. You are very good at your job, and know from market research exactlyhow much each household would be willing to pay.Write a function max sales(street) that finds the maximum amount of sales you can make for a givenstreet.Input: a list street of non-negative integers that represents the street you are visiting; each integer representsthe amount of money the ith household would be willing to pay; the ith household is neighbours to theith - 1 and ith + 1 household. The first and last household are not neighbours.Output: an integer that is the maximum amount of sales you can expect to make on that street.Examplesa) Calling max sales([2,3,10,5,6,0,4,12,6]) returns 30, because you could sell to the first, third, fifth, andeighth house on the street, thus making a sale of 2 + 10 + 6 + 12 = 30.b) Calling max sales([]) returns 0, because you cannot make any sales when selling to a street with no houses.Part B: Burgerperson (3 Marks)Your sales business was shutdown by the IEEE and you have had to get a job at a hip burger joint. This burgerjoint is different from most - the only ingredient used in the burgers is bread. Your job is to check the breadstacks made in the kitchen are actually burgers.For a bread stack to be a burger it must follow two rules: first, any open piece of bread must be followedby a matching closing piece of bread; second, any open-close pair may contain a stack of bread between them,provided the stack is also a burger. There are three different kinds of bread: brioche (open brioche is ‘ob’,closed is ‘cb’), wholemeal (‘ow’, ‘cw’), and rye (‘or’, ‘cr’).Write a function is burger(breads) that determines whether a stack of bread is a burger.Input: a non-empty list of strings breads that represents the bread stack you are checking; the possible stringsare: ‘ob’, ‘cb’, ‘ow’, ‘cw’, ‘or’, ‘cr’.Output: a boolean, True if the bread stack is a burger; otherwise False. A bread stack is a burger if eachopen piece of bread is followed by a matching closed piece of bread, and there is either nothing betweenthe opening and closing bread, or there is one or more burgers between the opening and closing bread.Examplesa) Calling is burger([‘ob’]) returns False, because the opening brioche does not have a closing brioche.b) Calling is burger([‘ob’,‘cb’]) returns True.c) Calling is burger([‘ob’,‘or’,‘cb’]) returns False, because the brioche bun does not contain a validburger.d) Calling is burger([‘ob’,‘or’,‘cr’,‘cb’]) returns True.e) Calling is burger([‘ob’,‘or’,‘cb’,‘cr’]) returns False, because the brioche bun does not contain avalid burger, and the rye bun does not contain a valid burger.f) Calling is burger([‘ob’,‘or’,‘cr’,‘ob’,‘cb’,‘cb’]) returns True.g) Calling is burger([‘or’,‘cr’,‘ob’,‘cb’]) returns True.8Marking Guide (total 6 marks)Marks are given for the correct behavior of the different functions:(a) 3 marks for max sales.(b) 3 marks for is burger.Note: marks will be deducted for including print statements or for including function calls outside of functiondefinitions.9