Untitled

import java.util.*;
import java.util.stream.Collectors;

// IMPORTANT: All code must be in this file or it will not be submitted

public class VotingSystems {

    public static void main(String args[]) throws Exception {
        // Sample Test Case
        final var sample = Map.of(List.of("A", "B", "C"), 4, List.of("B", "C", "A"), 3, List.of("C", "B", "A"), 2);
        final Map<List<String>, Integer> case1 = new HashMap<>();
        case1.put(Arrays.asList("A", "B", "C"), 2);
        case1.put(Arrays.asList("A", "C", "B"), 2);
        case1.put(Arrays.asList("B", "A", "C"), 3);
        final Map<List<String>, Integer> case2 = new HashMap<>();
        case2.put(Arrays.asList("B", "A"), 2);
        case2.put(Arrays.asList("A", "B"), 2);
        final Map<List<String>, Integer> case3 = new HashMap<>();
        case3.put(Arrays.asList("A", "B", "C"), 1);
        case3.put(Arrays.asList("B", "A", "C"), 2);
        case3.put(Arrays.asList("C", "A", "B"), 1);
        final Map<List<String>, Integer> case4 = new HashMap<>();
        case4.put(Arrays.asList("A", "B"), 5);
        case4.put(Arrays.asList("B"), 4);
        case4.put(Arrays.asList("C"), 3);
        case4.put(Arrays.asList("D"), 2);
        final Map<List<String>, Integer> case5 = new HashMap<>();
        case5.put(Arrays.asList("B", "A", "C", "D"), 1);
        case5.put(Arrays.asList("C", "A", "B", "D"), 1);
        case5.put(Arrays.asList("D", "A", "B", "C"), 1);
        // Determine plurality winner (Part 1)
        System.out.println("The plurality winner is: " + getPluralityWinner(sample));

        // todo: add additional test cases for Part 1 here
        System.out.println("The plurality winner is: " + getPluralityWinner(case1));
        System.out.println("The plurality winner is: " + getPluralityWinner(case2));
        System.out.println("The plurality winner is: " + getPluralityWinner(case3));
        System.out.println("The plurality winner is: " + getPluralityWinner(case4));
        System.out.println("The plurality winner is: " + getPluralityWinner(case5));

        // // Determine ranked choice winner (Part 2)
        System.out.println("The ranked choice winner is: " + getRankedChoiceWinner(sample));
        System.out.println("The ranked choice winner is: " + getRankedChoiceWinner(case1));
        System.out.println("The ranked choice winner is: " + getRankedChoiceWinner(case2));
        System.out.println("The ranked choice winner is: " + getRankedChoiceWinner(case3));
        System.out.println("The ranked choice winner is: " + getRankedChoiceWinner(case4));
        System.out.println("The ranked choice winner is: " + getRankedChoiceWinner(case5));

        // todo: add additional test cases for Part 2 here

    }

    // implement this method for Part 1
    public static String getPluralityWinner(Map<List<String>, Integer> ballots) {
        Map<String, Integer> candidateToVotes = createCandidateToVotes(ballots);
        LinkedHashMap<String, Integer> sortedCandidateToVotes = sortMap(candidateToVotes);
        Map.Entry<String, Integer> firstEntry = sortedCandidateToVotes.entrySet().iterator().next();
        String winner = firstEntry.getKey();
        return winner;
    }

public static Map<List<String>, Integer> removeLastFromBallots(Map<List<String>, Integer> ballots,
        String lastCandidate) {
    return ballots.entrySet().stream().filter(
            entry -> !entry.getKey().isEmpty() && !entry.getKey().equals(Collections.singletonList(lastCandidate)))
            .map(entry -> {
                List<String> newBallotCandidateList = entry.getKey().stream()
                        .filter(candidate -> !candidate.equals(lastCandidate)).collect(Collectors.toList());
                return new AbstractMap.SimpleEntry<>(newBallotCandidateList, entry.getValue());
            }).collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (v1, v2) -> v1 + v2));
}
    

    public static LinkedHashMap<String, Integer> sortMap(Map<String, Integer> map) {
        // Convert the entries to a list
        List<Map.Entry<String, Integer>> entryList = new ArrayList<>(map.entrySet());

        // Sort the list using a custom comparator
        Collections.sort(entryList, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> entry1, Map.Entry<String, Integer> entry2) {
                // Compare by value first
                int valueComparison = entry2.getValue().compareTo(entry1.getValue());

                // If value are equal, compare by key
                if (valueComparison == 0) {
                    return entry1.getKey().compareTo(entry2.getKey());
                }

                return valueComparison;
            }
        });

        // Create a LinkedHashMap to store the sorted entries
        LinkedHashMap<String, Integer> sortedMap = new LinkedHashMap<>();
        for (Map.Entry<String, Integer> entry : entryList) {
            sortedMap.put(entry.getKey(), entry.getValue());
        }

        return sortedMap;
    }

    public static String getLastEntry(LinkedHashMap<String, Integer> sortedMap) {
        String lastEntry = "";
        for (Map.Entry<String, Integer> entry : sortedMap.entrySet()) {
            lastEntry = entry.getKey();
        }
        return lastEntry;
    }


    public static HashMap<String, Integer> createCandidateToVotes(Map<List<String>, Integer> ballots) {
        // Initialize all candidates to zero votes
        HashMap<String, Integer> candidateToVotes = new HashMap<String, Integer>();
        for (List<String> rankedCandidates : ballots.keySet()) {
            for (String candidate : rankedCandidates) {
                candidateToVotes.put(candidate, 0);
            }
        }
        ballots.entrySet().stream().forEach(ballot -> {
            String candidate = ballot.getKey().get(0);
            Integer votes = ballot.getValue();
            if (candidateToVotes.containsKey(candidate)) {
                candidateToVotes.put(candidate, candidateToVotes.get(candidate) + votes);
            } else {
                candidateToVotes.put(candidate, votes);
            }
        });
        return candidateToVotes;
    }

    // implement this method for Part 2
    public static String getRankedChoiceWinner(Map<List<String>, Integer> ballots) {
        int strictMajority = ballots.entrySet().stream().mapToInt(ballot -> ballot.getValue()).sum() / 2 + 1;
        Map<String, Integer> candidateToVotes = createCandidateToVotes(ballots);
        LinkedHashMap<String, Integer> sortedCandidateToVotes = sortMap(candidateToVotes);
        Map.Entry<String, Integer> firstEntry = sortedCandidateToVotes.entrySet().iterator().next();
        String winner = firstEntry.getKey();
        int votes = firstEntry.getValue();
        if (votes < strictMajority) {
            String lastCandidate = getLastEntry(sortedCandidateToVotes);
            ballots = removeLastFromBallots(ballots, lastCandidate);
            return getRankedChoiceWinner(ballots);
        }
        return winner;
    }
}