Important Information, Tips and Tricks
Before you get working on the implementation, please read these instructions and tips to ensure you don't lose any important marks!
Documentation Requirements
Documentation requirements are different when comparing to the previous assignments.
In addition to the
● required worst case and best case analysis for each function/method,
You are also
● required to include short paragraphs (50-300 words) detailing your approach in detail in the docstring of the associated class.
Approach details in general should include:
● Data structures and data types used
● Small example(s)
● Explanations/Reasonings/Proofs on your complexity result (i.e., details on why you obtained the specific best case and worst case results)
See the rubric for information on how this is marked.
Common Mistakes
● [Marking] You are marked on correctness in Ed. It doesn't matter if your code passes locally, it needs to pass in Ed. Please contact us in Ed forum and/or consultation hours if you have any issues.
● [Tools] Make sure you use an up-to-date Python version.
● [Tools] As usual, if importing a third-party/external library means you do not need to implement some of/all the assignment tasks, chances are that it is not allowed. As always, follow the latest instructions on Ed Forum.
● [Tools] If introducing new classes, consider usingdataclasses to simplify this definition.
● [Clarity/Style/Readability] Write clear and concise docstrings for methods you introduce / edit.
● [Clarity/Style/Readability] Try to separate your code into small methods of at most 20 to 30 lines. Try to abstract logic if you find lots of duplicated/similar codes.
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.
[TASK] Mode 2 - A Fair Fight
Please be aware of the documentation requirements and complexity assumptions touched on in Important Information, Tips and Tricks!
In this mode, your team isn't alone! You're battling it out against other groups and teams of greedy adventurers for treasures!
To make the fight for treasures fair and square, the adventure guild has set up some rules. Your team has to prove yourselves to be the best in a qualifying game!
The game works in the following way:
1. Every navigator gets a fresh team of adventurers (with the same adventurer team size for fairness).
2. Each adventurer team then takes turns selecting ONE land site to adventure, with a specific adventurer size. The adventure team can also skip their turn and do nothing.
○ Note: Different teams are also allowed to send adventurers to the same sites!
3. After each team selected their action (i.e., sending adventurers or do nothing), the day is over and the scores of the day is counted:
○ The score OO of a particular adventure team on a given day is:
O=2.5 ×c+rO=2.5 ×c+r, where cc is the remaining adventure numbers and rr is the gold (reward) gained on that day.
○ Please refer to Task 1 for the reward descriptions/equations for calculating rr.
4. The adventure team with the highest scores wins the qualifying game.
All the team leaders surprisingly are perfect logicians! They will always select the site and adventurer numbers that will maximise their total scores for the day.
Your task is to implement Mode2Navigator with the following methods to simulate the game:
● __in it__(self, n_teams: int) -> None:
○ The method initialise the object and stores the number of adventurer teams n_teams in the game (i.e., total number of teams).
● add_sites(self, sites: list[Land]) -> None:
○ The method stores and adds land sites (sites) to the object. If there are existing land sites already in the object, then this method will append land sites (sites) to the existing land sites.
● simulate_day(self, adventurer_size: int) -> list[tuple[Land|None, int]]:
○ The method simulates a day of the game.
○ Input:adventurer_size is the size of the adventurers for every team.
○ Output: The method must return a list of tuples, where each tuple represents the choices made by the first, second, third, ..., n_teams team leaders in the order.
■ 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!
● When populating data into your chosen data structure(s), please check the complexity of the construction method(s). There may be multiple construction
methods/mechanisms for the same data structure, and their complexity can be different!
For simplicity, [ONLY for this task] you are allowed to assume the set item and get item methods for the given hash table data structure to be O(1).