MCD4710代写、Python语言编程

日期：2021-11-20 05:00

MCD4710 - Introduction to Algorithms and Programming

Assignment 1 (8%)

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 Implementing problem solving strategies

o Recognizing the relationship between a problem description and program design

o Decomposing code into functions in Python.

SubmissionProcedure

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 file(s) into a zip file called YourStudentID.zip

3. Submit your zip file containing your entire submission to Moodle.

LateSubmission

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.

ImportantNotes

● 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-IntegrityDiplomas-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.

2

MCD4710 - Introduction to Algorithms and Programming

Assignment 1 (8%)

Assignmentcodeinterview

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.

Task 1: Display Sudoku - 5 marks

? Displaying all rows of the field in individual lines (1 mark)

? Displaying spaces instead of zeroes and no commas (1 mark)

? Visualisation of subgrid boundaries for k==2 (1 mark)

? Visualisation of subgrid boundaries for arbitrary k (not necessarily aligned columns for k > 2) (1 mark)

? If function correctly aligns columns for k = 4 by replacing values 10 to 16 by letters 'A' to 'G' (1 mark)

Task 2: Implement the rules - 5 marks

? Correct implementation of subgrid values (2 mark)

? Correct implementation of options (1 mark)

? Integration into the play function (1 mark)

? For success message when board is solved (1 mark)

Task 3: Undo – 2 marks

? Restart functionality (1 mark)

? Undo functionality (1 mark)

Task 4: Hints - 3 marks

? Printing a hint and explaining how the hint is chosen in the docstring (2 marks)

? Printing board with marker on the field corresponding to the hint (1 mark)

Programming practice – 2 marks

? Decomposition (1 mark)

? Variable names and code Documentation (1 mark)

Total: 17 marks

3

MCD4710 - Introduction to Algorithms and Programming

Assignment 1 (8%)

Sudoku

Sudoku is a puzzle game for one player where one has to fill up a regular grid of fields (game board) with

numbers. Typically a Sudoku board is 9 times 9 fields, but in this assignment we will write functions that can

work in principle with arbitrary sized n times n boards as long as n = k**2 for some integer k > 1.

Conceptually, the board is composed of k×k subgrids (each consisting of k×k fields). The objective of the

player is to fill all fields with the numbers 1 to n (inclusive) such that

? no column of the grid contains the same number more than once

? no row of the grid contains the same number more than once

? none of the k**2 subgrids contains the same number more than once

See https://en.wikipedia.org/wiki/Sudoku for more information.

In this assignment, we represent a Sudoku board by a n×n table where each entry is either a number from

1 to n (inclusive) or 0 representing that the corresponding field is still empty. For example, a small game board

with n=4 (and k=2) with four fields already filled could be defined as follows:

>>> small = [[0, 0, 1, 0],

... [4, 0, 0, 0],

... [0, 0, 0, 2],

... [0, 3, 0, 0]]

An example for the typical 9x9 size is:

>>> big = [[0, 0, 0, 0, 0, 0, 0, 0, 0],

... [4, 0, 0, 7, 8, 9, 0, 0, 0],

... [7, 8, 0, 0, 0, 0, 0, 5, 6],

... [0, 2, 0, 3, 6, 0, 8, 0, 0],

... [0, 0, 5, 0, 0, 7, 0, 1, 0],

... [8, 0, 0, 2, 0, 0, 0, 0, 5],

... [0, 0, 1, 6, 4, 0, 9, 7, 0],

... [0, 0, 0, 9, 0, 0, 0, 0, 0],

... [0, 0, 0, 0, 3, 0, 0, 0, 2]]

Finally, an example of a giant board with 4x4 subgrids each of size 4x4 is:

>>> giant = [[ 0, 5, 0, 0, 0, 4, 0, 8, 0, 6, 0, 0, 0, 0, 9, 16],

... [ 1, 0, 0, 0, 0, 0, 0, 13, 4, 0, 0, 7, 15, 0, 8, 0],

... [13, 0, 0, 0, 0, 7, 3, 0, 0, 0, 0, 9, 5, 10, 0, 0],

... [ 0, 11, 12, 15, 10, 0, 0, 0, 0, 0, 5, 0, 3, 4, 0, 13],

... [15, 0, 1, 3, 0, 0, 7, 2, 0, 0, 0, 0, 0, 5, 0, 0],

... [ 0, 0, 0, 12, 0, 3, 0, 5, 0, 11, 0, 14, 0, 0, 0, 9],

... [ 4, 7, 0, 0, 0, 0, 0, 0, 12, 0, 15, 16, 0, 0, 0, 0],

... [ 0, 0, 0, 0, 14, 0, 15, 0, 6, 9, 0, 0, 0, 0, 12, 0],

... [ 3, 0, 15, 4, 0, 13, 14, 0, 0, 0, 0, 1, 0, 0, 7, 8],

... [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 10, 0, 0, 0, 0],

... [11, 0, 16, 10, 0, 0, 0, 0, 0, 7, 0, 0, 0, 3, 5, 0],

... [ 0, 0, 13, 0, 0, 0, 0, 0, 14, 0, 15, 16, 0, 9, 0, 1],

... [ 9, 0, 2, 0, 0, 14, 0, 4, 8, 0, 0, 0, 0, 0, 0, 0],

... [ 0, 14, 0, 0, 0, 0, 0, 10, 9, 0, 3, 0, 0, 0, 1, 7],

... [ 8, 0, 0, 0, 16, 0, 0, 1, 2, 14, 11, 4, 0, 0, 0, 3],

... [ 0, 0, 0, 1, 0, 0, 5, 0, 0, 16, 0, 6, 0, 12, 0, 0]]

4

MCD4710 - Introduction to Algorithms and Programming

Assignment 1 (8%)

Play Sudoku

Task 1: Display Sudoku (5 marks)

The function print_board(board) from the template accepts as input parameter a game board and prints it.

Improve the function such that each row of the board is printed in its own line with aligned column entries, zeroes

replaced by spaces, and the subgrids are visible. For example, the output for the above small and big boards could be:

>>> print_board(small)

-------

| |1 |

|4 | |

-------

| | 2|

| 3| |

-------

>>> print_board(big)

-------------

| | | |

|4 |789| |

|78 | | 56|

-------------

| 2 |36 |8 |

| 5| 7| 1 |

|8 |2 | 5|

-------------

| 1|64 |97 |

| |9 | |

| | 3 | 2|

-------------

For k=4, it is more complicated to have the columns aligned. Thus a nicer overview is to use letter codes

for the numbers 10 to 16, where 10 =A, 11 = B, …, 16 = G, For example:

>>> print_board(giant)

---------------------

| 5 | 4 8| 6 | 9G|

|1 | D|4 7|F 8 |

|D | 73 | 9|5A |

| BCF|A | 5 |34 D|

---------------------

|F 13| 72| | 5 |

| C| 3 5| B E| 9|

|47 | |C FG| |

| |E F |69 | C |

---------------------

|3 F4| DE | 1| 78|

| | | 9A| |

|B GA| | 7 | 35 |

| D | |E FG| 9 1|

---------------------

|9 2 | E 4|8 | |

| E | A|9 3 | 17|

|8 |G 1|2EB4| 3|

| 1| 5 | G 6| C |

---------------------

Hint: You may need to use print(x, end=‘’) to avoid printing new line with each print.

5

MCD4710 - Introduction to Algorithms and Programming

Assignment 1 (8%)

Task 2: Implement the rules (5 marks)

The function play(board) provided in the template accepts as input a Sudoku board and allows to play a

game of Sudoku via the console. When you run the function you will find that it has the following bevaviour:

? When the function is called, it prints the input game board (via the function print_board)

? Then it goes into an infinite loop where it first waits for user input (via the built-in input function)

and then proceeds as follows:

– On input ‘q’ or ‘quit’ the loop ends.

– On inputting three integers i j x (separated by a single whitespace character), it updates the game

board by setting the value of field (i, j) to x and prints the updated board.

– On input ‘n’ k d (the character ‘n’ followed by integers k and d, separated by a single whitespace

character), it loads a new game board of specified size k

2

and difficulty d (with some limited available

choices for k and d).

What is unsatisfactory is that the function allows the player to modify the board with invalid moves. Also,

the program does not notice when the Sudoku has been solved. In short, it doesn’t actually k now how Sudoku

works. Let’s change that.

Subgrid values:

Write a function subgrid_values(board, r, c) that accepts as input parameters a Sudoku board, board, a

row index r, and a column index c, and that produces as output a list of all numbers that are present in the subgrid of

the board that row r and column c belong to. For example:

>>> subgrid_values(small, 1, 3)

[1]

>>> subgrid_values(big, 4, 5)

[3, 6, 7, 2]

>>> subgrid_values(giant, 4, 5)

[7, 2, 3, 5, 14, 15]

Options:

Write a function options(board, r, c) that accepts as input parameters a game board (board), an integer

row index r, and an integer column index c and that produces as output a list of all possible values that a player is

allowed to place into field (r, c) of the board. For example:

>>> options(small, 0, 0)

[2, 3]

>>> options(big, 6, 8)

[3, 8]

>>> options(giant, 1, 5)

[2, 5, 6, 9, 11, 12, 16]

Now modify the play function that on user input of three numbers i j x, it only modifies and reprints the board if x is a

legal value for the field (i, j) in the current board and otherwise prints an error message. Finally, let the play function

print a success message when, at the beginning of the loop, the sudoku is solved (i.e., there are no empty fields left)

6

MCD4710 - Introduction to Algorithms and Programming

Assignment 1 (8%)

Task 3: Undo (2 marks)

Extend the behaviour of the play function such that:

? on input ‘r’ or ‘restart’ the game restarts with the last loaded game board ( the board that was loaded with the command

n),

? on input ‘u’ or ‘undo’ the last move is taken back.

Task 4: Hints (3 marks)

Extend the behaviour of the play function such that on input ‘h’ or ‘hint’ it prints the coordinates of a

field for which it is easiest to see the correct value. Think of meaningful ways to implement this functionality

and explain your approach in a docstring. The functionality should also reprint the board with the indicator

symbol ‘*’ at the position referred to by the hint.

For instance, when entering ‘h’, the function could print the following to the console (this is just an

illustration; your function might behave differently):

-------------

| | | |

|4 |789| |

|78 | | 56|

-------------

| 2 |36 |8 |

| 5| *7| 1 |

|8 |2 | 5|

-------------

| 1|64 |97 |

| |9 | |

| | 3 | 2|

-------------

(4, 4)