Created
May 5, 2016 00:59
-
-
Save chipbell4/4ed9c28daf6d21bc7ec335f1957236a4 to your computer and use it in GitHub Desktop.
Solution for ACM SER 2016 Division 2 "Simplicity"
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# A class for holding the unique letters from a string, and their number of occurences | |
class LetterSet: | |
# constructor, adds the words to a dictionary with letters as keys and letter counts as values | |
# ala: { 'a': 4, 'b' : 2, ... } etc. | |
def __init__(self, word): | |
self.letter_counts = {} | |
for letter in word: | |
self.add_letter(letter) | |
# adds a single letter to the letter set. If the letter is already there, the count is incremented | |
# otherwise, it's added to the set | |
def add_letter(self, letter): | |
# if letter is not in the set yet, add it | |
if letter not in self.letter_counts: | |
self.letter_counts[letter] = 0 | |
# count this occurrence of the letter | |
self.letter_counts[letter] += 1 | |
# return the new value, just in case we want to use it | |
return self.letter_counts[letter] | |
# A quick "to string" function | |
def __str__(self): | |
return repr(self.letter_counts) | |
# gets the distinct letters sorted ascendingly by frequency | |
def letters_by_frequency(self): | |
sorted_keys_with_vals = sorted(self.letter_counts.items(), key=lambda x : x[1]) # sort by dict vals (counts) | |
return list(map(lambda x : x[0], sorted_keys_with_vals)) | |
# gets the frequency of a particular letter | |
def frequency_of_letter(self, letter): | |
if letter in self.letter_counts: | |
return self.letter_counts[letter] | |
else: | |
return 0 | |
# read the word from stdin, and convert to a letter set | |
word = raw_input().strip() | |
letter_set = LetterSet(word) | |
# Get a list of the distinct letters in the letter set | |
distinct_letters = letter_set.letters_by_frequency() | |
# assume that we don't have to delete any characters, i.e. assume there are 2 or less distinct characters in the word | |
deletion_count = 0 | |
# if there are more than two distinct letters get all of the distinct letters but 2 (these are the least frequent | |
# letters), and count how many deletions it would take to delete those characters | |
if len(distinct_letters) > 2: | |
letters_to_remove = distinct_letters[:-2] | |
deletion_count = sum(map(lambda letter : letter_set.frequency_of_letter(letter), letters_to_remove)) | |
print(deletion_count) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment