Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Third solution in Clear category for Halloween Monsters by mortonfox
MONSTERS = '''
skeleton
ghost
jack
vampire
witch
mummy
zombie
werewolf
frankenstein
'''
# Attempt to extract monster from spell. If spell doesn't have the right
# letters for monster, return None. Otherwise, return spell with the letters
# in monster removed.
def extract_monster(spell, monster):
lst = list(spell)
for ch in monster:
if ch not in lst:
return None
lst.remove(ch)
return ''.join(lst)
# Recursive search for monsters. Try extracting one monster and then call the
# search again on the spell string minus that monster.
def search_monsters(spell, monsters):
maxcount = 0
for i, monster in enumerate(monsters):
result = extract_monster(spell, monster)
if result is not None:
# We don't have to recheck the whole list of monsters on the next
# level of the search tree. If we have skipped past a monster,
# it's not going to be in this branch of the search tree.
maxcount = max(maxcount, search_monsters(result, monsters[i:]) + 1)
return maxcount
def halloween_monsters(spell: str)-> int:
return search_monsters(spell, MONSTERS.split())
if __name__ == '__main__':
assert halloween_monsters('jackghost') == 2, 'jack ghost'
assert halloween_monsters('mummyzombiewerewolf') == 3, 'mummy zombie werewolf'
assert halloween_monsters('witchwitchfrankenstein') == 3, 'witch witch frankenstein'
assert halloween_monsters('skeletonvampirejc') == 2, 'skeleton vampire (not jack)'
assert halloween_monsters('vampirevampireumy') == 2, 'vampire vampire (not mummy)'
print('The local tests are done. Click on "Check" for more real tests.')
Sept. 24, 2019
Comments:
