package main

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

func main() {
	patterns, targets := readData("example.txt")
	fmt.Println(part1(patterns, targets), 6)
	fmt.Println(part2(patterns, targets), 16)

	patterns, targets = readData("data.txt")
	fmt.Println(part1(patterns, targets), 280)
	fmt.Println(part2(patterns, targets))
}

func part1(patterns []string, targets []string) (okCount int) {
	notFound := make(map[string]bool)
	for _, target := range targets {
		if doable(patterns, target, notFound) {
			okCount++
		}
	}
	return
}

func part2(patterns []string, targets []string) (okCount int) {
	combis := make(map[string]int)
	for _, target := range targets {
		okCount += combinations(patterns, target, combis)
	}
	return
}

func combinations(patterns []string, target string, combis map[string]int) (combiCount int) {
	if combiCountCache, ok := combis[target]; ok {
		return combiCountCache
	}

	for _, p := range patterns {
		if len(p) > len(target) {
			continue
		}
		if target[:len(p)] != p {
			continue
		}

		if len(p) == len(target) {
			if p == target {
				combiCount++
			}
		} else {
			combiCount += combinations(patterns, target[len(p):], combis)
		}
	}

	combis[target] = combiCount
	return
}

func doable(patterns []string, target string, notFound map[string]bool) bool {
	if len(target) == 0 {
		return true
	}

	if _, n := notFound[target]; n {
		return false
	}

	for _, p := range patterns {
		if len(p) > len(target) {
			continue
		}
		if target[:len(p)] != p {
			continue
		}
		if doable(patterns, target[len(p):], notFound) {
			return true
		}
	}

	notFound[target] = true
	return false
}

func readData(fileName string) (patterns []string, targets []string) {
	fp, _ := os.Open(fileName)
	scanner := bufio.NewScanner(fp)

	scanner.Scan()
	patterns = strings.Split(scanner.Text(), ",")
	for i, p := range patterns {
		patterns[i] = strings.TrimSpace(p)
	}

	scanner.Scan()
	for scanner.Scan() {
		targets = append(targets, strings.TrimSpace(scanner.Text()))
	}

	return
}