Answer Happy

Problem Background - Potion Seller You are constructing a new bartering game "Potion Seller". The game is centred around the titular Potions, and contains 3 groups of people: Vendors working for the company Potion Corp • Adventurers, looking to buy Potions You, the player, attempting to be the man-in-the-middle of this transaction. The aim of this game is to buy potions from the vendors, and sell these to the adventurers for big profits. On any given day, your aim is to find discrepancies between the adventurers buying price, and the vendors selling price. For example, you might buy 5 Litres of a Potion of Instant Health from the vendors for $25, and sell this to the adventurers for $125, for a profit of $100. A few things are assumed about these groups: • The adventurers have access to infinite amounts of money - They will always buy a potion if you offer it to them, at the rate they specify. • The vendors have a shared inventory of Potions, supplied to them by PotionCorp. A vendor can only sell a single potion at a time, but may choose any potion from the inventory that no other vendor is selling. Each potion has the following attributes: • A category - The type of potion sold (Healing, Damage, Buff, etc) • A name - Specifying the exact effects ("Potion of Minor Regeneration", "Deadly Poison", "Potion of Undying Strength", etc) • A price per litre - The amount paid per litre, to purchase this potion from a vendor ($10/L, $23.5/L, etc). Note that one can buy fractional quantities of each potion (I can buy 250ml of the first potion for $2.5) The selling price to adventurers changes day by day, and so will be covered later on. A potion is uniquely identified by its name. All buy prices of potions are unique. The vendors, however, do not offer all items at all times. Each day, each vendor will only offer 1 item from this inventory. The game is played over multiple days, and each day progresses as follows: 1. Certain potions/quantities are added to the inventory of the vendors by Potion Corp 2. Each vendor picks a single potion from the inventory to offer (Which is different from that of every other vendor) 3. The player can purchase potions from the vendors 4. The player can sell potions to the adventurers for profits

Task Descriptions Problem Setup Before simulating this bartering game, we need to do a 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 generators. 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 the function largest prime (k: int) -> int(located in primes.py), which returns the largest prime number strictly less than k. You may want to take inspiration from the Sieve of Eratosthenes. You can guarantee that k will always be larger than 2 (1 is not a prime number!), and at most 100,000

Hashing Potions In order to keep track of Potions in the game, we want to create an object for them. In addition to this, since these potions will eventually be stored in a hash table, we also need a way to hash them. To analyse the efficacy of your hash function, you will implement two hash functions, one which you think is good, and another which you think will cause issues for your hash table. name: str. Your task (in potion.py) is to create a Potion class, with the following attributes: • potion_type: str name: str • buy_price: float quantity: float And must implement the following methods: Instance Method _init__(self, potion_type: str, buy_price: float, quantity: float) -> None • Class Method create_empty(cls, potion_type: str, name: buy_price: float) -> Potion, which creates a potion with O quantity. • Class Method good_hash (cls, name: str, tablesize: int) -> int, which hashes a potion name, given a fixed table size. • Class Method bad_hash(cis, name: str, tablesize: int) -> int, which hashes a potion name, given a fixed table size. stri

Hash Table Analysis Now that we have potion objects and hashing functions, change the file hash_table.py and add the following functionality: • Instance Method init__(self, max_potions: int, good_hash: bool=True, tablesize_override: int=-1) -> None, which initialises the hash table. max_potions is the maximum number of elements that will be added to the hash table. If good_nash is true, use Potion.good_hash to hash keys, otherwise use Potion.bad_hash. If tablesize_override is - 1, then your class should select a reasonable choice for tablesize, given the value of max_potions. Otherwise, your class should set the tablesize to the exact value of tablesize_override. • Instance Method hash(self, potion_name: str) -> int, which hashes a potion name. • Instance Method statistics (self) -> tuple, which returns a tuple of 3 values: o the total number of conflicts (conflict_count) o the total distance probed throughout the execution of the code (probe_total) o the length of the longest probe chain throughout the execution of the code (probe_max) Additionally, you need to provide a short paragraph on what you expect the output of the statistics method to be for your good hash function, and bad hash function, and why this is. (Aroundabout 50-200 words). You should produce sufficient fake data to validate or invalidate your prediction and present these results 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.