Untitled
unknown
plain_text
2 years ago
7.1 kB
8
Indexable
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; } }
Editor is loading...