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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
1 point
*
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)
spoiler
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();
}
}
3 points
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();
}
3 points
*
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;
3 points
3 points
*
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")))
3 points
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
