using System.Collections.Concurrent;

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();
}

}

#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;
}

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!();

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

{-# 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