Question

Python recursive design question:
Background:

The class vote creates vote objects. A vote is either a blue vote, a red vote, or a purple. This information is stored in the "value" attribute.

The function Poll returns a list of random votes. In the code below, some_poll is a list of 32 random votes.

some_poll = Poll(32)

# -----------------------------------------------------
import random
# -----------------------------------------------------
#
# Return a list of n random votes
#
# -----------------------------------------------------
def Poll(n=16):
    #
    # A random vote, if value is not specified.  Value can be either 'red', 'blue', or 'purple'
    #
    class Vote:
        def __init__(self, value=None):
            if value is None:
                r = random.random()
                if 0 <= r < 0.45:
                    self.value = 'red'
                elif 0.45 <= r < 0.9:
                    self.value = 'blue'
                else:
                    self.value = 'purple'
            else:
                if value not in ('red', 'blue', 'purple'):
                    raise Exception('Invalid vote: ' + value)
                self.value = value

        def __eq__(self, b):
            return self.value == b.value

        def __str__(self):
            return self.value

    return [Vote() for i in range(n)]


# -----------------------------------------------------

Your task is to write a recursive designed function find_winner_fast so that it can correctly find a winner (if there is one) in time Θ(? log ?).

• A winner of a poll is a color that occurs more than 50%.
• If all colors occur less than 50%, there's no winner, and find_winner_fast returns None.
• find_winner should run in Θ(? log ?), where ? is the number of votes in a_poll.

Hint: suppose that w1 is the winner of half of the votes, and w2 is the winner of the other half of the votes. Will knowing w1 and w2 help you determine the winner of all the votes?

• If w1 is equal to w2, who would be the winner of all votes?
• If w1 is not equal to w2, how would you find the winner? Is the winner w1 or w2? Can it be someone else?

Note

• You can store votes, but cannot directly create a vote.
• You can compare two votes using equality. See the example of usage.

Thinking about the recursive design

• a_poll = [ left. ][ right ] 100 votes (n votes) 50 50
• blue is the winner on left. This means blue must have at least 25 votes on left.
• blue is the winner on right. This means blue must also have at least 25 votes on the right.
• Altogether, blue must have at least 50 votes on both left and right. This means blue is the winner overall.

def find_winner_fast(a_poll):
pass

Answer 1

Rasw_code: (my be added to your code):

# find_winner_fast recursive function
def find_winner_fast(a_poll):
# temporary vote_type tuple for comparing the value of Vote object
vote_type = ("red", "blue", "purple", None)
# list for counting votes
vote_count = [0, 0, 0, 0]
# winner variable for storing winner
winner = None
# condition for breaking recusursion
if len(a_poll) == 1:
# finding the corresponding vote count of Vote object and incrementing vote count by 1
vote_count[vote_type.index(a_poll[0].value)] += 1
winner = a_poll[0].value
# returning vote_count and winner
return vote_count, winner
else:
# calling find_winner_fast by slicing the a_poll: second element to last element
(vote_count, winner) = find_winner_fast(a_poll[1:])
# finding the corresponding vote count of first Vote object and incrementing vote count by 1
vote_count[vote_type.index(a_poll[0].value)] += 1

# for loop for finding the winner by iterating over vote_count
for index in range(len(vote_count)):
# checking if any votes count is greater than half of total votes
if vote_count[index] > len(a_poll)/2:
# checking if votes count is greater than votes count of current winner
if vote_count[index] > vote_count[vote_type.index(winner)]:
winner = vote_type[index]

# checking if final votes count is less than half of total votes   
if vote_count[vote_type.index(winner)] < len(a_poll)//2:
winner = None
# returing votes count and winner
return (vote_count, winner)

(votes_count, winner) = find_winner_fast(some_poll)
print("winner: ", winner)
print("red: ", votes_count[0], ", blue: ", votes_count[1], ", purple: ", votes_count[2], sep = "")

if you want to return a winner , even it's votes are not greater than half of votes, then just remove last if statement (lines 67 and 68)