Pythonist

Кодинг-марафон. Задача № 7.

Фермеру нужна ваша помощь, чтобы узнать количество животных, спрятанных в заданной строке txt.

У нас есть список названий животных:

animals = ["dog", "cat", "bat", "cock", "cow", "pig",
           "fox", "ant", "bird", "lion", "wolf", "deer", "bear",
           "frog", "hen", "mole", "duck", "goat"]

Напишите функцию, которая будет принимать строку txt и возвращать максимальное количество названий животных, которые возможно собрать из символов строки.

Пример

txt = "goatcode"
count_animals(txt) ➞ 2

# первое животное = "dog"
# оставшиеся символы в строке = "atcoe",
# второе животное = "cat".
# count = 2 (верно)

# если взять  сперва  "goat", 
# оставшиеся символы в строке = "code",
# т.е. больше нельзя составить имен животных
# count = 1 (неверно)

Еще примеры

count_animals("goatcode") ➞ 2
# "dog", "cat"

count_animals("cockdogwdufrbir") ➞ 4
# "cow", "duck", "frog", "bird"

count_animals("dogdogdogdogdog") ➞ 5

Решение

animals = ["dog", "cat", "bat", "cock", "cow", "pig",
           "fox", "ant", "bird", "lion", "wolf", "deer", "bear",
           "frog", "hen", "mole", "duck", "goat"]


def count_animals(txt):
    counts = []

    def f(t, c):
        for a in animals:
            s = t
            for x in a: s = s.replace(x, "", 1)
            if len(s) + len(a) == len(t): f(s, c + 1)
        counts.append(c)

    f(txt, 0)
    return max(counts)