代做Lawnmower Project 1代做Python编程

2024.09.10 - 首页 >> CS

In this project, you will work on a problem called Shaanan’s Lawnmower. Completing the project will give you the opportunity to improve your understanding of Python and allow you to develop your skills in representing and solving real-world problems using programming.

Your task is to:

· Question 1 (3 marks): Help Shaanan select the best lawnmower from all possible options in different stores.

· Question 2 (3 marks): Given a path, determine what Shaanan’s backyard will be like after he mowed through this path.

· Question 3 (4 marks): Given one of the two “mowing strategies”, design the path for Shaanan’s mowing task.

· Question 4 (5 marks): Given a mowing strategy that involves four people mowing together, determine the paths of these mowers at a specific point in time.

· Optional Question 5 (bonus 2 marks): Given a lawn, find a path that is as short as possible.

A detailed description of each question is provided in its corresponding problem slide.

In each Grok worksheet that you've done before, you’re awarded a green diamond as long as you pass all the test cases. In this project, there are some additional criteria. Therefore, you need to ensure that:

· Approach: Your code structure is intuitive, easy to understand and not overly complicated. You should use helper functions when needed.

· Style: Your code is formatted well with no PEP8 warnings, no “magic” numbers or strings, and good variable names.

· Comments: Your docstrings and comments have the correct format with the appropriate level of detail.

Regarding test cases, there will be two types of test cases that you will be marked against:

· Hidden: similar to the ones in your Grok worksheet. If you fail a hidden test, you will be notified.

· Assessed: the additional, “hidden” hidden test cases that will not show up when you hit the “mark” button. You won't know if you pass them or not.

Each question in the project is independent, so you don't have to solve the current question before attempting the next question. One thing to note is that Q3 and Q4 share some similarities, so you can approach them in a similar way (if you want).

Now you can start solving the problems. Good luck!

Errata:

· 27th Aug Q4: the docstring of visualise_paths should be "orange, green, blue and purple" rather than "orange, blue, green and purple".

Question 1: Getting the Best Lawnmower

Shaanan just bought a new house, and it’s time to buy a lawnmower for the house! He wants to buy the one that has the best power-to-dollar ratio (i.e. biggest value of power divided by price).

Your Task

Shaanan knows the power of all lawnmowers available in the market (see optionsbelow). He also has the catelogue of all the stores that may or may not sell lawnmowers (see store_catalogues below). Write a function best_lawnmower(options, store_catalogues) to help Shaanan find the best lawnmower from all the available options in different stores' catalogue!

Input:

· options: a dictionary with the name of a lawnmower as key, and its corresponding power as value. The key is of type str, and the value is of type int. Example: {"mower1": 20, "mower2": 30, "mower3": 5}

· store_catalogues: A dictionary whose keys are available stores' name, and each value is the store's corresponding catalogue. Each catalogue is itself a dictionary containing product (type str) and its corresponding price (type int or float). Example: {"TheBadBoys": {"mower2": 150, "markbook_pro": 1999},"Colas": {"egg": 7, "water": 2, "mower1": 119.5}, "Burnings":{"mower2": 150, "mower1": 100}}

Output: A 3-element tuple (i.e. (lawnmower, store, score)).

· The first element is the name of the best lawnmower;

· The second element is the store that Shaanan should buy this lawnmower from

· The third element is the score, which is the power-to-dollar ratio defined earlier. The score should be of type float, and you should use the round function to round it to two decimal places.

· Example output: ('mower1', 'Burnings', 0.2)

If there’s a tie in the rounded score, select the “smallest” store in alphanumeric order. If there’s still a tie, select the “smallest” lawnmower in alphanumeric order.

Reminder of how the dictionary works:

· Dictionaries store key-value pairs, where each key is unique in a dictionary and the key has to be immutable.

· To iterate through a dictionary, you can do something like for key, value inmy_dictionary.items():. Note that the variable name in this line of code is for illustration purpose only. You should have more descriptive variable names.

Assumptions you can make:

· The inputs are well-formatted with the correct type.

· The power of lawnmower options and the price of lawnmowers are both positive.

· options and store_catalogues are both non-empty.

· There will be at least one valid lawnmower option for you to return.

· Example calls:

· >>> ptions = {"mower1": 20, "mower2": 30, "mower3": 5}

· >>> store_catalogues = {"TheBadBoys": {"mower2": 150, "markbook_pro": 1999}, "Colas": {"egg": 7, "water": 2, "mower1": 119.5}, "Burnings": {"mower2": 150, "mower1": 100}}

· >>> print(best_lawnmower(options, store_catalogues))

· ('mower1', 'Burnings', 0.2)

Question 2: Mow the Backyard Through a Path

Now that Shaanan has his lawnmower, it’s time to start mowing the backyard!

We use a 2-D list of str to represent Shaanan’s backyard, which has a rectangle shape with the dimensions of row_dim * col_dim (Note: both are positive int). The value in the backyard 2-D list can be either "-" or "+", representing the grass being short or long, respectively. We can use a coordinate (containing two non-negative int) to locate the grass in the backyard, with (0, 0) being the top left corner, and (row_dim - 1,col_dim - 1) being the bottom right corner.

The image below is an illustration of a backyard, whose dimension is 3 * 4.

Shaanan drives the lawnmower through a path in the backyard to cut the grass short. The path is represented by a list of coordinates, such as [(0, 0), (0, 1), (1, 1),(2, 1), (2, 2), (2, 1)]. Note that a lawnmower is allowed to land on a piece of grass even if it is short.

There are some obvious rules for the path to be valid.

1. The entire path must be in the backyard. For example, (row_dim, col_dim) can not be part of the path.

2. The path has to be continuous, with the lawnmower only being able to move up, down, left of right for 1 unit for each step. For example, (0, 0) and (1, 1) can not be locations of two adjacent coordinates in the path.

Your Task

Write a function backyard_after_mowing(backyard, path).

Input:

· backyard: The 2-D list described earlier, represents the length of grass in Shaanan’s backyard by "-" and "+".

· path: A list of tuples representing all coordinates in a lawnmower's path.

Output: The updated backyard in its list representation after the lawnmower goes through this path. If the path is invalid, return None.

Assumptions you can make:

· The inputs are well-formatted with the correct type.

· The backyard contains only two possible string values: "-" and "+".

· The path is non-empty.

Example calls:

>>> backyard = [["-", "+", "-", "+"], ["-", "+", "-", "+"], ["-", "+", "+", "+"]]

>>> valid_path = [(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 1)]

>>> invalid_path_rule1 = [(0, 0), (1, 1), (2, 1), (2, 2)]

>>> invalid_path_rule2 = [(0, 0), (0, 1), (1, 1), (2, 1), (3, 1), (2, 1)]

>>> print(backyard_after_mowing(backyard, valid_path))

[['-', '-', '-', '+'], ['-', '-', '-', '+'], ['-', '-', '-', '+']]

>>> print(backyard_after_mowing(backyard, invalid_path_rule1))

None

>>> print(backyard_after_mowing(backyard, invalid_path_rule2))

None

Question 3: Complete a Path

Shaanan wants to make sure the grass on his lawn is of equal length. It means that each time Shaanan mows, he goes through a path covering the entire backyard with his lawnmower. Also, given he has to mow the entire lawn, he really wants to avoid any repetition (i.e., mowing the same piece of grass twice).

He comes up with two strategies to mow the lawn that will satisfy his requirement above:

· Strategy 1 - Back and Forth Path: start at the top left corner and go straight to the right. Every time he reaches the edge of the backyard, make a U-turn and continue mowing.

· Strategy 2 - Spiral Path: start at the top left corner and go clockwise through a spiral path until he reaches the centre with no more land to cover.

Your Task

Write a function complete_path(dimension, path_type).

Input:

· dimension: A 2-element tuple (row_dim, col_dim) signalling the dimension of the backyard (described in Q2).

· path_type: A str with value of either "back_and_forth" or "spiral", signalling the type of the path.

Output: The path as described above, depending on path_type. The format of the path is the same as in Q2. The returned path should contain every coordinate in the backyard, without duplication.

Assumptions you can make:

· The inputs are well-formatted with the correct type.

· The dimension tuple contains two int with positive values.

Example calls:

>>> print(complete_path((3, 4), "back_and_forth"))

[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (1, 2), (1, 1), (1, 0), (2, 0), (2, 1), (2, 2), (2, 3)]

>>> print(complete_path((3, 4), "spiral"))

[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (2, 1), (2, 0), (1, 0), (1, 1), (1, 2)]

Question 4: Mow Mow Mow Together!

Errata:

· 27th Aug: the docstring of visualise_paths should be "orange, green, blue and purple" rather than "orange, blue, green and purple".

Shaanan’s talent in lawnmowing is now well-known. The University of Melbourne offers him a part-time job – mowing South Lawn once per week!

Due to the size of South Lawn, Shaanan cannot complete the task himself. So he has to… kidnap three teaching fellows: Yige, Han, and Rose, to do the task with him. The step-by-step visualisation of them mowing the South Lawn is provided here, and the following paragraphs provide detailed description on how this works.

They all used the spiral strategy that Shaanan developed (see Q3). Their initial position and initial direction has been predetermined: Shaanan starts from the top left corner as before (will move to the right), Yige starts from the top right corner (will move downwards), Han starts from the bottom right corner (will move to the left), and Rose starts from the bottom left corner (will move upwards). No piece of lawn can be repeatedly mowed.

They start mowing at the time step 0. Then at each time step, each of the four people completes one of the three actions with their lawnmower:

· Move one step forward without turning (i.e., no change in direction).

· Turn clockwise and move one step forward. This action will only be selected if:

o moving one step forward without turning will result in the person immediately land on a coordinate that has already been mowed, AND

o after turning clockwise and move one step forward, the person immediately lands on a coordinate that has not been mowed)

· Do nothing. Select this action if the other two actions are not possible.

During each time step, Shaanan performs his action first, then Yige, then Han, then Rose.

Your Task

Write a function quad_clockwise_spiral_paths(dimension, time_step).

Input:

· dimension: same as in Q3.

· time_step: a non-negative int signalling the time step when mowing

Output: The function returns a list containing 4 paths, in the order of Shaanan’s, Yige’s, Han’s and Rose’s, at the time_step given.

Assumptions you can make:

· The inputs are well-formatted with the correct type.

· For this question, you can assume that in the dimension tuple (row_dim,col_dim) , row_dim and col_dim are no less than 2.

To help you visualise the result of your function, we create the function visualise_paths for you. See the example calls below.

Example calls:

>>> dimension = (7, 5)

>>> paths_t0 = quad_clockwise_spiral_paths(dimension, 0)

>>> paths_t3 = quad_clockwise_spiral_paths(dimension, 3)

>>> paths_t12 = quad_clockwise_spiral_paths(dimension, 12)

>>> print(paths_t0)

[[(0, 0)], [(0, 4)], [(6, 4)], [(6, 0)]]

>>> visualise_paths(paths_t0, dimension)

��⬜⬜⬜��

⬜⬜⬜⬜⬜

��⬜⬜⬜��

>>> print(paths_t3)

[[(0, 0), (0, 1), (0, 2), (0, 3)], [(0, 4), (1, 4), (2, 4), (3, 4)], [(6, 4), (6, 3), (6, 2), (6, 1)], [(6, 0), (5, 0), (4, 0), (3, 0)]]

>>> visualise_paths(paths_t3, dimension)

��

⬜⬜⬜⬜��

��⬜⬜⬜��

��⬜⬜⬜⬜

��

>>> print(paths_t12)

[[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3), (4, 2), (3, 2)], [(0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 4), (5, 3), (5, 2)], [(6, 4), (6, 3), (6, 2), (6, 1), (5, 1), (4, 1), (3, 1), (2, 1), (2, 2)], [(6, 0), (5, 0), (4, 0), (3, 0), (2, 0), (1, 0), (1, 1), (1, 2)]]

>>> visualise_paths(paths_t12, dimension)

��

Program.py

RANGE = '\U0001F7E7'

BLUE = '\U0001F7E6'

GREEN = '\U0001F7E9'

PURPLE = '\U0001F7EA'

WHITE = '\U00002B1C'

SQUARES = [ORANGE, GREEN, BLUE, PURPLE]

# ---------- DEFINE YOUR CONSTANTS AFTER THIS LINE ----------

# ---------- DEFINE YOUR CONSTANTS BEFORE THIS LINE ----------

def visualise_paths(paths, dimension):

'''Take a list with four paths and the dimension, print out the visualised

version of it. Shaanan, Yige, Han and Rose's path are printed out in

orange, green, blue and purple respectively. Unvisited coordinates are

printed in white.'''

row_dim, col_dim = dimension

backyard = [[WHITE for _ in range(col_dim)] for _ in range(row_dim)]

# create the backyard represented by coloured squares

for mower_i, mower_path in enumerate(paths):

for x, y in mower_path:

backyard[x][y] = SQUARES[mower_i]

# print out the backyard

for row in backyard:

line = ''

for col in row:

line += col

print(line)

# ------------- WRITE YOUR SOLUTION AFTER THIS LINE ---------------

Question 5: Ultimate Path (Optional)

Before you start, note that this is an optional bonus question. You should attempt this question after you are confident with your Q1 to Q4 submissions. Also since this is a bonus question, the teaching team will provide minimum support on this question compared to previous questions. If you are ready, keep reading and good luck!

Introduction

Shaanan’s popularity is now out of control. Everyone is calling him to help them with the mowing task!

As you can imagine, people’s backyards look quite different. Some are large, some are small, some only have long grass in the middle of the backyard, and some only have long grass at the edge… To save time, Shaanan has to look at their backyard and come up with the ultimate path.

In this question, you will help Shaanan come up with a path to cut all grass short. Because not all coordinate has long grass, you don't have to visit all coordinates in this question. You should think strategically, and come up with a path that is as short as possible.

Your Task

Write a function ultimate_path(backyard).

Input:

· backyard: same as in Q2.

Output:

· The path that can cut all grass short, with the type and requirement specified in Q2. In addition for this question, the path should start with coordinate (0, 0) and end with the coordinate (0, 0).

Assumptions you can make:

· See Q2

· Also, you can assume that the backyard contains long grass (i.e. "+").

· The backyard’s dimension is at least 2 * 2, and at most 20 * 20.

Marking Criteria

After you submit your code, we will test your submission with many possible backyard test cases and calculate the average standardised path length (ASPL). Given that N is the total number of test cases, i is the index of one test case and mi∗ni is the dimension of backyard i, your submission’s ASPL is calculated as :

ASPL=∑NiLiN,where Li=len(ultimate_path(backyardi))mi∗ni

To score your work, a class-wide tournament will be run on the ASPL. We will create a leaderboard ranking all submissions’ ASPL in increasing order. The mark you receive will be based on your rank in the cohort.

To be eligible for 2 bonus marks, you need to rank in the top 25% of submissions. To be eligible for 1 bonus mark, you need to rank in the top 50% of submissions.

For any test case i, if one of the below scenarios happens, you will be penalised:

· your code runs into an error

· your path did not cut all grass short

· your function ultimate_path runs for over 1 second for this test case

If your submission for test case i get penalised, the Li will be set to 5. However, if you see 0 as your score on gradescore, it means that we are not able to test your code (e.g. wrong file name or syntax errors etc.). You need to test your code before submitting it.

You can submit your solution multiple times, but only the last submission before the deadline counts.

How to Submit:

In order to facilitate a live leaderboard, entry to the tournament is via Gradescope, not Grok.

The following instructions assume you are using Grok as a "code editor" to work on Task 5, but it's equally possible to develop your program offline on your computer locally and upload directly if that's your preference.

Before continuing, make sure your entire Task 5 submission is self-contained within a single program.py file as submitting multiple files is not possible.

· Step 1. On Grok, click the ">" next to program.py to expand options for the respective file. Click on the "Download" button to download a copy of program.py to your computer (be careful not to click "Reset" as this will wipe saved progress in the file!)

· Step 2. Go to Gradescope by clicking here, or simply go to this url https://canvas.lms.unimelb.edu.au/courses/183294/external_tools/5945. If Gradescope does not load, consider changing the browser. If that still doesn't work, try visiting Gradescope website directly rather than through Canvas.

· Step 3. Click on the assignment named "Project1-Q5-Bonus", then submit the program.py file you downloaded. DO NOT CHANGE THE FILE NAME, otherwise the Gradescope autograder will not work. You will also be asked to provide a "Leaderboard Name" that other students will see in the public ranking (your real name is only visible to teaching staff).

· Step 4. Click the "Upload" button and your submission will be created. To verify that it has been successfully submitted, wait a few seconds for the autograder to finish running your code. If successful, you will see something like:

Note that the total points and autograder score are not your marks, they are your submission’s ASPL.

If you click on the "Leaderboard" button at the top of the submission page this will allow you to view all other tournament entries alongside your own.