day19HEADmain

2 files changed, 221 insertions, 0 deletions

diff --git a/day19/example.txt b/day19/example.txt
new file mode 100644
index 0000000..e5b5d64
--- /dev/null
+++ b/day19/example.txt
@@ -0,0 +1,17 @@
+px{a<2006:qkq,m>2090:A,rfg}
+pv{a>1716:R,A}
+lnx{m>1548:A,A}
+rfg{s<537:gd,x>2440:R,A}
+qs{s>3448:A,lnx}
+qkq{x<1416:A,crn}
+crn{x>2662:A,R}
+in{s<1351:px,qqz}
+qqz{s>2770:qs,m<1801:hdj,R}
+gd{a>3333:R,R}
+hdj{m>838:A,pv}
+
+{x=787,m=2655,a=1222,s=2876}
+{x=1679,m=44,a=2067,s=496}
+{x=2036,m=264,a=79,s=2244}
+{x=2461,m=1339,a=466,s=291}
+{x=2127,m=1623,a=2188,s=1013}
diff --git a/day19/solution.zig b/day19/solution.zig
new file mode 100644
index 0000000..0c4b274
--- /dev/null
+++ b/day19/solution.zig
@@ -0,0 +1,204 @@
+const std = @import("std");
+const print = std.debug.print;
+const assert = std.debug.assert;
+const ArrayList = std.ArrayList;
+const HashMap = std.HashMap;
+const mem = std.mem;
+
+const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
+var gpa = std.heap.GeneralPurposeAllocator(.{}){};
+const allocator = gpa.allocator();
+
+const Condition = struct {
+    let: u64,
+    islt: bool,
+    thresh: u64,
+
+    pub fn check(self: @This(), val: u64) bool {
+        return if (self.islt) val < self.thresh else val > self.thresh;
+    }
+};
+
+const Rule = struct {
+    cond: ?Condition,
+    res: []const u8,
+
+    fn parseCondition(s: []const u8) Condition {
+        var splitCond = mem.tokenizeAny(u8, s, "<>");
+        const let: u64 = switch (splitCond.next().?[0]) {
+            'x' => 0,
+            'm' => 1,
+            'a' => 2,
+            's' => 3,
+            else => unreachable,
+        };
+        const islt = mem.count(u8, s, "<") != 0;
+        const thresh = std.fmt.parseInt(u64, splitCond.next().?, 10) catch unreachable;
+
+        return Condition{
+            .let = let,
+            .islt = islt,
+            .thresh = thresh,
+        };
+    }
+
+    pub fn parse(s: []const u8) Rule {
+        var splitRule = mem.tokenizeScalar(u8, s, ':');
+        const first = splitRule.next().?;
+        const second = splitRule.next();
+
+        return if (second) |resStr|
+            Rule{
+                .cond = parseCondition(first),
+                .res = resStr,
+            }
+        else
+            Rule{
+                .cond = null,
+                .res = first,
+            };
+    }
+
+    pub fn check(self: @This(), ratings: Ratings) ?[]const u8 {
+        if (self.cond) |cond| {
+            return if (cond.check(ratings[cond.let])) self.res else null;
+        }
+        return self.res;
+    }
+
+    pub fn getNext(list: RuleList, ratings: Ratings) []const u8 {
+        for (list) |rule| {
+            const res = rule.check(ratings) orelse continue;
+
+            return res;
+        }
+
+        unreachable;
+    }
+
+    pub fn rangeCombs(rules: RuleGraph, curr: []const u8, ranges: Ranges) u64 {
+        if (mem.eql(u8, curr, "A")) {
+            var res: u64 = 1;
+            for (ranges) |r| {
+                res *= r[1] - r[0] + 1;
+            }
+            return res;
+        } else if (mem.eql(u8, curr, "R")) {
+            return 0;
+        }
+
+        var ans: u64 = 0;
+        var ranges_rej: Ranges = undefined;
+        @memcpy(&ranges_rej, &ranges);
+
+        const rule_list = rules.get(curr).?;
+        for (rule_list) |rule| {
+            if (rule.cond) |cond| {
+                const thresh = cond.thresh;
+                const l = ranges[cond.let][0];
+                const r = ranges[cond.let][1];
+                var ranges_suc: Ranges = undefined;
+                @memcpy(&ranges_suc, &ranges_rej);
+
+                if (cond.islt) {
+                    ranges_suc[cond.let] = nextRange(
+                        ranges_suc[cond.let],
+                        .{ l, thresh - 1 },
+                    );
+                    ranges_rej[cond.let] = nextRange(
+                        ranges_rej[cond.let],
+                        .{ thresh, r },
+                    );
+                } else {
+                    ranges_suc[cond.let] = nextRange(
+                        ranges_suc[cond.let],
+                        .{ thresh + 1, r },
+                    );
+                    ranges_rej[cond.let] = nextRange(
+                        ranges_rej[cond.let],
+                        .{ l, thresh },
+                    );
+                }
+                ans += rangeCombs(rules, rule.res, ranges_suc);
+            } else {
+                ans += rangeCombs(rules, rule.res, ranges_rej);
+            }
+        }
+
+        return ans;
+    }
+};
+
+const Range = [2]u64;
+const Ranges = [4]Range;
+const Ratings = []u64;
+const RuleList = []const Rule;
+const RuleGraph = std.StringHashMap(RuleList);
+
+fn nextRange(lhs: Range, rhs: Range) Range {
+    return Range{
+        @max(lhs[0], rhs[0]),
+        @min(lhs[1], rhs[1]),
+    };
+}
+
+pub fn solve(rules: RuleGraph, parts: []const Ratings) !void {
+    var part1: u64 = 0;
+    for (parts) |ratings| {
+        var curr: []const u8 = "in";
+
+        const accepted = while (true) {
+            if (mem.eql(u8, curr, "A")) {
+                break true;
+            } else if (mem.eql(u8, curr, "R")) {
+                break false;
+            }
+            curr = Rule.getNext(rules.get(curr).?, ratings);
+        };
+
+        if (accepted) {
+            for (ratings) |r| {
+                part1 += r;
+            }
+        }
+    }
+
+    print("{d}\n", .{part1});
+
+    const ranges = [_]Range{Range{ 1, 4000 }} ** 4;
+    const ans = Rule.rangeCombs(rules, "in", ranges);
+
+    print("{d}\n", .{ans});
+}
+
+pub fn main() !void {
+    var segments = mem.tokenizeSequence(u8, fin, "\n\n");
+    var splitRules = mem.tokenizeScalar(u8, segments.next().?, '\n');
+    var splitWorkflows = mem.tokenizeScalar(u8, segments.next().?, '\n');
+    var allRules = RuleGraph.init(allocator);
+    var parts = ArrayList(Ratings).init(allocator);
+
+    while (splitRules.next()) |line| {
+        var list = mem.tokenizeAny(u8, line, "{},");
+        const id = list.next().?;
+        var rules = ArrayList(Rule).init(allocator);
+
+        while (list.next()) |ruleStr| {
+            try rules.append(Rule.parse(ruleStr));
+        }
+        try allRules.put(id, rules.items);
+    }
+
+    while (splitWorkflows.next()) |line| {
+        var splitRatings = mem.tokenizeAny(u8, line, "{=,xmas}");
+        var ratings = ArrayList(u64).init(allocator);
+
+        while (splitRatings.next()) |r| {
+            try ratings.append(try std.fmt.parseInt(u64, r, 10));
+        }
+
+        try parts.append(ratings.items);
+    }
+
+    try solve(allRules, parts.items);
+}