#!/usr/bin/env python
# -*- encoding: utf-8; py-indent-offset: 4 -*-

# Author: Sebastian Mark, Christian Hennevogl
# CC-BY-SA (https://creativecommons.org/licenses/by-sa/4.0/deed.de)

# pylint: disable=missing-module-docstring,missing-function-docstring,consider-using-f-string


def readinput():
    with open("input", "r", encoding="utf-8") as file:
        lines = file.readlines()
        towels = [pattern.strip() for pattern in lines[0].split(",")]
        designs = list(map(str.strip, lines[2:]))
    return towels, designs


# pylint: disable-next=inconsistent-return-statements
def check_design(design: str, towels: list, cache=None) -> bool:
    if cache is None:
        cache = {}

    if design in cache:  # Check if the result for the current design is already cached.
        return cache[design]

    if not design:  # Base case: empty design means it was successfully constructed.
        return True

    for towel in towels:
        if design.startswith(towel):  # Check if the design starts with the towel.
            if check_design(design.removeprefix(towel), towels, cache):
                cache[design] = True
                return True

    cache[design] = False  # Cache the result as False if no valid combination is found.


def main():
    towels, designs = readinput()

    # part 1
    sorted_towels = sorted(towels, key=len, reverse=True)
    count = 0
    for design in designs:
        if check_design(design, sorted_towels):
            count += 1
    print("\nPossible designs: %d" % count)


if __name__ == "__main__":
    main()