from collections import deque

def profiler(method):
    from time import perf_counter_ns
    def wrapper_method(*args: any, **kwargs: any) -> any:
        start_time = perf_counter_ns()
        ret = method(*args, **kwargs)
        stop_time = perf_counter_ns() - start_time
        time_len = min(9, ((len(str(stop_time))-1)//3)*3)
        time_conversion = {9: 'seconds', 6: 'milliseconds', 3: 'microseconds', 0: 'nanoseconds'}
        print(f"Method {method.__name__} took : {stop_time / (10**time_len)} {time_conversion[time_len]}")
        return ret

    return wrapper_method

def build_aho_corasick(towels):
    # Each node: edges dict, failure link, output (which towels end here)
    trie = [{'fail': 0, 'out': []}]
    
    # Build trie of towels
    for index, word in enumerate(towels):
        node = 0
        for char in word:
            if char not in trie[node]:
                trie[node][char] = len(trie)
                trie.append({'fail': 0, 'out': []})
            node = trie[node][char]
        trie[node]['out'].append(len(word))  # store length of matched towel

    # Build fail links (BFS)
    queue = deque()
    # Initialize depth-1 fail links
    for c in trie[0]:
        if c not in ('fail', 'out'):
            nxt = trie[0][c]
            trie[nxt]['fail'] = 0
            queue.append(nxt)

    # BFS build deeper fail links
    while queue:
        r = queue.popleft()
        for c in trie[r]:
            if c in ('fail', 'out'):
                continue
            nxt = trie[r][c]
            queue.append(nxt)
            f = trie[r]['fail']
            while f and c not in trie[f]:
                f = trie[f]['fail']
            trie[nxt]['fail'] = trie[f][c] if c in trie[f] else 0
            trie[nxt]['out'] += trie[trie[nxt]['fail']]['out']
    return trie

def count_possible_designs_aho(trie, design):
    n = len(design)
    dp = [0] * (n + 1)
    dp[0] = 1

    # State in the trie automaton
    state = 0

    for i, char in enumerate(design, 1):
        # Advance in trie
        while state and char not in trie[state]:
            state = trie[state]['fail']
        if char in trie[state]:
            state = trie[state][char]
        else:
            state = 0
        
        # For every towel match that ends here:
        for length_matched in trie[state]['out']:
            dp[i] += dp[i - length_matched]
    
    return dp[n]

@profiler
def main(input_data):
    towels,desired_patterns = ( sorted(x.split(), key=len, reverse=True) for x in input_data.replace(',', ' ').split('\n\n') )
    part1 = 0
    part2 = 0
    
    # Build Aho-Corasick structure
    trie = build_aho_corasick(towels)
    
    for pattern in desired_patterns:
        count = count_possible_designs_aho(trie, pattern)
        if count:
            part1 += 1
            part2 += count
    
    return part1,part2

if __name__ == "__main__":
    with open('input', 'r') as f:
        input_data = f.read().replace('\r', '').strip()
    result = main(input_data)
    print("Part 1:", result[0], "\nPart 2:", result[1])

pub fn day19(input: &str) -> (u64, u64) {
    fn recur_helper<'a>(pat: &'a str, towels: &[&str], map: &mut HashMap<&'a str, u64>) -> u64 {
        let mut hits = 0;
        let mut towel_subset = towels;
        for l in 1..=pat.len() {
            let test_pat = &pat[0..l];
            match towel_subset.binary_search(&test_pat) {
                Ok(idx) => {
                    if pat[l..].is_empty() {
                        return hits + 1;
                    } else if let Some(&v) = map.get(&pat[l..]) {
                        hits += v;
                    } else {
                        let v = recur_helper(&pat[l..], towels, map);
                        map.insert(&pat[l..], v);
                        hits += v;
                    }

                    towel_subset = &towel_subset[idx..];
                    let end = towel_subset.partition_point(|&x| x.starts_with(test_pat));
                    towel_subset = &towel_subset[..end];
                    if towel_subset.is_empty() {
                        return hits;
                    }
                }
                Err(idx) => {
                    towel_subset = &towel_subset[idx..];
                    let end = towel_subset.partition_point(|&x| x.starts_with(test_pat));
                    towel_subset = &towel_subset[..end];
                    if towel_subset.is_empty() {
                        return hits;
                    }
                }
            }
        }
        hits
    }
    let mut part1 = 0;
    let mut part2 = 0;
    let mut lines = input.lines();
    let mut towels = lines.next().unwrap().split(", ").collect::<Vec<_>>();
    towels.sort();
    let mut map = HashMap::new();
    for pat in lines.skip(1) {
        let tmp = recur_helper(pat, &towels, &mut map);
        part2 += tmp;
        if tmp > 0 {
            part1 += 1;
        }
    }
    (part1, part2)
}

import os

here = os.path.dirname(os.path.abspath(__file__))

# read input
def read_data(filename: str):
    global here

    filepath = os.path.join(here, filename)
    with open(filepath, mode="r", encoding="utf8") as f:
        return f.read()

class Trie:
    class TrieNode:
        def __init__(self) -> None:
            self.children = {}  # connections to other TrieNode
            self.end = False  # whether this node indicates an end of a pattern

    def __init__(self) -> None:
        self.root = Trie.TrieNode()

    def add(self, pattern: str):
        node = self.root
        # add the pattern to the trie, one character at a time
        for color in pattern:
            if color not in node.children:
                node.children[color] = Trie.TrieNode()
            node = node.children[color]
        # mark the node as the end of a pattern
        node.end = True

def soln(filename: str):
    data = read_data(filename)
    patterns, design_data = data.split("\n\n")

    # build the Trie
    trie = Trie()
    for pattern in patterns.split(", "):
        trie.add(pattern)

    designs = design_data.splitlines()

    # saves the design / sub-design -> number of component pattern combinations
    memo = {}

    def backtrack(design: str):
        nonlocal trie

        # if design is empty, we have successfully 
        #   matched the caller design / sub-design
        if design == "":
            return 1
        # use memo if available
        if design in memo:
            return memo[design]

        # start matching a new pattern from here
        node = trie.root
        # number of pattern combinations for this design
        pattern_comb_count = 0
        for i in range(len(design)):
            # if design[0 : i+1] is not a valid pattern,
            #   we are done matching characters
            if design[i] not in node.children:
                break
            # move along the pattern
            node = node.children[design[i]]
            # we reached the end of a pattern
            if node.end:
                # get the pattern combinations count for the rest of the design / sub-design
                # all of them count for this design / sub-design
                pattern_comb_count += backtrack(design[i + 1 :])

        # save the pattern combinations count for this design / sub-design
        memo[design] = pattern_comb_count
        return pattern_comb_count

    pattern_comb_counts = []
    for design in designs:
        pattern_comb_counts.append(backtrack(design))
    return pattern_comb_counts


assert sum(1 for dc in soln("sample.txt") if dc > 0) == 6
print("Part 1:", sum(1 for dc in soln("input.txt") if dc > 0))

assert sum(soln("sample.txt")) == 16
print("Part 2:", sum(soln("input.txt")))

import Control.Arrow

import Data.Map (Map)

import qualified Data.List as List
import qualified Data.Map as Map

parse :: String -> ([String], [String])
parse = lines . init
        >>> (map (takeWhile (/= ',')) . words . head &&& drop 2)

countDesignPaths :: [String] -> String -> Map Int Int -> Int
countDesignPaths ts d es
        | Map.null es    = 0
        | ml == length d = mc
        | otherwise = countDesignPaths ts d es''
        where
                ((ml, mc), es') = Map.deleteFindMin es
                ns = List.filter (flip List.isPrefixOf (List.drop ml d))
                        >>> List.map length
                        >>> List.map (ml +)
                        $ ts
                es'' = List.foldl (\ m l' -> Map.insertWith (+) l' mc m) es'
                        $ ns
solve (ts, ds) = List.map (flip (countDesignPaths ts) (Map.singleton 0 1))
        >>> (List.length . List.filter (/= 0) &&& List.sum)
        $ ds

main = getContents
        >>= print
        . solve
        . parse

use std::collections::HashMap;

use crate::solver::DaySolver;

fn parse_input(input: String) -> (Vec<String>, Vec<String>) {
    let towels = input.lines().take(1).collect::<String>().split(", ").map(|s| s.to_string()).collect();

    let designs = input.lines().skip(2).map(|s| s.to_string()).collect();

    (towels, designs)
}

fn how_many_ways(cache: &mut HashMap<String, usize>, towels: &[String], current: String, target: &str) -> usize {
    if let Some(ways) = cache.get(&current) {
        *ways
    } else if current == target {
        cache.insert(current.clone(), 1);
        1
    } else if !target.starts_with(&current) {
        cache.insert(current.clone(), 0);
        0
    } else {
        let ways = towels.iter()
            .map(|t| format!("{}{}", current, t))
            .map(|next| how_many_ways(cache, towels, next, target))
            .sum();
        cache.insert(current, ways);
        ways
    }
}

pub struct Day19Solver;

impl DaySolver for Day19Solver {
    fn part1(&self, input: String) -> String {
        let (towels, designs) = parse_input(input);

        designs.into_iter()
            .filter(|d| how_many_ways(&mut HashMap::new(), &towels, "".to_string(), d) > 0)
            .count()
            .to_string()
    }

    fn part2(&self, input: String) -> String {
        let (towels, designs) = parse_input(input);

        designs.into_iter()
            .map(|d| how_many_ways(&mut HashMap::new(), &towels, "".to_string(), &d))
            .sum::<usize>()
            .to_string()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_part1() {
        let input = include_str!("../../inputs/test/19");
        let solver = Day19Solver {};
        assert_eq!("6", solver.part1(input.to_string()));
    }

    #[test]
    fn test_part2() {
        let input = include_str!("../../inputs/test/19");
        let solver = Day19Solver {};
        assert_eq!("16", solver.part2(input.to_string()));
    }
}

{-# LANGUAGE LambdaCase #-}

module Main where

import Control.Arrow
import Control.Monad.State
import Data.Char
import Data.List
import Data.Map qualified as M
import Data.Monoid
import Text.ParserCombinators.ReadP

parse = fst . last . readP_to_S ((,) <$> (patterns <* eol <* eol) <*> designs)
  where
    eol = char '\n'
    patterns = sepBy word (string ", ")
    designs = endBy word eol
    word = munch1 isLetter

part1 patterns = length . filter (valid patterns)
part2 patterns = getSum . combinations patterns

dropPrefix = drop . length

valid :: [String] -> String -> Bool
valid patterns design = go design
  where
    go "" = True
    go design = case filter (`isPrefixOf` design) patterns of
        [] -> False
        l -> any (go . (`dropPrefix` design)) l

combinations :: [String] -> [String] -> Sum Int
combinations patterns designs = evalState (fmap mconcat . mapM go $ designs) mempty
  where
    go "" = return $ Sum 1
    go design =
        gets (M.lookup design) >>= \case
            Just c -> return c
            Nothing -> case filter (`isPrefixOf` design) patterns of
                [] -> return $ Sum 0
                l -> do
                    res <- mconcat <$> mapM (go . (`dropPrefix` design)) l
                    modify (M.insert design res)
                    return res

main = getContents >>= print . (uncurry part1 &&& uncurry part2) . parse

import Control.Monad.Memo
import Data.List

splitX :: Eq a => [a] -> [a] -> [[a]]
splitX xs = go
    where
        go [] = [[]]
        go ys@(y : ys') = case stripPrefix xs ys of
            Just ys'' -> [] : go ys''
            Nothing   -> let (zs : zss) = go ys' in (y : zs) : zss

parse :: String -> ([String], [String])
parse s =
    let (patterns : _ : designs) = lines s
    in  (splitX ", " patterns, takeWhile (not . null) designs)

countPatterns :: (Eq a, Ord a) => [[a]] -> [a] -> Memo [a] Int Int
countPatterns yss = go
    where
        go [] = return 1
        go xs = sum <$> sequence
            [memo go xs' | Just xs' <- map (\ys -> stripPrefix ys xs) yss]

main :: IO ()
main = do
    (patterns, designs) <- parse <$> getContents
    let ns = startEvalMemo $ mapM (countPatterns patterns) designs
    print $ length $ filter (> 0) ns
    print $ sum ns

use regex::Regex;
use rustc_hash::FxHashMap;

fn parse(input: &str) -> (Vec<&str>, Vec<&str>) {
    let (towels, designs) = input.split_once("\n\n").unwrap();
    (towels.split(", ").collect(), designs.lines().collect())
}

fn part1(input: String) {
    let (towels, designs) = parse(&input);
    let pat = format!("^({})*$", towels.join("|"));
    let re = Regex::new(&pat).unwrap();
    let count = designs.iter().filter(|d| re.is_match(d)).count();
    println!("{count}");
}

fn n_arrangements<'a>(
    design: &'a str,
    towels: &[&str],
    cache: &mut FxHashMap<&'a str, u64>,
) -> u64 {
    if design.is_empty() {
        return 1;
    }
    if let Some(n) = cache.get(design) {
        return *n;
    }
    let n = towels
        .iter()
        .filter(|t| design.starts_with(*t))
        .map(|t| n_arrangements(&design[t.len()..], towels, cache))
        .sum();
    cache.insert(design, n);
    n
}

fn part2(input: String) {
    let (towels, designs) = parse(&input);
    let sum: u64 = designs
        .iter()
        .map(|d| n_arrangements(d, &towels, &mut FxHashMap::default()))
        .sum();
    println!("{sum}");
}

util::aoc_main!();

#include "common.h"

static char *pats[480];
static int lens[480];
int np;

/* memoized for 's' by mem[off], 0 = unknown, >0 = value+1 */
static int64_t
recur(char *s, int off, int64_t *mem)
{
	int64_t acc=0;
	int i;

	if (!s[off]) return 1;
	if (mem[off]) return mem[off]-1;

	for (i=0; i<np; i++)
		if (!strncmp(s+off, pats[i], lens[i]))
			acc += recur(s, off+lens[i], mem);

	mem[off] = acc+1;
	return acc;
}

int
main(int argc, char **argv)
{
	static char patbuf[3200], design[64];
	int64_t p1=0,p2=0, mem[64], n;
	char *rest, *lf;

	if (argc > 1)
		DISCARD(freopen(argv[1], "r", stdin));

	rest = fgets(patbuf, sizeof(patbuf), stdin);

	for (; (pats[np] = strsep(&rest, ",")); np++) {
		while (isspace(pats[np][0]))
			pats[np]++;	/* skip spaces */
		if ((lf = strchr(pats[np], '\n')))
			*lf = '\0';	/* trim trailing \n */
		lens[np] = strlen(pats[np]);
		assert(np+1 < (int)LEN(pats));
	}

	while (scanf(" %63s", design) == 1) {
		memset(mem, 0, sizeof(mem));
		n = recur(design, 0, mem);
		p1 += n >0;
		p2 += n;
	}

	printf("19: %"PRId64" %"PRId64"\n", p1, p2);
	return 0;
}

#ingesloten "zee.kop"
#ingesloten "algemeen.kop"

besloten letterverwijzing patronen[480];
besloten getal lengtes[480];
getal patroonsom;

besloten zeer groot getal
afdaling(
    letterverwijzing tekst,
    getal startpositie,
    zeergrootgetalreeksverwijzing onthouden)
{
	zeer groot getal deelsom=0;
	getal sortering, teller;

	tenzij (tekst[startpositie])
		lever 1;
	mits (onthouden[startpositie])
		lever onthouden[startpositie]-1;

	voor (teller=0; teller < patroonsom; teller++) {
		sortering = tekstdeelvergelijking(
		    tekst + startpositie,
		    patronen[teller],
		    lengtes[teller]);

		mits (sortering == 0) {
			deelsom += afdaling(
			    tekst,
			    startpositie + lengtes[teller],
			    onthouden);
		}
	}

	onthouden[startpositie] = deelsom+1;
	lever deelsom;
}

getal
aanvang(
    getal parametersom,
    letterverwijzingsreeksverwijzing parameters)
{
	blijvende letter patroonruimte[3200];
	blijvende letter ontwerp[64];
	zeer groot getal deel1=0, aantal;
	zeer groot getal deel2=0, onthouden[64];
	letterverwijzing rest;
	letterverwijzing regeleinde;

	mits (parametersom > 1)
		VERWERP(heropen(parameters[1], "r", standaardinvoer));

	rest = geefregel(patroonruimte, grootte(patroonruimte),
	    standaardinvoer);

	voor (; ; patroonsom++) {
		verzeker(patroonsom+1 < (getal)LENGTE(patronen));
		patronen[patroonsom] = tekstsplitsing(naar rest, ",");
		mits (patronen[patroonsom] == NIETS)
			klaar;

		zolang (iswitruimte(patronen[patroonsom][0]))
			patronen[patroonsom]++;
		mits ((regeleinde = zoekletter(patronen[patroonsom], '\n')))
			volg regeleinde = '\0';

		lengtes[patroonsom] = tekstlengte(patronen[patroonsom]);
	}

	zolang (invorm(" %63s", ontwerp) == 1) {
		overschrijf(onthouden, 0, grootte(onthouden));
		aantal = afdaling(ontwerp, 0, onthouden);
		deel1 += aantal >0;
		deel2 += aantal;
	}

	uitvorm("19: %"GEEFZGG" %"GEEFZGG"\n", deel1, deel2);
	lever 0;
}

namespace AoC2024.day_19;

public class Day19 { private ConcurrentDictionary<string,ulong> _cachedPossibilities = new ConcurrentDictionary<string, ulong>();

public void GoPart1()
{
    var inputText = File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\day_19\\input.txt");
    var availableTowels = GetAvailableTowels(inputText);
    var requiredPatterns = GetTargetPatterns(inputText);
    int reachablePatterns = 0;
    
    foreach (var targetPattern in requiredPatterns)
    {
        var result = DoTowelsMatch(targetPattern, availableTowels);

        if (result.Item1)
        {
            reachablePatterns++;
            Console.WriteLine($"Target pattern {targetPattern} can be reached with the following towels: {result.Item2.Aggregate("",(s, s1) => $"{s},{s1}")}");
        }
        else
        {
            Console.WriteLine($"Target pattern {targetPattern} can't be reached");
        }
    }
    
    Console.WriteLine($"reachable patterns: {reachablePatterns}");
}

public void GoPart2()
{
    var inputText = File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\day_19\\input.txt");
    //var inputText = File.ReadAllText("\\AdventOfCode2024\\AoC\\src\\day_19\\testInput.txt");
    var availableTowels = GetAvailableTowels(inputText);
    var requiredPatterns = GetTargetPatterns(inputText);
    ulong patternCount = 0;
    
    var tasks = new List<Task<ulong>>();
    
   // requiredPatterns = requiredPatterns.Take(5).ToList();
    
    
    foreach (var targetPattern in requiredPatterns)
    {
        var task = new Task<ulong>(() =>
        {
            Console.WriteLine(targetPattern);
            ulong taskPatternCount = 0;
            var result = DoTowelsMatch2(targetPattern, availableTowels);

            if (result.Item1)
            {
                taskPatternCount = result.Item2;
                Console.WriteLine($"Target pattern {targetPattern} can be reached with {result.Item2} permutations");
            }
            else
            {
                Console.WriteLine($"Target pattern {targetPattern} can't be reached");
            }

            return taskPatternCount;
        });
        
        task.Start();
        tasks.Add(task);
    }

    Task.WaitAll(tasks);

    tasks.ForEach(task => patternCount += task.Result);
    Console.WriteLine($"{tasks.Count(task => task.Result > 0)} of the patterns were achieved");
    
    Console.WriteLine($"reachable patterns: {patternCount}");
}

private (bool,ulong) DoTowelsMatch2(string targetPattern, List<string> towelPatterns)
{
    ulong possiblePatternCount = 0;
   
    if (_cachedPossibilities.ContainsKey(targetPattern))
    {
        _cachedPossibilities.TryGetValue(targetPattern, out possiblePatternCount);
        return (possiblePatternCount > 0,possiblePatternCount);
    }
    
    foreach (var towelPattern in towelPatterns)
    {
        if (targetPattern.StartsWith(towelPattern))
        {
            var newTargetPattern = targetPattern.Substring(towelPattern.Length);

            if (string.IsNullOrEmpty(newTargetPattern))
            {
                possiblePatternCount++;
                continue;
            }
            
            var doTowelsMatchResult = DoTowelsMatch2(newTargetPattern, towelPatterns);
            if (doTowelsMatchResult.Item1)
            {
                possiblePatternCount += doTowelsMatchResult.Item2;
            }
        }
    }

    _cachedPossibilities.TryAdd(targetPattern, possiblePatternCount);
    
    return (possiblePatternCount>0,possiblePatternCount);
}

private (bool,List<string>?) DoTowelsMatch(string targetPattern, List<string> towelPatterns)
{
    foreach (var towelPattern in towelPatterns)
    {
        if (targetPattern.StartsWith(towelPattern))
        {
            var newTargetPattern = targetPattern.Substring(towelPattern.Length);

            if (string.IsNullOrEmpty(newTargetPattern))
            {
                return (true, new List<string>(){ towelPattern });
            }
            
            var doTowelsMatchResult = DoTowelsMatch(newTargetPattern, towelPatterns);
            if (doTowelsMatchResult.Item1)
            {
                doTowelsMatchResult.Item2.Insert(0, towelPattern);
                return (true, doTowelsMatchResult.Item2);
            }
        }
    }

    return (false,null);
}

private List<string> GetAvailableTowels(string input)
{
    return input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries).First().Split(',', StringSplitOptions.RemoveEmptyEntries).Select(s => s.Trim()).ToList();
}

private List<string> GetTargetPatterns(string input)
{
    var lines = input.Split(Environment.NewLine, StringSplitOptions.RemoveEmptyEntries).ToList();
    lines.RemoveAt(0);
    return lines.Select(s => s.Trim()).ToList();
}

}