Advertisement
nirajs

courseera

Feb 26th, 2024
589
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.82 KB | None | 0 0
  1. from collections import defaultdict
  2. import math
  3. import os
  4. import random
  5. import re
  6. import sys
  7.  
  8. """
  9. 4,A,B,C
  10. 3,B,C,A
  11. 2,C,B,A
  12. 2,C,A,B
  13.  
  14.  
  15. Count
  16. A -> x
  17. B -> b
  18.  
  19. 1.) Creat a count Map [A] -> count
  20. 2.a) create a list and sort [(4,A), (2,B)]
  21. 2.b) creata a heap with these elements
  22.    pick up top element
  23. 2.c) Scan the map entries get the max
  24.  
  25.  
  26. A
  27. A
  28. B
  29. B
  30. C
  31. C
  32. D
  33. D
  34.  
  35. 2
  36. [1,2,3,4] -> [1,3,4] ->
  37.  
  38. rep
  39.  
  40. 1.) check if we have winner
  41.    a.) if yes  then return the winner
  42.    b.) No
  43.        2.) delete min entry from all got0 step 1 with new input
  44.  
  45.  
  46.  
  47. """
  48.  
  49. class BallotGroup:
  50.     def __init__(self, votes: int, candidates: list[str]):
  51.         self.votes = votes
  52.         self.candidates = candidates
  53.  
  54. # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
  55.  
  56. def pluralityWinner(ballots: list[BallotGroup]) -> str:
  57.     countMap = defaultdict(int)
  58.     candidate = None
  59.     maxCount = 0
  60.     for entry in ballots:
  61.         count = entry.votes
  62.         candidates = entry.candidates
  63.        
  64.         countMap[candidates[0]] += count
  65.        
  66.     for entry in countMap:
  67.         key = entry
  68.         val = countMap[key]
  69.         if candidate == None:
  70.             candidate = key
  71.             maxCount = val
  72.             continue
  73.  
  74.         if val > maxCount:
  75.             candidate = key
  76.             maxCount = val
  77.         elif val == maxCount and key < candidate:
  78.             candidate = key
  79.    
  80.     return candidate
  81.  
  82.  
  83. def checkForWinner(votes) -> str:
  84.     countMap = defaultdict(int)
  85.     maxCount = 0
  86.     candidate = None
  87.     sz = len(votes)
  88.     for entry in votes:
  89.         countMap[entry[0]] += 1
  90.    
  91.     for key in countMap:
  92.         if candidate == None:
  93.             candidate = key
  94.             maxCount = countMap[key]
  95.             continue
  96.         if maxCount < countMap[key]:
  97.             candidate = key
  98.             maxCount = countMap[key]
  99.              
  100.            
  101.    
  102.     if (maxCount > sz//2):
  103.         return candidate
  104.    
  105.     else:
  106.         return None
  107.        
  108.    
  109. def getMinandTrim(votes: list[list[str]]) -> list[list[str]]:
  110.     countMap = defaultdict(int)
  111.     maxCount = len(votes) + 1
  112.     candidate = None
  113.     for entry in votes:
  114.         countMap[entry[0]] += 1
  115.    
  116.     for key in countMap:
  117.         if candidate == None:
  118.             candidate = key
  119.             maxCount = countMap[key]
  120.             continue
  121.         elif maxCount > countMap[key]:
  122.             candidate = key
  123.             maxCount = countMap[key]
  124.            
  125.         elif maxCount == countMap[key] and candidate < countMap[key]:
  126.             candidate = key
  127.    
  128.     newVotes = []
  129.     for entry in votes:
  130.         temp = []
  131.         for ele in entry:
  132.             if ele != candidate:
  133.                 temp.append(ele)
  134.         newVotes.append(temp)        
  135.        
  136.     return newVotes
  137.    
  138.        
  139.    
  140.    
  141.        
  142.    
  143.    
  144. def rankedChoiceWinner(ballots: list[BallotGroup]) -> str:
  145.    
  146.     votes = []
  147.     for entry in ballots:
  148.         for _ in range(entry.votes):
  149.             votes.append(entry.candidates)
  150.    
  151.     while True:
  152.         winner = checkForWinner(votes)
  153.         if winner != None:
  154.             return winner
  155.         votes = getMinandTrim(votes)
  156.  
  157. # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  158.  
  159. def main():
  160.     ballotsCount = int(input().strip().split(",")[0])
  161.  
  162.     ballots = list[BallotGroup]()
  163.     for _ in range(ballotsCount):
  164.         ballotLine = input().strip().split(",")
  165.         ballots.append(BallotGroup(int(ballotLine[0]), ballotLine[1:]))
  166.  
  167.     with open(os.environ["OUTPUT_PATH"], "w") as outfile:
  168.         outfile.write(f"pluralityWinner: {pluralityWinner(ballots)}\n")
  169.         outfile.write(f"rankedChoiceWinner: {rankedChoiceWinner(ballots)}\n")
  170.  
  171.     # Disable unused import warnings for the default imports.
  172.     _ = math, random, re, sys
  173.  
  174. if __name__ == "__main__":
  175.     main()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement