Instant-runoff voting

irv.java

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);
    }
}

IRV.py

#!/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)

vote-examples.txt

"abcd,bcda,bcda,bcda,cdab"       -> B
"abcd,bcda,cdab,cdab,dabc,dabc"  -> C
"ab,ab,cba,cba,"                 -> Tie