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; }
}
}
This is the way. Web client to MPV Shim for local playback.