SHARE
TWEET

Untitled

a guest Aug 25th, 2019 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """
  2. Module for detecting voter fraud using a hash table.
  3. Students need to complete the contains method for the VoterHashTable
  4. and then complete the fraud_detect_hash function
  5. """
  6. from classes import VoterList, VoterName
  7. from stats import StatCounter, HASH_TABLES_CREATED
  8.  
  9.  
  10. class VoterHashTable:
  11.     """A chaining hash table to store VoterName objects.
  12.        You should use the default hash function for VoterName objects as the basis for
  13.        determining which slot items go/are in, eg, hash(my_voter_name)
  14.        You should be able to add other objects when testing,
  15.           as long as they are hashable with hash(my_testing_thing)...
  16.        But make sure you test it with VoterName objects as this will let you compare
  17.        your comparisons_used with the actual comparisons used.
  18.        ************************************************************************
  19.        ************************************************************************
  20.        ****==== DON'T change any methods expcept the contains method!!! ===****
  21.        ************************************************************************
  22.        ************************************************************************
  23.     """
  24.     # class variables - used for keeping track of things
  25.     _memory_used = 0
  26.  
  27.     def __init__(self, initial_size):
  28.         """ Initialises a hash table with initial_size slots.
  29.             The slots are basically stored as a list of VoterLists,
  30.             which are intially empty.
  31.             The performance counters are all set to zero.
  32.         """
  33.         self.number_of_slots = initial_size
  34.         self.number_of_names = 0
  35.         self.comparisons_used = 0
  36.         self._data = []
  37.         # setup the given number of slots, each containing an empty VoterList
  38.         for _ in range(initial_size):
  39.             self._data.append(VoterList())
  40.         VoterHashTable._memory_used += initial_size
  41.         StatCounter.increment(HASH_TABLES_CREATED)
  42.  
  43.     def add(self, voter_name):
  44.         """ Takes a Votername object and adds it to the hash table,
  45.             Does nothing if it's already in the table.
  46.             Adds item to the list/chain at the appropriate index
  47.             Note that this method does not count comparisons of Voternames directly,
  48.             but the contains check will - you need to write contains
  49.             so that it counts any comparisons that it does.
  50.         """
  51.         if not self.contains(voter_name):
  52.             slot_index = hash(voter_name) % self.number_of_slots
  53.             slot_list = self._data[slot_index]
  54.             slot_list.append(voter_name)
  55.             VoterHashTable._memory_used += 1
  56.             self.number_of_names += 1
  57.  
  58.     def contains(self, voter_name):
  59.         """ Returns True if the hash table contains the given voter_name.
  60.             Make sure you update self.comparisons_used so that it counts
  61.             any comparisons of VoterName objects.
  62.             Hint: Which slot will voter_name be in if it's in the table?
  63.         """
  64.         # ---start student section---
  65.         if self.getitem(hash(voter_name)) == voter_name:
  66.             return True
  67.         elif self.getitem(hash(voter_name)) == None:
  68.             return False
  69.         else:
  70.             evac = 0
  71.             hash_holder = hash(voter_name)
  72.             while evac == 0:
  73.                 hash_holder += 1
  74.                 if self.getitem(hash_holder) == voter_name:
  75.                     evac = 1
  76.                     return True
  77.                 elif self.getitem(hash_holder) == None:
  78.                     evac = 1
  79.                     return False
  80.         # ===end student section===
  81.  
  82.     def __repr__(self):
  83.         """ This is rather ugly, you are better to do a print(my_hashtable)
  84.         which will use the __str__ method to give more readable output.
  85.         """
  86.         return repr(self._data)
  87.  
  88.     def __str__(self):
  89.         string_thing = 'VoterHashTable:\n'
  90.         for slot_index, slot_list in enumerate(self._data):
  91.             string_thing += f'{slot_index:6}: {repr(slot_list)}\n'
  92.         string_thing += (f'Num of names = {self.number_of_names}\n')
  93.         string_thing += (f'Num of slots = {self.number_of_slots}\n')
  94.         string_thing += (f'Load factor  = {self.load_factor():.2f}')
  95.         return string_thing
  96.  
  97.     def __eq__(self, other):
  98.         return self._data == other._data
  99.  
  100.     def __len__(self):
  101.         return len(self._data)
  102.  
  103.     def __contains__(self, item):
  104.         raise TypeError(
  105.             "You can't use the 'in' keyword with a VoterHashTable")
  106.  
  107.     def load_factor(self):
  108.         """ Returns the load factor for the hash table """
  109.         return self.number_of_names / self.number_of_slots
  110.  
  111.     def index(self, start=None):
  112.         """ Points out that we can't do this! """
  113.         raise TypeError(f"{type(self)} doesn't allow using index")
  114.  
  115.     def __getitem__(self, i):
  116.         return self._data[i]
  117.  
  118.     @classmethod
  119.     def get_memory_used(cls):
  120.         """ Returns the amount of memory used """
  121.         return cls._memory_used
  122.  
  123.     @classmethod
  124.     def reset_memory_used(cls):
  125.         """ Resets the the memory tracker """
  126.         cls._memory_used = 0
  127.  
  128.  
  129. def fraud_detect_hash(first_booth_voters, second_booth_voters, load_factor=0.5):
  130.     """This function takes a VoterList from two voting booths and makes a list
  131.     of voters that appear in both lists.
  132.     The function should return two things:
  133.     1. A VoterList containing the fraudulent voters,
  134.     2. The number of comparisons that were used to find the fraudulent voters
  135.     The hashtable is initialised such that adding the voters from the second booth
  136.     will result in a load factor of approximately load_factor, with the
  137.     default load_factor set to 0.5.
  138.     That is, the table size is set to be int(len(second_booth_voters)/load_factor)
  139.     **** NOTE: Remember to complete the VoterHashTable definition above!
  140.     """
  141.     table_size = int(len(second_booth_voters) / load_factor)
  142.     voter_hash_table = VoterHashTable(table_size)
  143.     fraudulent_voters = VoterList()
  144.     # ---start student section---
  145.     for voter_name in first_booth_voters:
  146.        
  147.         VoterHashTable.add(voter_name)
  148.        
  149.     for voter_2 in second_booth_voters:
  150.         if VoterHashTable.contains(voter_2) == True:
  151.             fraudulent_voters.append(voter_2)
  152.     # ===end student section===
  153.     comparisons = voter_hash_table.comparisons_used
  154.     return fraudulent_voters, comparisons
  155.  
  156.  
  157.  
  158. asd = VoterList()
  159. asd.append(VoterName('bob'))
  160. asd.append(VoterName('katylin'))
  161. asd.append(VoterName('harrison'))
  162. asd.append(VoterName('shaun'))
  163.  
  164. fgh = VoterList()
  165. fgh.append(VoterName('bob'))
  166. fgh.append(VoterName('harrison'))
  167. fgh.append(VoterName('katylin'))
  168. fgh.append(VoterName('shaun'))
  169.  
  170.  
  171. print(fraud_detect_hash(asd, fgh))
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top