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
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
You are viewing a single thread.
View all comments 3 points
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();
}
