Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Permutations and counters solution in Clear category for Halloween Monsters by kkkkk
from collections import Counter
from itertools import permutations
MONSTERS = '''
skeleton
ghost
jack
vampire
witch
mummy
zombie
werewolf
frankenstein
'''
def found_in_spell(monster_letters, spell_chars):
"""Return True if the number of letters are found in spell_chars."""
for letter, count in monster_letters.items():
if count > spell_chars[letter]:
return False
return True
def halloween_monsters(spell: str)-> int:
"""Count number of strings from MONSTERS found in 'spell' string."""
# Convert the text string of MONSTERS into a Counter (dict) of monster
# names. Each monster name will then be associated with a dict that
# has a count of each letter in the name.
monsters = {}
for monster in sorted([x for x in MONSTERS.split()], key=len):
monsters[monster] = Counter(monster)
# Count the occurances of each letter in the spell.
spell_chars = Counter(spell)
# The order of the monster names is important, so all variations of
# the order must be tried. To reduce the number of permutations,
# first determine just those names that can be found in the spell.
potential_names = []
for monster_name, monster_letters in monsters.items():
if found_in_spell(monster_letters, spell_chars):
potential_names.append(monster_name)
# For each permutation of monster name ordering, continue looking for
# a match until all repeats of a name are counted.
max_monster_count = 0
for monster_list in permutations(potential_names):
# Reset the dict of spell letters.
spell_chars = Counter(spell)
monster_count = 0
while True:
match_found = False
for monster_name in monster_list:
if not found_in_spell(monsters[monster_name], spell_chars):
continue
# Update count of letters in remaining spell string.
spell_chars.subtract(monsters[monster_name])
monster_count +=1
match_found = True
if not match_found:
break
if monster_count > max_monster_count:
max_monster_count = monster_count
return max_monster_count
Nov. 25, 2019
Comments: