package aoc2024;

import ak.Fn;
import ak.List;
import ak.Map;
import ak.Set;

public class D19 {

  public static long findAll (List<String> patterns, String target, Map<String, Long> seen) {
    if (target.length() == 0) { return 1L; }
    if (seen.containsKey(target)) { return seen.get(target); }
    long oks = 0L;
    for (String pattern : patterns) {
      if (target.startsWith(pattern)) { oks += findAll(patterns, target.substring(pattern.length()), seen); }
    }
    seen.initOrBust(target, oks);
    return oks;
  }

  public static boolean findOne (List<String> patterns, String target, Set<String> seen) {
    if (target.length() == 0) { return true; }
    if (seen.contains(target)) { return false; }
    seen.add(target);
    for (String pattern : patterns) {
      if (target.startsWith(pattern)) {
        boolean ok = findOne(patterns, target.substring(pattern.length()), seen);
        if (ok) { return true; }
      }
    }
    return false;
  }

  public static void main (String[] args) {
    List<String> targets = Fn.inputLinesTrimmed("d19-targets.txt");
    List<String> patterns = Fn.inputLinesTrimmed("d19-patterns.txt");
    {
      long p1 = targets
        .parallelStream()
        .filter(target -> findOne(patterns, target, new Set<>()))
        .count();
      Fn.println("p1: %d", p1);
    }
    {
      long p2 = targets
        .parallelStream()
        .mapToLong(target -> findAll(patterns, target, new Map<>()))
        .sum();
      Fn.println("p2: %d", p2);
    }
  }

}