6
\$\begingroup\$

Part of the Eurovision Song Contest is the voting process to determine the winner of the contest. Each country gives between 1 and 12 points to its 10 most favorite songs. When all the points have been calculated, the presenters of the show call upon each voting country in turn to invite them to announce the results of their vote. Once all the countries have announced their votes, the country with the most points is declared the winner of the contest.

Since 2011, the voting order is determined by an algorithm so as to create as much suspense as possible when the votes were revealed. I don't know what algorithm is used, so I tried to come up with an algorithm of my own to calculate the voting order. And this is my code:

def voting_order(score_board, countries):
    '''
    Reorders the voting order to make the voting more "exciting".

    The algorithm is based on the observation that if a certain country
    awarded x points to the 1st place of the scoreboard and y points to the
    2nd place, and the difference x - y is the same as the difference between
    1st place's score and 2nd place's score, then removing this country's vote
    from the scoreboard will leave it with 1st place and 2nd place having the
    same score, i.e. a tie. Therefore we look for the country with the smallest
    difference between (x - y) and (1st place's score - 2nd place's score). If
    there are more than one country with the same minimal difference, we look
    at the differences between 2nd place and 3rd place, and so on. (If we
    reached the last place and still have two or more countries with the same
    differences, we choose one of them.)

    So the idea is to work backwards, starting with the full scoreboard and
    removing at every iteration the "best candidate" that will leave the
    remaining scoreboard with scores as close as possible. The voting order is
    the reverse order in which the countries have been removed from the
    scoreboard (the first country to be removed is the last one to vote, etc.)
    '''

    #We sort the scoreboard by scores so that it's easier to get the scores of
    #1st, 2nd etc. places.
    sorted_board = sort_scoreboard(score_board)
    voting_order = []

    while len(countries) > 0:
        best_candidate = find_best_candidate(countries, sorted_board)
        remove_from_scoreboard(sorted_board, countries.index(best_candidate))
        voting_order.insert(0, best_candidate)
        countries.remove(best_candidate)
        sorted_board = sort_scoreboard(sorted_board)

    return voting_order

def sort_scoreboard(scoreboard):
    return sorted(scoreboard, key=lambda row: sum(row), reverse=True)

def find_best_candidate(candidates, scoreboard):
    init_cands = candidates
    scores = [sum(row) for row in scoreboard]
    place = 0
    while len(candidates) > 1 and place < len(scoreboard):
        diff_score = scores[place] - scores[place+1]
        cand_diffs = [abs(scoreboard[place][init_cands.index(c)] -
                          scoreboard[place+1][init_cands.index(c)] - diff_score)
                      for c in candidates]
        candidates = [c[0] for c in zip(candidates, cand_diffs)
                      if c[1] == min(cand_diffs)]
        place += 1

    return candidates[0]

def remove_from_scoreboard(scoreboard, column_index):
    for row in scoreboard:
        row.pop(column_index)

if __name__ == '__main__':
    #Eurovision 2014 scoreboard. 1st column is Albania's vote, 2nd column is Armenia's vote, etc.
    VOTING_COUNTRIES = ['Albania', 'Armenia', 'Austria', 'Azerbaijan', 'Belarus', 'Belgium', 'Denmark', 'Estonia', 'FYR Macedonia', 'Finland', 'France',
                        'Georgia', 'Germany', 'Greece', 'Hungary', 'Iceland', 'Ireland', 'Israel', 'Italy', 'Latvia', 'Lithuania', 'Malta', 'Moldova',
                        'Montenegro', 'Norway', 'Poland', 'Portugal', 'Romania', 'Russia', 'San Marino', 'Slovenia', 'Spain', 'Sweden', 'Switzerland',
                        'Netherlands', 'Ukraine', 'United Kingdom']
    SCOREBOARD = [
        [ 0,  0,  5, 10,  8,  4,  1,  8,  0,  2,  0,  6,  0,  5,  2,  0,  0,  5, 10,  7,  5,  0, 10,  7,  0,  5,  0,  0,  7,  0,  0,  6,  0,  0,  0,  0,  0],
        [ 0,  8,  0,  7,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  3,  0,  5,  1,  0,  0,  0,  0, 12,  0,  0,  0,  0,  0,  0,  6,  0],
        [ 0,  0,  0,  0,  3,  0,  0,  0,  0,  0,  0,  7,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 10, 12,  0,  0,  0,  0,  0,  1,  0],
        [ 0,  0,  2,  0,  0,  0,  5,  0,  0,  0,  7,  0,  2,  0,  5,  0,  0,  0,  7,  0,  0,  0,  0,  0,  6,  0,  0,  0,  1,  8,  0,  1,  4,  0,  6,  0,  4],
        [ 0,  0,  1,  0,  4,  0,  6,  3,  0,  7,  2,  0,  5,  3,  0,  1,  7,  0,  0,  5,  8,  2,  0,  0,  0,  7,  3,  1,  0,  0,  5,  0,  3,  5, 10,  0,  0],
        [ 0,  0,  8,  6,  1,  5,  0,  0,  4,  0,  0,  0,  0,  0,  0,  0,  2,  8,  5,  0,  0,  8, 12,  0,  4,  0,  1,  0,  0,  0,  0,  8,  0,  0,  0,  0,  0],
        [ 0,  0, 12,  0, 10,  0,  2,  5,  8,  4, 12, 12,  6,  7,  7,  2,  0,  6,  0, 10,  0,  6,  3, 10,  0,  1,  4,  7,  8,  6,  0,  4,  5,  0,  7, 10,  0],
        [ 6, 12,  0,  0,  0,  0,  0,  0, 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  7,  0,  0,  0,  0,  0,  0],
        [ 0,  0,  0,  2,  7,  0,  0,  0,  5,  0,  5,  0, 10,  1,  3,  3,  0,  0,  8,  0,  0,  0,  2,  4,  2,  0,  0,  0,  0,  0,  1,  0,  2,  0,  0,  7,  0],
        [ 2,  7,  0,  4,  6,  0,  0,  0,  0,  0,  0,  4,  0,  0,  0,  0,  0,  2,  3,  0,  0,  1,  0,  0,  0,  0,  0,  0,  4,  0,  0,  0,  0,  0,  0,  0,  2],
        [ 5,  0,  0,  1,  0, 12,  8,  4,  3, 12, 10, 10,  7, 12, 10, 10, 12, 12, 12,  6, 10, 10,  7,  2, 10,  0, 12,  8,  5,  0, 12, 12, 12, 12, 12,  8, 12],
        [ 4,  6,  0,  0,  0,  0,  0,  0,  0,  0,  0,  5,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  8,  0,  2,  0,  0,  2,  0,  0,  7,  0,  5,  0],
        [ 7,  0,  6,  0,  0, 10, 12, 10,  0, 10,  4,  2,  0,  2,  8,  7,  4, 10,  0,  8,  7,  7,  6,  3,  8,  4,  8, 12,  2, 10,  8, 10,  0,  6,  8, 12,  7],
        [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0],
        [ 0, 10,  0, 12, 12,  0,  0,  1,  6,  0,  0,  8,  0, 10,  0,  0,  0,  3,  0,  2,  6,  5,  8,  0,  0,  0,  2,  0,  0,  0,  0,  0,  0,  0,  0,  4,  0],
        [10,  0,  0,  0,  0,  0,  0,  0,  2,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 12,  0,  6,  0,  0,  0,  0,  0,  0,  0,  0,  0,  2,  0,  0,  0],
        [ 0,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  8,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        [ 0,  0,  4,  0,  0,  3,  4,  6,  0,  0,  0,  0,  4,  0,  6,  5,  0,  0,  6,  3,  0,  0,  0,  0,  7,  3,  0,  0,  0,  3,  0,  0,  6,  4,  2,  0,  6],
        [12,  2,  0,  0,  0,  2,  0,  2,  0,  0,  6,  0,  1,  0,  0,  0,  6,  4,  0,  4,  4,  0,  0,  0,  5,  2,  0,  5,  0,  0,  4,  0,  0,  8,  0,  2,  5],
        [ 0,  5,  3,  0,  0,  0,  0,  0,  0,  0,  0,  1,  3,  4,  1,  0,  5,  0,  2,  0,  2,  3,  0,  5,  0, 10,  7,  6,  0,  0,  3,  0,  0,  0,  3,  0,  1],
        [ 8,  0,  7,  8,  5,  7,  3,  7, 10,  5,  0,  0,  0,  6,  0,  6,  1,  7,  0,  1,  0,  0,  4, 12,  0,  0,  6, 10,  6,  7,  0,  2,  7,  1,  4,  3,  0],
        [ 1,  0,  0,  5,  0,  0,  0,  0,  0,  3,  0,  0,  0,  0,  0,  0,  3,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  4,  0,  0,  0,  0,  5,  0, 10],
        [ 0,  1,  0,  0,  0,  6,  0,  0,  0,  6,  3,  0,  8,  0,  0,  8,  0,  0,  0,  0,  1,  0,  0,  0,  1,  6,  5,  4,  0,  1,  6,  3,  8,  3,  1,  0,  3],
        [ 0,  4, 10,  0,  2,  8, 10, 12,  7,  8,  8,  0, 12,  8, 12, 12, 10,  0,  4, 12, 12,  0,  0,  0, 12, 12, 10,  3,  3,  2, 10,  7, 10, 10,  0,  0,  8],
        [ 3,  3,  0,  3,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  4,  0,  0,  0,  0,  0,  0,  0,  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0],
        [ 0,  0,  0,  0,  0,  1,  7,  0,  0,  0,  0,  3,  0,  0,  0,  4,  8,  0,  0,  0,  0,  4,  0,  0,  3,  0,  0,  0,  0,  5,  0,  5,  0,  0,  0,  0,  0]
    ]

    print(voting_order(SCOREBOARD, VOTING_COUNTRIES))

I feel that this code is not perfect and could be improved, but I'm not sure how. Any advice would be appreciated.

\$\endgroup\$
  • \$\begingroup\$ Does the scoreboard indicate that Armenia voted itself by 8 points, or am I reading it wrong? \$\endgroup\$ – Janne Karila Oct 21 '14 at 5:43
  • \$\begingroup\$ @JanneKarila No, Armenia gave 8 points to Belarus. The order of the rows is not same as the voting order. The scoreboard is taken from here. \$\endgroup\$ – kodkod Oct 21 '14 at 14:26
1
\$\begingroup\$

I propose a few changes to find_best_candidate to simplify.

  • It is a good case for pairwise from itertools recipes.
  • init_cands.index(c) calls can be eliminated by working with indices instead of country names inside the function.

Here is my version. Omitting the if would not change the result, it is only a shortcut.

def find_best_candidate(candidates, scoreboard):
    cand_indices = range(len(candidates))
    for scores1, scores2 in pairwise(scoreboard):
        diff_score = sum(scores1) - sum(scores2)
        cand_diffs = [abs(scores1[i] - scores2[i] - diff_score) for i in cand_indices]
        min_diff = min(cand_diffs)
        cand_indices = [i for i, diff in zip(cand_indices, cand_diffs)
                        if diff == min_diff]
        if len(cand_indices) == 1:
            break

    return candidates[cand_indices[0]]

Other remarks:

  • Instead of key=lambda row: sum(row) you can simply use key=sum
  • It would have been nice had you included some code to replay the voting, so we could judge how well your algorithm maintains suspense.
\$\endgroup\$
1
\$\begingroup\$

I have no time to go for a full review but your question seems interesting and the code is well formatted : small functions, if main guard, documentation.

A simple improvement is replacing :

    candidates = [c[0] for c in zip(candidates, cand_diffs)
                  if c[1] == min(cand_diffs)]

with :

    candidates = [cand for cand, diff in zip(candidates, cand_diffs)
                  if diff == min(cand_diffs)]

to make things easier to read.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.