FIT1008 A3

Initial Setup + Running Tests

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

●    Import the template repository, and

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

Assumptions & Tidbits

YOU MAY ASSUME THE DEPTH OF A BST IS ALWAYS BOUND BY O(log(N))O(log(N)) FOR THIS ASSIGNMENT - FOR BOTH SOLUTIONS AND COMPLEXITY ANALYSIS!

USING THE sorted OR THE sort (PYTHON INBUILT) FUNCTIONS ARE BANNED.

● dataclasses are used in some of the scaffold 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 tasks. You should read more about ithere .

[TASK] Mode 1 - A dungeon 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 cc brave adventurers, ready to set the journey and make as much gold as possible. You can assume they are willing to die/perish for whatever reasons!

For every land site, containing gg guardians with holding rr amount of gold, you can decide to send over cici adventures (0≤ci≤c0≤ci≤c).

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

min(ci⋅rg, r),min(gci⋅r, r),

But the adventurers you send will perish in the process  (as well as an equal amount of guardians).

Assumption: Guardians gg and adventurers cc (including all cici) are positive integers, and gold rr is a positive real number.

Corollary:

●    If you send ci≥gci≥g adventurers to match gg guardians, you can max out rr (as reward).

Assumption: We assume if the land site has been previously plundered/invaded, then: a) there will be no guardians present (g=0g=0), and 2) there will be zero gold left (r=0r=0).

Every day, you will need to decide

● the land sites you wish to send the adventurers to and

●    how many adventurers to each of these sites

to maximise the reward.

Assumption: For simplicity, we discount the cost for the loss of adventurers (i.e., you pay $0 for their funerals)

Your task is to implement the Mode1Navigator class. You are required to implement the following methods:

● __in it__(self, sites: list[Land], adventurers: int):

○   This method perform initialisation. Input sites holds the initial states of the land sites, input adventurers indicates the total number of adventurers cc you are   going to take with you on your journey.

● select_sites(self) -> list[tuple[Land, int]]:

○ The method shall selects the land sites you desire to attack. It is required to

return a list of pairs (in tuple data type), where each pair containing a land object and the number of adventurers you will be sending to the corresponding land site.

●    select_sites_from_adventure_numbers(self, adventure_numbers: list[int]) -> list[float] :

○ The method calculates the maximum amount of reward you can make with

different adventurer numbers. Input adventure_numbersis a list indicating the  number of adventurers for each of the configuration. The method must return a list containing the amount of reward you could make for each of the configuration (corresponding to adventure_numbers).

●    update_site(self, land : Land, new_reward : float, new_guardians: int) -> None:

○   The method is used to update the state of the land object. Input new_reward and new_guardians represent the amount of reward and the number of guardians to be updated for the particular land site (land).

○    Note: The method is called whenever an Island needs to be updated.

For this task, you can assume all land sites: a) have unique names, and; b) the ratio of guardians to reward for each site is unique (throughout execution).

For this task, both select_sites and select_sites_from_adventure_numbers methods must not modify the internal states of the land site (land).

For example: If select_sites is called, and your plan is to ransack Site A for all of its gold (i.e., for obtaining the maximum reward), make sure your code:

* Will not modify/change the original adventure number/configuration

* Will not override the states (e.g., number of guardians and golds) of the Site A object.

In other words, if you call select_sites again, the return value should still be the same.

You are allowed to initialize Python in-built List (i.e., []) and use the append method. However, other methods of the in-build List are generally discouraged.

Complexities

Let NN be the number of land sites ( sites), determined by initialisation/marking test cases.

●    __in it__ method are required to have a worst case complexity of O(Nlog(N))O(Nlog(N)) (or less)

●    select_sites method are required to have a worst case complexity of O(N)O(N) (or less), and a best case complexity of O(log(N))O(log(N)) (or less).

●    select_sites_from_adventure_numbers method has a different complexity requirement for 1008/2085 (and 1054 students).

○ 1008/2085: The method is required to have a worst case complexity of O(A × N)O(A × N), where AA is the length of adventure_numbers.

○ (Bonus [optional]: The method could be done with a worst case complexity of O(N+Alog(A))O(N+Alog(A)), where AA is the length of adventure_numbers.  Try to work on it if you have extra time.)

●    update_site method is required to have a worst case complexity of O(log(N))O(log(N)) (or less).

Final Reminder: For this task, you are suggested to implement in the following order: init,

select_sites, select_sites_from_adventure_numbers, and update_site. Make sure you don't miss the complexity requirements & documentation requirements of the assignment too.

■    Each tuple should contain the land sites that the team leader chooses (or None object if the team leader decides not to send any adventurers), and how many adventurers onto the land site (or 0 if the team leader decides  not to send any adventurers).

For this task, you can assume that the names of the land sites are unique. However, you cannot assume the scores OO of landsites are unique. Your data structures should support  multiple landsites with the same score. In case of a tie (i.e., there are ≥2≥2 landsites with the highest score), you are free to select either one of the best landsites.

For this task, simulate_day will alter the internal states of the land sites.

For example, if simulate_day is called and an adventure team decides to ransack land site A, then you need to make sure A have the correct amount of remaining gold and gurdians left.

Complexities

Let NN be the number of existing land sites, and KK be the number of adventure teams participating in the game.

●    add_sites is required to have a worst case complexity of at most O(N+S)O(N+S), where SS is the length of the additional land sites (input sites) to be added.

●    simulate_day is required to have a worst case complexity of at most O(N+Klog(N))O(N+Klog(N)).

Tips

●    Method simulate_day is quite a large method to be implemented. In order to

implement simulate_day, you might want to consider breaking it down and implementing it step-by-step, with the help of multiple supporting methods. One possible strategy is to:

1.   Implement a method (e.g., compute_score ) to compute the maximum/potential score OO of a land site, based on the number of adventurers the team currently has. It should also return the remaining adventure numbers cc and the gold (reward) gained rr for the particular score OO. Keep in mind multiple land sites could have the same maximum/potential score.

2.   Implement a method (e.g., construct_score_data_structure) to construct the appropriate data structure(s) to organize the scores of all the land sites, and   their relationships to all the land sites (sites).

●   The worst case complexities of methods are hints to what data structures/types you are expected to use!