Skip to content

Instantly share code, notes, and snippets.

@pgaskin
Last active June 25, 2018 01:50
Show Gist options
  • Save pgaskin/48523865d3de1299cb8fb6542d8e2746 to your computer and use it in GitHub Desktop.
Save pgaskin/48523865d3de1299cb8fb6542d8e2746 to your computer and use it in GitHub Desktop.
Instant-runoff voting
import java.util.*;
public class IRV {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// Read the ballots
List<List<String>> ballots = new ArrayList<List<String>>();
for (String tmp: sc.nextLine().split(",")) {
List<String> b = new ArrayList<String>();
for (String c: tmp.split("")) b.add(c.toLowerCase());
ballots.add(b);
};
// Figure out the candidates
List<String> candidates = new ArrayList<String>();
for (List<String> b: ballots) for (String c: b) if (candidates.indexOf(c) == -1) candidates.add(c);
// Find the winner
String winner = null;
Integer last = ballots.hashCode();
while (winner == null) {
// Get the first choices from all ballots with votes left
List<String> firstChoices = new ArrayList<String>();
for (List<String> b: ballots) if (b.size() > 0) firstChoices.add(b.get(0));
// Count the number of first-choice votes for each candidate
HashMap<String, Integer> firstChoiceCounts = new HashMap<String, Integer>();
for (String c: candidates) {
Integer count = 0;
for (String fc: firstChoices) if (fc.equals(c)) count++;
firstChoiceCounts.put(c, count);
}
// Check for a majority winner (votes for candidate greater than sum of other votes)
Integer totalCount = 0;
for (Integer c: firstChoiceCounts.values()) totalCount += c;
for (Map.Entry<String, Integer> e: firstChoiceCounts.entrySet()) if (e.getValue() > totalCount - e.getValue()) winner = e.getKey();
if (winner != null) break;
// If no majority winner, find out the losing score (minimum score)
Integer loserCount = 99999999;
for (Integer c: firstChoiceCounts.values()) loserCount = loserCount < c ? loserCount : c;
// Find and remove the candidates with a losing score from all ballots
List<String> losers = new ArrayList<String>();
for (Map.Entry<String, Integer> e: firstChoiceCounts.entrySet()) if (e.getValue() == loserCount) losers.add(e.getKey());
for (List<String> b: ballots) b.removeAll(losers);
// If the ballots has not been modified and there is no winner, then it is a tie.
if (last == ballots.hashCode()) winner = "tie";
last = ballots.hashCode();
}
// Print the result
System.out.printf("The winner is %s\n", winner);
}
}
#!/usr/bin/env python3
ballots = list(map(list, input("ballots: ").lower().replace(" ", "").split(",")))
candidates = list(set([candidate for ballot in ballots for candidate in ballot]))
winner, last_ballots = None, ballots
while winner == None:
ballots = [b for b in ballots if len(b) > 0]
fcs = [b[0] for b in ballots]
fc_counts = {c: fcs.count(c) for c in candidates}
majority = [cd for cd, ct in fc_counts.items() if ct > sum(fc_counts.values()) - ct]
winner = majority[0] if len(majority) == 1 else None
if winner == None:
losers = [cd for cd, ct in fc_counts.items() if ct == min(fc_counts.values())]
ballots = [[c for c in b if not c in losers] for b in ballots]
winner = "tie" if last_ballots == ballots and winner == None else winner
last_ballots = ballots
print("winner", winner)
"abcd,bcda,bcda,bcda,cdab" -> B
"abcd,bcda,cdab,cdab,dabc,dabc" -> C
"ab,ab,cba,cba," -> Tie
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment