this post was submitted on 19 Dec 2024
8 points (78.6% liked)

Advent Of Code

995 readers
4 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

you are viewing a single comment's thread
view the rest of the comments
[โ€“] [email protected] 2 points 2 weeks 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; }
    }
}