this post was submitted on 19 Dec 2024
7 points (76.9% liked)

Advent Of Code

981 readers
21 users here now

An unofficial home for the advent of code community on programming.dev!

Advent of Code is an annual Advent calendar of small programming puzzles for a variety of skill sets and skill levels that can be solved in any programming language you like.

AoC 2024

Solution Threads

M T W T F S S
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25

Rules/Guidelines

Relevant Communities

Relevant Links

Credits

Icon base by Lorc under CC BY 3.0 with modifications to add a gradient

console.log('Hello World')

founded 1 year ago
MODERATORS
 

Day 19 - Linen Layout

Megathread guidelines

  • Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
  • You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL

FAQ

top 31 comments
sorted by: hot top controversial new old
[โ€“] [email protected] 1 points 5 days ago* (last edited 5 days ago)

C#

I had an error in the escape clause of the recursion that stumped me for a bit - wasn't counting the last towel!

This might be the first time I have ever had to use a long/ulong in 9 years of C# dev! (corp dev is obviously boring)

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

}

[โ€“] [email protected] 2 points 5 days ago

C

Interestingly part 1 already defied a naive approach. It was fun thinking of a way to memoize without hash tables.

Code

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

https://codeberg.org/sjmulder/aoc/src/branch/master/2024/c/day19.c

Zee

Also a port to my cursed Dutch dialect of C, Zee:

Code

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

https://codeberg.org/sjmulder/aoc/src/

[โ€“] [email protected] 2 points 5 days ago (1 children)

Rust

First part is solved by making a regex of the available towels, like ^(r|wr|bg|bwu|rb|gb|br)*$ for the example. If a design matches it, then it can be made. This didn't work for the second part, which is done using recursion and memoization instead. Again, it was quite surprising to see such a high solution number. 32 bits were not enough (thanks, debug mode overflow detection).

Solution

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

Also on github

[โ€“] [email protected] 2 points 5 days ago (1 children)

How fast was the regex approach?

[โ€“] [email protected] 3 points 5 days ago (1 children)

About 3ms. A manual implementation might be a bit faster, but not by much. The regex crate is quite optimized for pretty much these problems.

[โ€“] [email protected] 2 points 5 days ago* (last edited 5 days ago) (1 children)

Wow, that is very fast, nice. I was happy with 120ms, seems I'm leaving a lot of performance on the table.

Edit: Regex cut my total time in half, but I am measuring the whole execution, still a massive improvement.

[โ€“] [email protected] 3 points 5 days ago (1 children)

The 3ms are for part 1 only, part 2 takes around 27ms. But I see that our approaches there are very similar. One difference that might make an impact is that you copy the substrings for inserting into the hashmap into Strings.

[โ€“] [email protected] 2 points 5 days ago* (last edited 5 days ago)

Removing the string copy with the length->count array from @sjmulder saved me 20ms, so not super significant. I'll have to play the the profiler and see what I am doing wrong.

I think your approach looks a lot more Rust-like, which I like. Part 1 in 4 lines is very nice.

[โ€“] [email protected] 2 points 5 days ago

Haskell

Runs in 115 ms. Today's pretty straight forward. Memoization feels like magic sometimes!

Code

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

[โ€“] [email protected] 3 points 5 days ago

Haskell

solution

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

[โ€“] [email protected] 2 points 5 days ago (1 children)

Rust

Pretty similar to the other rust answer. This definitely requires

spoilermemoization
of some form, but when done right, is very performant. 122ms for both.

#[cfg(test)]
mod tests {
    use std::collections::HashMap;

    fn count_solutions(
        design: &str,
        patterns: &[&str],
        seen_designs: &mut HashMap<String, i64>,
    ) -> i64 {
        if design.is_empty() {
            return 1;
        }
        if let Some(s) = seen_designs.get(design) {
            return *s;
        }
        let mut count = 0;
        for pattern in patterns {
            if design.starts_with(pattern) {
                count += count_solutions(&design[pattern.len()..], patterns, seen_designs);
            }
        }
        seen_designs.insert(design.to_string(), count);
        count
    }

    #[test]
    fn day19_both_test() {
        let input = std::fs::read_to_string("src/input/day_19.txt").unwrap();
        let parts = input.split_once("\n\n").unwrap();
        let patterns = parts.0.split(", ").collect::<Vec<&str>>();
        let designs = parts.1.split('\n').collect::<Vec<&str>>();

        let mut count = 0;
        let mut total = 0;
        let mut seen_designs = HashMap::new();
        for design in designs {
            let shortlist = patterns
                .iter()
                .filter_map(|p| {
                    if design.contains(p) {
                        return Some(*p);
                    }
                    None
                })
                .collect::<Vec<&str>>();
            let sol_count = count_solutions(design, &shortlist, &mut seen_designs);
            total += sol_count;
            count += (sol_count != 0) as usize;
        }
        println!("{}", count);
        println!("{}", total);
    }
}
[โ€“] [email protected] 2 points 5 days ago (1 children)

I don't know much about Rust but I assume the HashMap<String, i64> requires hashing on insertion and lookup, right? I realized that, for every design, all the strings you'll see are substrings of that design from different starting positions, so I made my lookup table int pos -> int count. The table is reset after every design.

[โ€“] [email protected] 2 points 5 days ago* (last edited 5 days ago) (1 children)

That does mean that if two or more strings end with the same substring, you'd recalculate those substrings? Would be a faster lookup cost though, clever.

My code ran in 120ms, so its pretty damn fast as is, especially compared to the non-memoised version

edit: Tried the array of lengths method, shaved about 20ms off. Not bad, but probably not my main issue either

[โ€“] [email protected] 3 points 5 days ago (1 children)

That does mean that if two or more strings end with the same substring, youโ€™d recalculate those substrings?

I hadn't really considered that, but yes. I'm inclined to think that replacing hash table lookups with plain array indexing (which this allows) outweighs that downside but I'm not sure. Indeed 120ms is pretty damn fast!

[โ€“] [email protected] 1 points 5 days ago (1 children)

It saved me 20ms, and given your using C, saved you dealing with uthash or similar, so probably worth it.

The hashmap is probably a more generic solution though

[โ€“] [email protected] 2 points 5 days ago

Certainly more generic and less prone to user error too. Indeed dealing with hash maps or any advanced data structure is a pain with C, this is where generics or templates really shine, especially if you have control over lifetime aspects as you do with C++ or Rust (e.g. moves, lvalue references, constness, etc).

[โ€“] [email protected] 3 points 6 days ago

Rust

I figured that Part 2 would want something to do with unique paths, so I tried to generate all paths in Part 1, which took too long. So I then decided to go with dynamic programming. In Part 1, I stored a cache of whether a given state can lead to the solution. In Part 2, I updated it to store how many options are possible from a given state.

https://gitlab.com/bricka/advent-of-code-2024-rust/-/blob/main/src/days/day19.rs?ref_type=heads

The Code

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

[โ€“] [email protected] 6 points 6 days ago (3 children)

Javascript

Behold an abomination!

const input = require('fs').readFileSync(0, 'utf-8').toString();
const towels = new Set(input.split(/\r?\n\r?\n/g)[0].split(', '));
const count = (p, t) => [...new Array(p.length).keys()].reduce((acc, i) => [...new Array(i + 1).keys()].forEach(j => acc[j] > 0n && t.has(p.substring(j, i + 1)) ? acc[i + 1] += acc[j] : null) ? acc : acc, [1n, ...new Array(p.length).fill(0n)])[p.length];
input.split(/\r?\n\r?\n/g)[1].split(/\r?\n/g).filter(p => p.length > 0).reduce((acc, p) => { let c = count(p, towels); acc[0] += c > 0 ? 1 : 0; acc[1] += c; return acc }, [0, 0n]).forEach((v, i) => console.log(`Part ${i+1}: ${v}`));
[โ€“] [email protected] 4 points 5 days ago

Wanna try some Uiua?

[โ€“] [email protected] 4 points 5 days ago
[โ€“] [email protected] 3 points 6 days ago

Oh, my. That's... quite something.

[โ€“] [email protected] 2 points 6 days ago

C#

Part 2 was pretty much the same as Part 2 except we can't short-circuit when we find the first match. So, implement a cache of each sub-pattern and the number of ways to form it from the towels, and things get much faster.

using System.Collections.Immutable;
using System.Diagnostics;
using Common;

namespace Day19;

static class Program
{
    static void Main()
    {
        var start = Stopwatch.GetTimestamp();

        var sampleInput = ReceiveInput("sample.txt");
        var programInput = ReceiveInput("input.txt");

        Console.WriteLine($"Part 1 sample: {Part1(sampleInput)}");
        Console.WriteLine($"Part 1 input: {Part1(programInput)}");

        Console.WriteLine($"Part 2 sample: {Part2(sampleInput)}");
        Console.WriteLine($"Part 2 input: {Part2(programInput)}");

        Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
    }

    static object Part1(Input input)
    {
        return input.Patterns
            .Select(p => AnyTowelMatches(p, input.Towels) ? 1 : 0)
            .Sum();
    }

    static object Part2(Input input)
    {
        var matchCache = new Dictionary<string, long>();
        return input.Patterns
            .Select(p => CountTowelMatches(p, input.Towels, matchCache))
            .Sum();
    }

    private static bool AnyTowelMatches(
        string pattern,
        ImmutableArray<string> towels)
    {
        return towels
            .Where(t => t.Length <= pattern.Length)
            .Select(t =>
                !pattern.StartsWith(t) ? false :
                (pattern.Length == t.Length) ? true :
                AnyTowelMatches(pattern.Substring(t.Length), towels))
            .Any(r => r);
    }

    private static long CountTowelMatches(
        string pattern,
        ImmutableArray<string> towels,
        Dictionary<string, long> matchCache)
    {
        if (matchCache.TryGetValue(pattern, out var count)) return count;

        count = towels
            .Where(t => t.Length <= pattern.Length)
            .Select(t => 
                !pattern.StartsWith(t) ? 0 :
                (pattern.Length == t.Length) ? 1 :
                CountTowelMatches(pattern.Substring(t.Length), towels, matchCache))
            .Sum();

        matchCache[pattern] = count;
        return count;
    }

    static Input ReceiveInput(string file)
    {
        using var reader = new StreamReader(file);

        var towels = reader.ReadLine()!.SplitAndTrim(',').ToImmutableArray();
        var patterns = new List<string>();
        reader.ReadLine();
        var line = reader.ReadLine();
        while (line is not null)
        {
            patterns.Add(line);
            line = reader.ReadLine();
        }

        return new Input()
        {
            Towels = towels,
            Patterns = [..patterns],
        };
    }

    public class Input
    {
        public required ImmutableArray<string> Towels { get; init; }
        public required ImmutableArray<string> Patterns { get; init; }
    }
}
[โ€“] [email protected] 3 points 6 days ago

Haskell

I had several strategy switches from brute-force to pathfinding (when doing part1 input instead of example) because It simply wouldn't finish. My solution only found the first path to the design, which is why I rewrote to only count how many towels there are for each prefix I have already built. Do that until there is either only one entry with the total combinations count or no entry and it's impossible to build the design.

I like the final solution, its small (unlike my other solutions) and runs fast.

๐Ÿš€

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

[โ€“] [email protected] 3 points 6 days ago* (last edited 5 days ago) (1 children)

Dart

Thanks to this useful post for reminding me that dynamic programming exists (and for linking to a source to help me remember how it works as it always makes my head spin :-) I guessed that part 2 would require counting solutions, so that helped too.

Solves live data in about 40ms.

import 'package:collection/collection.dart';
import 'package:more/more.dart';

int countTarget(String target, Set<String> towels) {
  int n = target.length;
  List<int> ret = List.filled(n + 1, 0)..[0] = 1;

  for (int e in 1.to(n + 1)) {
    for (int s in 0.to(e)) {
      if (towels.contains(target.substring(s, e))) ret[e] += ret[s];
    }
  }
  return ret[n];
}

List<int> allCounts(List<String> lines) {
  var towels = lines.first.split(', ').toSet();
  return lines.skip(2).map((p) => countTarget(p, towels)).toList();
}

part1(List<String> lines) => allCounts(lines).where((e) => e > 0).length;
part2(List<String> lines) => allCounts(lines).sum;
[โ€“] [email protected] 3 points 5 days ago

Lovely! This is nicer than my memoized recursion. DP remains hard to wrap my head around even though I often apply it by accident.

[โ€“] [email protected] 3 points 6 days ago* (last edited 6 days ago)

Python

Approach: Recursive memoized backtracking with a Trie

I get to use one of my favorite data structures here, a Trie! It helps us figure out whether a prefix of the design is a valid pattern in linear time.

I use backtracking to choose potential component patterns (using the Trie), kicking off matching the rest of the design down the stack. We can continue matching longer patterns immediately after the recursion stack unwinds.
In addition, I use global memoization to keep track of the feasibility (part 1) or the number of combinations (part 2) for designs and sub-designs. This way, work done for earlier designs can help speed up later ones too.

I ended up combining part 1 and 2 solutions into a single function because part 1 is a simpler variant of part 2 where we count all designs with the number of possible pattern combinations > 0.

Reading Input

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

Trie Implementation

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

Solution

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")))

[โ€“] [email protected] 3 points 6 days ago

C#

public class Day19 : Solver {
  private string[] designs;

  private class Node {
    public Dictionary<char, Node> Children = [];
    public bool Terminal = false;
  }

  private Node root;

  public void Presolve(string input) {
    List<string> lines = [.. input.Trim().Split("\n")];
    designs = lines[2..].ToArray();
    root = new();
    foreach (var pattern in lines[0].Split(", ")) {
      Node cur = root;
      foreach (char ch in pattern) {
        cur.Children.TryAdd(ch, new());
        cur = cur.Children[ch];
      }
      cur.Terminal = true;
    }
  }

  private long CountMatches(Node cur, Node root, string d) {
    if (d.Length == 0) return cur.Terminal ? 1 : 0;
    if (!cur.Children.TryGetValue(d[0], out var child)) return 0;
    return CountMatches(child, root, d[1..]) + (child.Terminal ? CountMatches(root, d[1..]) : 0);
  }

  private readonly Dictionary<string, long> cache = [];
  private long CountMatches(Node root, string d) {
    if (cache.TryGetValue(d, out var cached_match)) return cached_match;
    long match = CountMatches(root, root, d);
    cache[d] = match;
    return match;
  }

  public string SolveFirst() => designs.Where(d => CountMatches(root, d) > 0).Count().ToString();

  public string SolveSecond() => designs.Select(d => CountMatches(root, d)).Sum().ToString();
}
[โ€“] [email protected] 3 points 6 days ago (2 children)

Haskell

My naive solution was taking ages until I tried matching from right to left instead :3

In the end the cache required for part two solved the problem more effectively.

import Control.Arrow
import Control.Monad.State
import Data.List
import Data.List.Split
import Data.Map (Map)
import Data.Map qualified as Map

arrangements :: [String] -> String -> Int
arrangements atoms = (`evalState` Map.empty) . go
  where
    go "" = return 1
    go molecule =
      let computed = do
            c <- sum <$> mapM (\atom -> maybe (return 0) go $ stripPrefix atom molecule) atoms
            modify (Map.insert molecule c)
            return c
       in gets (Map.!? molecule) >>= maybe computed return

main = do
  (atoms, molecules) <- (lines >>> (splitOn ", " . head &&& drop 2)) <$> readFile "input19"
  let result = map (arrangements atoms) molecules
  print . length $ filter (> 0) result
  print . sum $ result
[โ€“] [email protected] 2 points 5 days ago

A better version of arrangements using laziness:

arrangements :: [String] -> String -> Int
arrangements atoms molecule = head counts
  where
    counts = zipWith go (tails molecule) (tails counts)
    go [] _ = 1
    go m cs = sum $ map (\a -> if a `isPrefixOf` m then cs !! length a else 0) atoms
[โ€“] [email protected] 2 points 5 days ago (1 children)

until I tried matching from right to left instead :3

My intuition nudged me there but I couldn't reason how that would change things. You still have to test the remaining string, and its remaining string, backtrack, etc right?

[โ€“] [email protected] 1 points 5 days ago

It was just a hunch that the inputs were generated to be difficult to parse using a naive algorithm (ie the towels have a lot of shared prefixes). In general I don't think there's any reason to suppose that one direction is better than the other, at least for random inputs.