1 files changed, 179 insertions, 0 deletions
diff --git a/src/16/main.zig b/src/16/main.zig
new file mode 100644
index 0000000..1b45177
--- /dev/null
+++ b/src/16/main.zig
@@ -0,0 +1,179 @@
+const std = @import("std");
+const aoc = @import("aoc");
+
+const Range = struct { min: u32, max: u32 };
+const FieldRule = struct { name: []const u8, r1: Range, r2: Range };
+
+fn assert(comptime T: type, part: ?T) !T {
+    if (part == null) return aoc.Error.InvalidInput;
+    return part.?;
+}
+
+fn parseRange(str: []const u8) !Range {
+    const sep = try assert(usize, std.mem.indexOfScalar(u8, str, '-'));
+    if (sep == str.len - 1) return aoc.Error.InvalidInput;
+    return Range{
+        .min = try std.fmt.parseInt(u32, str[0..sep], 10),
+        .max = try std.fmt.parseInt(u32, str[sep + 1 ..], 10),
+    };
+}
+
+fn parseRules(rules: *std.ArrayList(FieldRule), str: []const u8) !void {
+    var lineit = std.mem.tokenize(u8, str, "\n");
+    while (lineit.next()) |line| {
+        const sep = try assert(usize, std.mem.indexOf(u8, line, ": "));
+        if (sep == line.len - 1) return aoc.Error.InvalidInput;
+        const name = line[0..sep];
+        var rangepart = line[sep + 2 ..];
+        var spaceit = std.mem.tokenize(u8, rangepart, " ");
+        const r1 = try parseRange(try assert([]const u8, spaceit.next()));
+        _ = spaceit.next();
+        const r2 = try parseRange(try assert([]const u8, spaceit.next()));
+        try rules.append(FieldRule{ .name = name, .r1 = r1, .r2 = r2 });
+    }
+}
+
+fn parseVals(vals: *std.ArrayList(u32), str: []const u8) !void {
+    var lineit = std.mem.tokenize(u8, str, "\n");
+    while (lineit.next()) |line| {
+        var partit = std.mem.tokenize(u8, line, ",");
+        while (partit.next()) |part| {
+            try vals.append(try std.fmt.parseInt(u32, part, 10));
+        }
+    }
+}
+
+fn matchesRule(rule: FieldRule, v: u32) bool {
+    return (v >= rule.r1.min and v <= rule.r1.max or v >= rule.r2.min and v <= rule.r2.max);
+}
+
+fn hasRule(rules: []FieldRule, v: u32) bool {
+    for (rules) |r| {
+        if (matchesRule(r, v)) return true;
+    }
+    return false;
+}
+
+fn printCandidates(candidates: []u1, rulecount: usize, remove: usize) void {
+    var i: u32 = 0;
+    while (i < rulecount) : (i += 1) {
+        for (candidates[i * rulecount .. (i + 1) * rulecount]) |c| {
+            aoc.debugfmt("{} ", .{c});
+        }
+        if (i == remove) aoc.debugfmt(" <<<", .{});
+        aoc.debugfmt("\n", .{});
+    }
+}
+
+fn part1(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+    _ = args;
+
+    var answer: u32 = 0;
+
+    var rules = std.ArrayList(FieldRule).init(allocator);
+    defer rules.deinit();
+
+    var othervals = std.ArrayList(u32).init(allocator);
+    defer othervals.deinit();
+
+    var secit = std.mem.split(u8, input, "\n\n");
+    try parseRules(&rules, try assert([]const u8, secit.next()));
+    _ = secit.next();
+    try parseVals(&othervals, (try assert([]const u8, secit.next()))[16..]);
+
+    for (othervals.items) |v| {
+        if (!hasRule(rules.items, v)) answer += v;
+    }
+
+    return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+fn part2(allocator: std.mem.Allocator, input: []u8, args: [][]u8) !?[]u8 {
+    _ = args;
+
+    var rules = std.ArrayList(FieldRule).init(allocator);
+    defer rules.deinit();
+
+    var ownvals = std.ArrayList(u32).init(allocator);
+    defer ownvals.deinit();
+
+    var othervals = std.ArrayList(u32).init(allocator);
+    defer othervals.deinit();
+
+    var secit = std.mem.split(u8, input, "\n\n");
+    try parseRules(&rules, try assert([]const u8, secit.next()));
+    try parseVals(&ownvals, (try assert([]const u8, secit.next()))[13..]);
+    try parseVals(&othervals, (try assert([]const u8, secit.next()))[16..]);
+
+    const rulecount = rules.items.len;
+
+    {
+        var index: u32 = 0;
+        while (index < othervals.items.len) {
+            var i: u32 = 0;
+            while (i < rulecount) : (i += 1) {
+                if (!hasRule(rules.items, othervals.items[index + i]))
+                    break;
+            }
+
+            if (i == rulecount) {
+                index += @intCast(u32, rulecount);
+            } else {
+                if (aoc.debug)
+                    aoc.debugfmt("REMOVE: ", .{});
+                i = 0;
+                while (i < rulecount) : (i += 1) {
+                    if (aoc.debug)
+                        aoc.debugfmt("{} ", .{othervals.items[index]});
+                    _ = othervals.orderedRemove(index);
+                }
+                if (aoc.debug)
+                    aoc.debugfmt("\n", .{});
+            }
+        }
+    }
+
+    var candidates = try allocator.alloc(u1, rulecount * rulecount);
+    defer allocator.free(candidates);
+    std.mem.set(u1, candidates, 1);
+
+    if (aoc.debug)
+        aoc.debugfmt("{}\n", .{othervals.items.len});
+    {
+        var index: u32 = 0;
+        while (index < othervals.items.len) : (index += 1) {
+            const ri = index % rulecount;
+            const v = othervals.items[index];
+            for (rules.items) |r, rri| {
+                if (!matchesRule(r, v)) {
+                    candidates[ri * rulecount + rri] = 0;
+                }
+            }
+        }
+    }
+
+    var answer: u64 = 1;
+    {
+        var index: u32 = 0;
+        while (index < rulecount * rulecount) : (index += 1) {
+            var ri = index % rulecount;
+            const cc = candidates[ri * rulecount .. (ri + 1) * rulecount];
+            if (std.mem.count(u1, cc, ([_]u1{1})[0..]) == 1) {
+                const field = std.mem.indexOfScalar(u1, cc, 1).?;
+                if (std.mem.indexOf(u8, rules.items[field].name, "departure") != null)
+                    answer *= ownvals.items[ri];
+                for (ownvals.items) |_, ii| {
+                    candidates[ii * rulecount + field] = 0;
+                }
+                if (aoc.debug) {
+                    printCandidates(candidates, rulecount, ri);
+                    aoc.debugfmt("\n", .{});
+                }
+            }
+        }
+    }
+
+    return try std.fmt.allocPrint(allocator, "{}", .{answer});
+}
+
+pub const main = aoc.main(part1, part2, .{ "25972", "622670335901" });