package main

import (
    "fmt"
    "strings"
    "os"
)

func count(pattern string, towels []string) int {
    counter := 0

	// Iterate over the map in sorted key order
	for _, t := range towels {
        if pattern == t { counter++ }

        if strings.HasPrefix(pattern, t) {
            counter += count(pattern[len(t):], towels)
        }
    }

    return counter
}

func count_with_map(pattern string, pmap map[string]int) int {
    counter := 0
    
	for key, val := range pmap {
        if pattern == key { return val }

        if strings.HasPrefix(pattern, key) {
            counter += count_with_map(pattern[len(key):], pmap)
        }
    }

    return counter
}

func construct_pmap(towels []string) map[string]int {
    pmap := make(map[string]int)

    for _, t := range towels {
        pmap[t] = count(t, towels)
    }
    
    return pmap
}

func check(err error) {
    if err != nil { panic(err) }
}

func main() {
    dat, err := os.ReadFile("data.txt")
    check(err)
    input := strings.TrimSpace(string(dat))
    
    towels   := strings.Split(strings.Split(input, "\n\n")[0], ", ")
    patterns := strings.Split(input, "\n\n")[1]

    // maps pattern to number of combinations
    pmap := construct_pmap(towels)

    counter := 0
    for i, pattern := range strings.Split(patterns, "\n") {
        counter += count_with_map(pattern, pmap)
    }

    fmt.Println(counter)
}