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 task’s 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    you’ve 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. You’d 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 don’t 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 don’t 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:

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. s1≠s2. 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 forbinary 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 themself-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, which returns the smallest node in the current sub-tree.

Self-balancing AVL Trees

Invented  in  1962  byGeorgy Adelson-Velsky andEvgenii 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:

BalanceFactOr(rOOt)  = Height(rOOt. right)  − Height(rOOt. left)

A tree T is called balanced, if the balance factor of every node in the tree T is in {-1, 0, 1}.

Hence, if for some of the nodes of T 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 fromWikipedia). 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 N −  1, with N  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: (j − i  + log(N))

Where N is the total number of nodes in the tree.

The Game

Now that we’ve 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:

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.

Let’s 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 we’ve got the Game functional, all that’s 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 select_food_and_caves method should have complexity at most O(M + T + F * C * logC)

-    For FIT 1054 students, your select_food_and_caves method should have complexity at most O(M + T + F * logF + C * logC)

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.