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

  • NighedEnglish
    1·
    2 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)

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

    }