Skip Navigation
Advent Of Code @programming.dev
CameronDev @programming.dev

👻 - 2024 DAY 19 SOLUTIONS -👻

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

34 comments

  • Haskell

    My naive solution was taking ages until I tried matching from right to left instead :3

    In the end the cache required for part two solved the problem more effectively.

     
        
import Control.Arrow
import Control.Monad.State
import Data.List
import Data.List.Split
import Data.Map (Map)
import Data.Map qualified as Map

arrangements :: [String] -> String -> Int
arrangements atoms = (`evalState` Map.empty) . go
  where
    go "" = return 1
    go molecule =
      let computed = do
            c <- sum <$> mapM (\atom -> maybe (return 0) go $ stripPrefix atom molecule) atoms
            modify (Map.insert molecule c)
            return c
       in gets (Map.!? molecule) >>= maybe computed return

main = do
  (atoms, molecules) <- (lines >>> (splitOn ", " . head &&& drop 2)) <$> readFile "input19"
  let result = map (arrangements atoms) molecules
  print . length $ filter (> 0) result
  print . sum $ result

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

  • 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; }
    }
}

  • 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)

34 comments