代做program、代写Python设计程序

日期：2023-10-20 11:43

Assignment 3.1 - Pirate's Plunder

Key Information

Key Information

Your Task

This is a solo open-book home assignment. It involves making a game that is broken up into a set of

programming questions. We provide a small set of tests to allow you to check the correctness of your

solutions. However, these tests are not exhaustive, and passing the tests does not guarantee full

marks. You should perform your own testing to ensure your solution is coded correctly.

Mark Value

The assignment is worth 100 marks. 50 marks are for the code, which is group based individual. 50

marks are for an individual written interview/test to be conducted during Week 12

Due Date

The code part of the assignment is due on Friday Week 12 (20 Oct 2023 11.55 PM Melbourne time

for Clayton students, 11.55PM MA time for Malaysian students)

Submission

The  nal submission of the assignment is to be done through Ed.

Assessment Criteria

Please check the rubric for the assessment criteria

Github Link

The Github template repository can be found here.

Video explanation:

A video explanation of the assignment can be found here.

Late Penalty

10% deduction per calendar day or part thereof for up to one week

Submissions more than 7 calendar days after the due date will receive a mark of zero (0) and no

assessment feedback will be provided.

Generative AI tools cannot be used in this assessment task: In this assessment, you must not use

generative arti cial intelligence (AI) to generate any materials or content in relation to the assessment task.

Welcome to A3 - Pirate Plunder!

Wealth, fame, power. A man who acquired everything in this world, the Chief Examiner,

Alex E. Ignatiev. His  nal words at his workshop sent people to the ed forums.

"My ADT knowledge? If you want it, you can have it! Search for it! I left it all at that

place!"

Students now set sail for Assignment 3 in search of knowledge beyond their wildest

dreams. The world has entered a Great Algorithms Era!

(yah-yo, yah-yo yah-yo...)

Welcome to A3!

This assignment in comparison to the other two is short and (hopefully) sweet. We'll just be solving

two versions of a single problem.

Our story follows some young pirate adventurers trying to make a name (and some treasure) for

themselves at seas. In these tasks you'll be their navigator, selecting the optimal islands to plunder to

avoid the might of the navy.

Important Information, Tips and Tricks

Important Information, Tips and Tricks

Before you get working on the application, please read these tips & tricks to ensure you don't get lost,

or lose any silly marks!

Documentation Requirements

Since we only have two classes for this assignment. Documentation requirements are di erent. In addition to

the usual worst/best case analysis, please include a short paragraph (50-300 words) detailing your

approach in detail in the docstring of the associated class.

Your details should include:

Data Structures used

A small example

Complexity Reasoning (Why are we getting the best/worst case speci ed)

See the rubric for information on how this is marked.

Common Mistakes

You are marked on correctness in Ed. It doesn't matter if your code passes locally, it needs to

pass in Ed. Contact a TA if you are having trouble achieving parity.

Be careful of the speci c Python version used, and don't import any other third party modules

excluding those already in requirements.txt . (There is no requirements.txt for A3.)

Write clear and concise docstrings for methods you introduce / edit.

If introducing new classes, consider using dataclasses to simplify this de nition.

Try to separate your code into small methods of at most 20 lines, and try to abstract logic if

you  nd lots of duplicated work.

Initial Setup + Running Tests

To get up and running you want to do a few things:

Import the template repository - Follow the instructions in the Getting Started with Git page.

To run tests, call python run_tests.py . Note that you can restrict which tests are run using a second

argument. For example, running python run_tests.py 1 will only run tests from the

tests/test_TODO.py  le.

Assumptions & Tidbits

YOU MAY ASSUME THE DEPTH OF A BST IS ALWAYS BOUND BY FOR THIS ASSIGNMENT - FOR

BOTH SOLUTIONS AND COMPLEXITY ANALYSIS!

O(log(N))

Use of sorted or the sort function is still banned.

dataclasses are used in some of the sca old code. In short, they do a lot of the initialisation

boilerplate for you by inspecting the type hinting for class variables. You'll be expected to

understand at a high level what this does to get started with your trail tasks. You

should read more about it here.

Since this is a pirate plundering assignment, here's some recommended listening while you

knock these tasks out of the park!

An error occurred.

Unable to execute JavaScript.

What is the problem?

You are the navigator for your crew of pirates setting sail for various treasures. Throughout the seas

there are various islands, each with their own stash of money, and marines protecting the borders.

For each of the two tasks, every day you'll be selecting one or multiple islands to plunder in order to

optimise something, either money or score. The exact particulars of this is gone through within the

individual tasks.

In terms of code we simply have one dataclass: Island , which has the following properties:

name

money

marines

And some helper methods like __str__ .

[TASK] Mode 1 - An island a day keeps the scurvy at bay

Please be aware of the documentation requirements and complexity assumptions touched on in Important

Information, Tips and Tricks!

In this task, you've amassed a crew of pirates, ready to set sail and make as much money as

possible (with no regard for your crewmates)!

c

For every island, containing marines and holding money, you can decide to send over pirates.

The money you'll earn from this is equal to:

m s ci

min ( , s ,

m

ci ⋅ s )

But the pirates you send will perish in the process 😦 (As well as an equal amount of marines).

Essentially you can take the ratio of pirates to marines, and multiply the available money by that

amount, maxing out at the total pool of money.

There will only be no marines present on an island if the island has been previously plundered (and therefore

has no money).

Every day, you can decide to which islands you'd like to send pirates, and how many to each of these

islands, so that you maximise the money earned (ignoring that you might end up with no crew at the

end of the day).

Your task is to implement the Mode1Navigator class, and the following methods:

__init__(self, islands: list[Island], crew: int) : Initialise, with the initial state of the

islands and the number of crew you'll be taking on your journey.

select_islands(self) -> list[tuple[Island, int]] : Select the islands you wish to attack,

returning a list containing pairs, each pair containing the island itself, as well as how many

crewmates you'll be sending to each island.

select_islands_from_crew_numbers(self, crew_numbers: list[int]) -> list[float] :

Similar to the last method, except rather than simply making the optimal choices for your crew

numbers, you want to calculate the most money you can make with di erent crew

con gurations. You should return a list containing the amount of money you could make with

the respective crew size in the input list.

update_island(self, island: Island, new_money: float, new_marines: int) -> None :

Called whenever an Island updates its money or marine value. island has attributes money

and marines which store the original values before update.

For this task, you may assume that all islands have a unique name, and that the ratio of marines to gold for

each island remains unique throughout execution.

For this task, both select_ tasks do not alter the internal state of the islands. For example, if select_islands

is called, and your plan of attack is to ransack Island A for all of its money, then:

* Your crew number doesn't change

* Island A still has all of its marines and money.

So if you call select_islands again, the return value should be the same.

Intended Complexities

Let be the length of N islands in initialisation.

__init__ should have worst case complexity or less O(N log(N))

select_islands should have worst case complexity or less, and a best case complexity

of or less.

O(N)

O(log(N))

select_islands_for_crew_numbers has a di erent intended complexity for 1008/2085 and

1054 students.

1008/2085: worst case complexity of , where is the length of

crew_numbers .

O(C × N) C

1054: worst case complexity of , where is the length of

crew_numbers .

O(N + C log(C)) C

update_island should have worst case complexity or less O(log(N))

[TASK] Mode 2 - Davy Back Fight

Please be aware of the documentation requirements and complexity assumptions touched on in Important

Information, Tips and Tricks!

Just as with Mode 1, we are faring the seas in search of treasure, and just as before:

For every island, containing marines and holding money, you can decide to send over pirates.

The money you'll earn from this is equal to:

m s ci

min ( , s ,

m

ci ⋅ s )

But the pirates you send will perish in the process 😦 (As well as an equal amount of marines).

Essentially you can take the ratio of pirates to marines, and multiply the available money by that

amount, maxing out at the total pool of money.

There will only be no marines present on an island if the island has been previously plundered (and therefore

has no money).

However, in this mode, you aren't alone at sea! You're battling it out against other up-and-coming

pirates to loot these islands before they do! The pirates that dwell in these seas are a bit

uncharacteristically organised, and have decided to turn this looting into a game called the Davy Back

Fight, so that they can determine who among them is the best pirate, and so deserves the best crew.

A Davy Back Fight works the following way:

1. At the start of each day, every pirate gets a fresh crew of the same size.

2. All pirates then take turns selecting an island to loot, with a speci ed number of crew to send

OR they could skip their turn and do nothing.

3. After each pirate has selected their action, the day is over and the score of the day is counted.

4. The score of a particular pirate crew on a given day is , where is the remaining

crew-mates and is the money looted on that day.

2 × c + m c

m

5. The pirate with the highest score wins the Davy Back Fight

6. Two pirates can send crew to the same island.

Every pirate in the Davy Back Fight surprisingly are perfect logicians, meaning they will always select

the island and crew amount that will maximise their total score for the day. We want you to

implement some code that simulates the Davy Back Fight.

Your task is to implement Mode2Navigator with the following methods:

__init__(self, n_pirates: int) -> None : Initialise the object, n_pirates is the number of

pirates in the Davy Back Fight.

add_islands(self, islands: list[Island]) -> None : Add islands to the seas.

simulate_day(self, crew: int) -> list[tuple[Island|None, int]] : Simulate a day of the

Davy Back Fight. crew is the size of the crew for every pirate captain, and you should return a

list of tuples, each representing the choices made by the  rst, second, ... captain in the order.

Each tuple should contain the Island that was plundered (if any), and how many crew-mates

were sent onto the island (0 if no island was selected).

For this task, you may assume that the name of the island is unique but nothing else.

For this task, simulate_day does alter the internal state of the islands. For example, if simulate_day is

called, and your plan of attack is to ransack Island A for all of its money, then Island A will lose money

proportionate to how much money was stolen, and will lose marines equal to the amount of crew sent.

Intended Complexities

Let be the current number of islands with non-zero money, and be the number of captains

participating in the Davy Back Fight.

N C

add_islands should have a worst case complexity of at most , where is the length

of islands .

O(N + I) I

simulate_day should have a worst case complexity of at most . O(N + C log(N))

Code Submission

This code slide does not have a description.

Rubric

1 Automatic Zoom