FIT 1008/2085/1054 Assignment 3 Semester 2, 2022

 Introduction Aims To adequately analyse the complexity of various operations / algorithms. To add small parts of implementations of the readily available Hash Table, BST / AVL, Heap data structures. To be able to use the Hash Table, BST / AVL, Heap data structures to solve complex problems. To be able to implement recursive sorting algorithms and anything else required to assist your solutions to complex problems. To continue practising the implementation of correct, high quality and well-documented code. Important Information Much of this assessment assumes some knowledge of Object Oriented Programming basics, as would have been covered in FIT1045. If you are taking FIT2085 or are generally behind on this, slides are available in the Week 5/6 sections on moodle. Use the names provided for internal and external methods, as we will use them in our testing harnesses. Provide appropriate documentation for each file, class, function, and method you define or modify. More on this can be found in the general constraints. For all constants described in this sheet, design your code in such a way that it is very easy to change these constants and still have the project work (This has mainly already been done for you). Tasks are really not separated by length or difficulty. Please read all tasks before deciding how your team should split the work. Any mention of Randomness should use the provided RandomGen class - please read its documentation carefully. Since this assignment features floating point numbers heavily, checking equality is often a bad idea. Please read through the examples given in constants.py to see how you can use EPSILON to make your code more robust. There is a separate rubric item for documentation of your approach for the final parts of this assignment - please see the exact information lower in the spec sheet. You will likely need to implement one or two classes/methods/functions mentioned in the workshops to complete certain parts of this assessment, but most of everything is provided in the scaffold document. Functions mentioning randomness will not be tested heavily, and as long as they do as intended this is ok. Because of this, multiple methods have been added to the Game classes to allow actually setting the materials / caves / traders. The one thing that should be consistent with the description on the spec sheet (and should use the RandomGen class) to ensure tests pass is the way traders generate deals. Submission, Format, and Expectations This assignment is a group assignment. Your group should complete the Group Work Agreement before commencing work on this assignment (Even if you are with the same group, as A2, you need to resubmit for A3). Your group will need to divide the work and submit the assignment together. The assignment will require you to submit all Python files that are detailed in each task. The naming convention for each file is given in the tasks. Once you have all the files completed, please zip them together and name the zip file in the following format: <groupname>_assignment3.zip For Example - A3_Group_100_assignment3.zip And upload to both Gradescope and Moodle. Please do not include the .git or MACOSX folders in your submission, just make a new folder, and copy across your tasks python files. General Constraints and Assumptions - The assignment will provide you with liberties on how to code your solution. However, please, make sure to go through the assessment rubric to see how you will be graded and certain concepts that need to be covered in your solution. - The docstring for each method should contain both the best- and worst-case complexity of the method. You are allowed to include a catchall in your class header (IE all functions, unless stated otherwise, have best/worst case complexity of O(1)) Background After some hard fought pokemon battles, you find yourself transported to a world made of differently-textured cubes, and your arms feel so strong you could punch a tree. It seems youve been transported to some other game, where you can Mine blocks and Craft items, I forget the name of it. The game contains long-nosed characters called Traders, which trade certain materials with you for emeralds. Youd love to get as many emeralds as possible, so you set off on an adventure to collect materials to sell to these Traders. However! The materials all take hunger (and therefore food) to collect, and so you need to choose your materials wisely! Materials A Material has two bits of important information: Name: Used to identify the material Mining Rate: Specifies how many hunger points are needed to mine a single unit of the material (can be a fractional number) Caves A Cave is where we can mine materials. A cave has three bits of important information: Name: Used to identify the cave Material: The material stored within this cave. Each cave houses exactly 1 material Quantity: The amount of the material which is currently mineable in the cave. Trader A Trader will only ever buy 1 material at a time, this material changes day by day. The way in which the Trader selects this material, and how many emeralds they are willing to buy it for, is covered in more detail later in the assessment. Traders have a name and type, which again will be talked about more later. Food Food has three properties: Name: Used to identify the food. Hunger bars: The number of bars of hunger this food will give you when eaten. This can be used to mine materials. Cost: The emerald cost of the food. This is fixed. The Game The game starts off by generating caves, materials, players, and traders randomly. The player starts off with a certain amount of emeralds. From here, each day of the game plays out like follows: 1. The traders decide on what materials they will buy today, and for how many emeralds 2. A number of randomly generated food items are offered to the player 3. The player can select one and only one food item to purchase, filling up their hunger points 4. The player can go mining for the day, using their hunger to collect materials, and then the player sells all of their materials for emeralds 5. The quantities of materials in each cave is updated, and the cycle repeats. Worked Example - 1 Day Here, the player can purchase the Cooked Chicken Cuts for 19 emeralds, and receive 424 hunger bars. Current Emeralds: 50 - 19 = 31 From here, they can first visit Castle Karstaag Ruins, and mine 4 Netherite Ingots. This takes 4 20.95 hunger bars. These 4 Netherite Ingots sell for 9.78 emeralds with Ruby Goodman. Current Emeralds: 31 + 4 9.78 = 70.12 From here, the player can then visit Red Eagle Redoubt, mining all 3 Fishing Rods. This takes 3 26.93 hunger bars. These 3 Fishing Rods sell for 7.44 emeralds with Waldo Morgan. Current Emeralds: 70.12 + 3 7.44 = 92.44 From here, the player can then visit Glacial Cave, mining all 3 Gold Nuggets. This takes 3 27.24 hunger bars. These 3 Gold Nuggets sell for 7.7 emeralds with Orson Hoover. Current Emeralds: 92.44 + 3 7.7 = 115.54 From here, the player can then visit Boulderfall Cave, mining all 10 Prismarine Crystals. This takes 10 11.48 hunger bars. These 10 Prismarine Crystals sell for 7.63 emeralds with Lea Carpenter. Current Emeralds: 115.54 + 10 7.63 = 191.84 From here, the player can then visit Orotheim, mining ~2.3353 Fishing Rods. This takes ~2.3353 26.93 hunger bars. These 2.3353 Fishing Rods sell for 7.44 emeralds with Waldo Morgan. Current Emeralds: 191.84 + 2.3353 7.44 = 209.2147 If the game continued, the quantities within each cave would be updated based on the player's choices. After this, some random amount of each material would be added to caves (see functions mentioned later in the spec) Note that there are other possible solutions, this one has just been highlighted. Any solution which allows the player to end with ~209.2147 emeralds is optimal. Hunger bars used in previous days cannot be saved for subsequent ones. Tasks ADT Setup Before running our Mining and Crafting game, we need to do just a little bit :-) of setup, so that we can make our code as efficient as possible. In particular, we need to work on implementations of: Hash Tables Binary Search Trees AVL Trees While implementing all the bits of preliminary implementation, you will also deal with efficient sorting algorithms, recursion, and iterators. Once we have all the aforementioned implementations, and some special methods, on hand, playing the game should be a lot easier. Prime Number Generation To assist with later tasks, you should first implement an iterator for generating prime numbers. This generator will be needed later when rehashing your hash table. Namely, you need to implement the necessary functionality, as described below, in the file primes.py. The iterator should be initialised with 2 input parameters: upper_bound and factor. Each time the next call of the iterator is made, it should compute and return the largest prime number that is strictly less than the current value of the upper bound. For that, you may want to take inspiration from the Sieve of Eratosthenes and/or additionally use probabilistic primality tests, like Miller-Rabin test, that you have already seen in the applied practicals. When a new prime number p is computed, the value of upper bound should be updated as upper_bound = p factor. Note that we do not require the iterator to have a limit on the upper bound, i.e. it is not required to raise StopIteration we can call it as many times as needed. For example the iterator LargestPrimeIterator(6, 2) should yield 5, 7, 13, 23, 43, ... Hash Tables - Statistics + Analysis In order to keep track of various objects in the game, we want to store and access them efficiently. For this, we may need to use a hash table and so we also need a way to compute hash values for our objects based on their names. Given this information, you will need to implement a reasonably good hash function in the class LinearProbeTable of file hash_table.py for handling string-valued keys. Overall, to handle the game objects efficiently, please change the file hash_table.py and add the following functionality: Instance Method __init__(self, expected_size: int, tablesize_override: int=-1) -> None, which initialises the hash table. Here expected_size is the maximum number of elements that will be added to the hash table. If tablesize_override is -1, then your class should make a reasonable choice for tablesize, chosen to avoid collisions and based on the value of expected_size. Otherwise, your class should set the tablesize to the exact value of tablesize_override. Instance Method hash(self, key: str) -> int, which hashes an object name. Instance Method rehash(self) -> None, which performs rehashing of the table. This should be called on insert if the number of items stored there exceeds a half of its capacity. (Hint: The choice of new table size is up to you, but should be done to reduce the load factor and generally avoid collisions.) Instance Method statistics(self) -> tuple, which returns a tuple of 4 values: the total number of conflicts (conflict_count) the total distance probed throughout the execution of the code (probe_total) the length of the longest probe chain throughout the execution of the code (probe_max) the total number of times rehashing is done (rehash_count) Additionally, you need to provide some analysis in a file called Analysis.pdf. Different cohorts have different requirements here: FIT 1008/2085 Students: Write a short analysis on what you expect the output of the statistics method to be for your hash function and why this is (Around 50-200 words, discuss relationships between different statistics). You should produce at least one set of fake data to validate or invalidate your prediction and present these results. (You dont need to be correct in your expectation, but provide relevant justification for your idea.) FIT 1054 Students: Write a short analysis on what you expect the output of the statistics method to be for your hash function and why this is (Around 50-200 words, discuss relationships between different statistics). You should produce multiple sets of fake data to validate or invalidate your prediction and present these results as well as show how different ratios of inserts / updates affect the result. (You dont need to be correct in your expectation, but provide relevant justification for your idea). Some instance variables have already been initialised in the __init__ method to give you a headstart for statistics. To get the statistics function working, you will need to modify other methods of the Hash Table. Information on what Conflicts, Collisions, and Probes are, and how they differ, is provided below: Conflict Handling Recall that in practice hash functions may map two distinct keys s1 and s2 into the same hash value, i.e. h(s1)=h(s2) s.t. s1s2. Such situations are referred to as collisions. Also, when discussing open addressing, we introduced two more concepts: that of a conflict, which occurs when we attempt to insert a key into our hash table, but the location for that key is already occupied by a different key); and that of probe chain, which is the sequence of positions we inspect before finding an empty space suitable for our key. Note that a conflict may be caused either by (a) a collision due to the bad choice of our hash function, or (b) some of the previous runs of linear probing. Also note that when adding a new key to the hash table, at most one conflict may happen due to the reasons above. For example, consider inserting keys s1, s2 and s3 into an empty table with linear probing, assuming all three hash to location 5, i.e. all the three collide since h(s1)=h(s2)=h(s3)=5h(s_1)=h(s_2)=h(s_3)=5h(s1)=h(s2)=h(s3)=5. If we first insert s1, location 5 is empty and, thus, there is no conflict. If we then insert s2, location 5 is full but 6 is empty. This results in one conflict, with probe chain length 1. If we then insert s3, 5 and 6 are full, but 7 is free. This again results in one conflict, with probe chain length 2. (Both conflicts are caused by the aforementioned collisions h(s1)=h(s2)=h(s3)=5.) Please refer to the diagram below for reference: a Situation when there is no Collision but there is a Conflict You might be wondering what the difference between a collision and conflict really is and you're not alone. To sum up from what we learned above: 1. A collision happens when two values are hashed into the same location 2. A conflict happens when linear probing is required to find a position for the value being inserted. So, there can be a situation where a key is present at a location that occurred due to a prior linear probing but wasn't originally hashed in that space. In this case, when we try to insert a new key to this position, there is no collision but there is a conflict. The reason for no collision is because that space would have been empty if the previous element was inserted after the current one. For example - Let's expand on the example that we used before and let's expand the hash table to have one extra spot. Now, let's consider an element s4 such that h(s4)=7. Now we know that s3 already exists in index 7, but that happened due to a linear probe as h(s3)=5. This means that we have a conflict, but no collision. The probe chain is still [7] and the probe length is 1. Binary Search Trees As you already know, binary trees are ubiquitous in computer science and in programming. Same holds for binary search trees (BSTs), which enable us to apply them in a number of important practical settings. Although being arguably one of the simplest and yet powerful data structures, binary search trees are susceptible to becoming unbalanced, after a number of insertion and deletion operations. To overcome this issue, computer scientists proposed various modifications and extensions to BSTs that made them self-balancing. The basic idea is that whenever an insertion or deletion operation is performed, the balance of the tree is checked and rebalancing is done if needed. Examples of self-balancing BSTs include red-black trees B-trees and B+-trees AVL trees Clearly, the advantage of self-balancing trees is that they guarantee that insertion, deletion, lookup operations can be performed in logarithmic time (on the number of nodes in the tree), which is in clear contrast with the simple binary search trees. Moreover, since they are valid BSTs, they provide us with a simple and efficient way to traverse our data in order. In this set of tasks, we are going to implement self-balancing AVL trees by extending the functionality of class BinarySearchTree of file bst.py partially provided to you in the scaffold. Although the implementation of self-balancing is to be done in the next section of the assignment, here you need to prepare the foundation for that. In the following tasks, you need to update the implementation of BSTs provided to you by adding the following missing functionality. Your concrete task is to update the class BinarySearchTree in file bst.py by adding implementations for the following methods: get_successor(self, current: TreeNode) -> TreeNode, which returns the successor of current (the smallest node greater than current) in the sub-tree. It should return None if there is no element greater in the subtree. get_minimal(self,current:TreeNode)->TreeNode,whichreturnsthe smallest node in the current sub-tree. Self-balancing AVL Trees Invented in 1962 by Georgy Adelson-Velsky and Evgenii Landis, AVL trees serve as a simple extension of the standard binary search trees and represent one of the first examples of self-balancing BSTs. AVL trees build on the concept of balance factor of a subtree defined by the root of the subtree: () = h(. h) h(. ) A tree is called balanced, if the balance factor of every node in the tree is in {-1, 0, 1}. Hence, if for some of the nodes of the balance factor is above these limits, the height of the corresponding left and right branches of the node-rooted subtree differ a lot thus breaking the worst-case logarithmic guarantees on the complexity of the main tree operations. AVL trees only add a way to rebalance the tree if it is necessary. Besides that, the trees perform exactly the same way as the standard binary search trees. Example of a balanced AVL tree with balance factors shown green: How It Works Basic Idea Assume that after an insertion or deletion operation we end up having an unbalanced subtree with the root node having the balance factor from {-2, 2}. In this case, we can perform a rotation operation to return the balance factor of the subtree back to normal. Note that the balance factor cannot get larger than 2 or less than 2 if each insertion and deletion operation is followed by rebalancing. Below is an animated illustration of how the process works in practice (original GIF animation is taken from Wikipedia). Here the nodes in the tree are additionally labeled by the values of their balance factors. There are two basic types of rotation: left rotation right rotation Your task is to update avl.py to add implementations for the following methods: left_rotate(self, current: AVLTreeNode) -> AVLTreeNode, which performs the left rotation of the current subtree, as shown below, and then updates the heights of all the modified nodes. Note that it returns the new root (r-child in this case). right_rotate(self, current: AVLTreeNode) -> AVLTreeNode, which perform the right rotation of the current subtree, as shown below, and then updates the heights of all the modified nodes. Note that it returns the new root (l-child in this case). Putting it all together Once the above functionality of AVL trees is prepared, you can start making them self-balancing. The code for rebalancing is given, and should complete the rotations correctly. Now that you're done with subtree rebalancing, the final bit left is to apply it whenever the tree becomes unbalanced. When does this happen? Well, after you add or delete nodes. As a result, in class AVLTree redefine the following methods provided in the base class BinarySearchTree such that they apply subtree rebalancing after performing the corresponding operations: insert_aux(self,current:AVLTreeNode,key:K,item:I)-> AVLTreeNode delete_aux(self,current:AVLTreeNode,key:K)->AVLTreeNode Note that both methods should update the height of the current node, and rebalance the subtree rooted by the current node. Return the new (possibly the same) root of the subtree rooted at current. Range of Ith to Jth Smallest Entries Your task is to update avl.py, to add an implementation for the following method: range_between(self, i: int, j: int) -> List Returns a list of smallest entries in the tree from ith to jth inclusive, using recursion. Here indices i and j can take values from 0 to 1, with being the number of nodes in the tree. Note that a 0th entry is meant to store the smallest value in the tree. (Hint: You may need to add some extra code to other AVL operations, and create other attributes in order to achieve the intended complexity). Complexity Requirement: ( + log()) Where is the total number of nodes in the tree. The Game Now that weve done all of that setup we can actually implement our game! NOTE: For the remaining tasks, you may assume that linear probe hash tables have worst case complexity of O(1) for insert, retrieval, update. Basic Classes - Player, Material, Cave Start by adding relevant functionality to the Player, Material, and Cave classes, stored in player.py, material.py, and cave.py. You should add methods to represent objects of each of these classes as strings, and also add any relevant helper methods that might be used later on in the game. The Trader Class There are multiple types of traders but they all satisfy the following functionality: They all have a name. (Set in __init__) They all have some inventory of materials that they might buy. (Set with add_material and remove_material) They all have 1 or 0 currently active deals. (Returned by current_deal) They all can generate a new deal. (Done by generate_deal) They have a string representation, which should mention the current deal. When generating deals, they always calculate the buying price as round(2 + 8 RandomGen.random_float(), 2) For whatever functionality is shared, add implementations in trader.py for the Trader class. Remember to add @abstractmethod for any methods which must be implemented by the child classes. Trader type 1: Random The first trader type is Random. This means that whenever they generate a deal, a random material is selected from their list of materials, and a random buy price is selected. Edit the class RandomTrader in trader.py to implement this. Trader type 2: Range The second trader type is a Range Trader. These traders, when generating a deal, first generate two random numbers. The first number, i, is selected from 0 to the number of available materials minus 1. The second number, j, is selected from i to the number of available materials minus 1. Pseudocode: From here the range trader then generates a list of all materials which lie between the ith easiest to mine and the jth easiest to mine, inclusive. A random material is then chosen from this list, and a random buy price is selected. The range trader should also implement a special helper method materials_between(self, i: int, j: int) -> list[Material], which returns a list containing the materials which are somewhere between the ith and jth easiest to mine, inclusive. Trader type 3: Hard The third trader type is a Hard Trader. These traders, when generating a deal, retrieve the hardest to mine material from their inventory of materials, remove it from the inventory, then make it their deal, and a random buy price is selected. This trader should also have an efficient (O(N)) implementation of set_all_materials. Hooking the Game up The general flow for the Game is now as follows: i = RandomGen.randint(0, len(#materials)-1) j = RandomGen.randint(i, len(#materials)-1) To see how all of this fits together with the example given earlier in the spec sheet - check out example.py and game.py. Note that there is a similar method to initialise_game which allows a tester to provide the exact materials, caves, and traders to the Game class. Lets start by implementing all of the Game Class intermediate methods in the diagram (Ignoring the last two lines of simulate_day) - generating random amounts of each material / food / cave / trader. See the provided docstrings for more information. Making the player functional (and optimal) Now that weve got the Game functional, all thats left to implement is a functional player AI! Given that the player has access to the materials, caves, and traders given through the relevant methods in the player class (which you need to implement), we want to implement the method select_food_and_caves, which generates a tuple containing 3 objects: 1. The food which this player will buy 2. The emerald balance after this player has made their move 3. A list of all caves plundered on their journey, paired with the quantity of each material mined. The choice the player makes should be optimal (Achieving the highest balance of emeralds possible in a single day) The method should not change the existing quantities of any caves, or any statistics of any material/cave/trader object. Complexity Requirement! Given that F = #Foods, T = #Traders, C=#Caves, M=#Materials: - For FIT 1008/2085 students, your method should have complexity at most - For FIT 1054 students, your method should have complexity at most Documentation Requirement! For your solution to select_food_and_caves, please leave a lengthy docstring describing the motivation for your approach in full. Please use a small example to demonstrate your approach. Additionally, you need to fully justify the complexity of your approach - Give line comments to summarise the complexity of blocks of your code. select_food_and_caves O(M + T + F C logC) Verifying your solution makes sense Add a method to the class result of is passed in: 1. Checks that the result makes sense - That: which, when called with the SoloGame select_food_and_caves O(M + T + F logF + C logC) verify_output_and_update_quantities(player_result) select_food_and_caves a. Quantities are in line with what the player provided b. The food is purchasable c. The remaining balance is correct d. Any other sanity checks you can think of 2. Updates the quantities within each cave accordingly. The Game... Part 2? While our current game is all well and good, what it needs is some competition. Rather than having a single player optimising their cave choices, lets involve more players! The Multiplayer Game acts similarly to the Solo Game, with some key differences: Only 1 food is offered per day - everyone can either buy this or not go mining at all. Each player can only visit one cave per day Players go mining in order, so player #1 does all of their mining, followed by player #2, then player #3, and so on. Rather than adding a method to each player class, we want to guess each players move through the Game class! So in the above example, where only Cooked Chicken Cuts are offered: The best choice for Alexey (player #1) is to mine all they can at Boulderfall Cave (8.71 crystals) Jackson cant afford the Cooked Chicken :( The best choice for Saksham (player #3) is not to go to Boulderfall Cave (not much left), but to mine everything at Castle Karstaag Ruins The best choice for Brendon (player #4) is to go to Orotheim and mine 3.71 Fishing Rods See example_multi.py from the scaffold for more info. In the MultiplayerGame class, add the two following methods: : Assuming every player is selecting food/caves to maximise their emeralds at the end of the day, return a list of what foods the players buy (or None if no food is bought), a list of what emeralds the players have at the end of the day, and a list of what caves each player visits, paired select_for_players(self, food: Food) -> tuple[list[Food|None], list[float], list[tuple[Cave, float]|None]] with how much of the material they mined. class. Complexity Requirement! : Serves a similar purpose to from the SoloGame verify_output_and_update_quantities(self, foods: Food | None, balances: float, caves: list[tuple[Cave, float]|None]) -> None verify_output_and_update_quantities(player_result) Given that M=#Materials, T=#Traders, C=#Caves, P=#Players, the method should have complexity at most . This complexity bound applies to all FIT1008/2085 and FIT1054 students. Documentation Requirement! For your solution to select_for_players, please leave a lengthy docstring describing the motivation for your approach in full. Please use a small example to demonstrate your approach. Additionally, you need to fully justify the complexity of your approach - Give line comments to summarise the complexity of blocks of your code. select_for_players O(M + T + C + P log C)