C#
Part 1 was straight forward Dykstra with a cost of 1 for each move. Part 2 was a binary search from the number of corrupted bytes given to us for Part 1 (where we know a path can be found) to the total number of corrupted bytes.
using System.Collections.Immutable;
using System.Diagnostics;
using Common;
namespace Day18;
static class Program
{
static void Main()
{
var start = Stopwatch.GetTimestamp();
var sampleInput = ReceiveInput("sample.txt");
var sampleBounds = new Point(7,7);
var programInput = ReceiveInput("input.txt");
var programBounds = new Point(71, 71);
Console.WriteLine($"Part 1 sample: {Part1(sampleInput, 12, sampleBounds)}");
Console.WriteLine($"Part 1 input: {Part1(programInput, 1024, programBounds)}");
Console.WriteLine($"Part 2 sample: {Part2(sampleInput, 12, sampleBounds)}");
Console.WriteLine($"Part 2 input: {Part2(programInput, 1024, programBounds)}");
Console.WriteLine($"That took about {Stopwatch.GetElapsedTime(start)}");
}
static int Part1(ImmutableArray<Point> input, int num, Point bounds) => FindBestPath(
new Point(0, 0),
new Point(bounds.Row - 1, bounds.Col - 1),
input.Take(num).ToImmutableHashSet(),
bounds);
static object Part2(ImmutableArray<Point> input, int num, Point bounds)
{
var start = num;
var end = input.Length;
while (start != end)
{
var check = (start + end) / 2;
if (Part1(input, check, bounds) < 0) end = check;
else start = check + 1;
}
var lastPoint = input[start - 1];
return $"{lastPoint.Col},{lastPoint.Row}";
}
record struct State(Point Location, int Steps);
static int FindBestPath(Point start, Point end, ISet<Point> corruptedBytes, Point bounds)
{
var seenStates = new Dictionary<Point, int>();
var queue = new Queue<State>();
queue.Enqueue(new State(start, 0));
while (queue.TryDequeue(out var state))
{
if (state.Location == end) return state.Steps;
if (seenStates.TryGetValue(state.Location, out var bestSteps))
{
if (state.Steps >= bestSteps) continue;
}
seenStates[state.Location] = state.Steps;
queue.EnqueueRange(state.Location.GetCardinalMoves()
.Where(p => p.IsInBounds(bounds) && !corruptedBytes.Contains(p))
.Select(p => new State(p, state.Steps + 1)));
}
return -1;
}
static ImmutableArray<Point> ReceiveInput(string file) => File.ReadAllLines(file)
.Select(l => l.Split(','))
.Select(p => new Point(int.Parse(p[1]), int.Parse(p[0])))
.ToImmutableArray();
}
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; } } }