2022-15 part 1 in zig

3 files changed, 118 insertions, 0 deletions

diff --git a/2022/15-beacon-exclusion-zone/example b/2022/15-beacon-exclusion-zone/example
new file mode 100644
index 0000000..a612424
--- /dev/null
+++ b/2022/15-beacon-exclusion-zone/example
@@ -0,0 +1,14 @@
+Sensor at x=2, y=18: closest beacon is at x=-2, y=15
+Sensor at x=9, y=16: closest beacon is at x=10, y=16
+Sensor at x=13, y=2: closest beacon is at x=15, y=3
+Sensor at x=12, y=14: closest beacon is at x=10, y=16
+Sensor at x=10, y=20: closest beacon is at x=10, y=16
+Sensor at x=14, y=17: closest beacon is at x=10, y=16
+Sensor at x=8, y=7: closest beacon is at x=2, y=10
+Sensor at x=2, y=0: closest beacon is at x=2, y=10
+Sensor at x=0, y=11: closest beacon is at x=2, y=10
+Sensor at x=20, y=14: closest beacon is at x=25, y=17
+Sensor at x=17, y=20: closest beacon is at x=21, y=22
+Sensor at x=16, y=7: closest beacon is at x=15, y=3
+Sensor at x=14, y=3: closest beacon is at x=15, y=3
+Sensor at x=20, y=1: closest beacon is at x=15, y=3
diff --git a/2022/15-beacon-exclusion-zone/first.zig b/2022/15-beacon-exclusion-zone/first.zig
new file mode 100644
index 0000000..9263efc
--- /dev/null
+++ b/2022/15-beacon-exclusion-zone/first.zig
@@ -0,0 +1,71 @@
+const std = @import("std");
+
+const example = @embedFile("example");
+const input = @embedFile("input");
+
+var allocator: std.mem.Allocator = undefined;
+
+pub fn main() anyerror!void {
+    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
+    defer arena.deinit();
+    allocator = arena.allocator();
+
+    try std.testing.expectEqual(try solve(example, 10), 26);
+    const result = try solve(input, 2000000);
+    try std.io.getStdOut().writer().print("{}\n", .{result});
+}
+
+const Interval = struct {
+    l: i64,
+    r: i64,
+};
+
+fn lesserThan(context: void, a: *Interval, b: *Interval) bool {
+    _ = context;
+    return a.l < b.l;
+}
+
+fn solve(puzzle: []const u8, yline: i64) !i64 {
+    var it = std.mem.tokenize(u8, puzzle, "\n");
+    var intervals = std.ArrayList(*Interval).init(allocator);
+    // process input
+    while (it.next()) |line| {
+        var coords = std.mem.tokenize(u8, line, "Sensor at x=, y=: closest beacon is at x=, y=");
+        const sx = try std.fmt.parseInt(i64, coords.next() orelse continue, 10);
+        const sy = try std.fmt.parseInt(i64, coords.next() orelse unreachable, 10);
+        const bx = try std.fmt.parseInt(i64, coords.next() orelse unreachable, 10);
+        const by = try std.fmt.parseInt(i64, coords.next() orelse unreachable, 10);
+        const d = try std.math.absInt(sx - bx) + try std.math.absInt(sy - by);
+        if (sy - d > yline or sy + d < yline) {
+            continue;
+        }
+        const l = d - try std.math.absInt(yline - sy);
+        var i = try allocator.create(Interval);
+        i.* = Interval{ .l = sx - l, .r = sx + l };
+        try intervals.append(i);
+    }
+    // sort by left bound
+    std.sort.sort(*Interval, intervals.items, {}, lesserThan);
+    // Reduce intervals and compute results
+    var n: i64 = 0;
+    var i: usize = 0;
+    while (i < intervals.items.len) : (i += 1) {
+        var int = intervals.items[i];
+        var j = i + 1;
+        while (j < intervals.items.len) {
+            const jnt = intervals.items[j];
+            if (jnt.l <= int.r) { // jint overlaps
+                if (jnt.r > int.r) {
+                    int.r = jnt.r;
+                }
+                _ = intervals.orderedRemove(j);
+                continue;
+            } else {
+                break;
+            }
+            j += 1;
+        }
+        n = n + int.r - int.l;
+    }
+    return n;
+}
diff --git a/2022/15-beacon-exclusion-zone/input b/2022/15-beacon-exclusion-zone/input
new file mode 100644
index 0000000..e6a6df5
--- /dev/null
+++ b/2022/15-beacon-exclusion-zone/input
@@ -0,0 +1,33 @@
+Sensor at x=2302110, y=2237242: closest beacon is at x=2348729, y=1239977
+Sensor at x=47903, y=2473047: closest beacon is at x=-432198, y=2000000
+Sensor at x=2363579, y=1547888: closest beacon is at x=2348729, y=1239977
+Sensor at x=3619841, y=520506: closest beacon is at x=2348729, y=1239977
+Sensor at x=3941908, y=3526118: closest beacon is at x=3772294, y=3485243
+Sensor at x=3206, y=1564595: closest beacon is at x=-432198, y=2000000
+Sensor at x=3123411, y=3392077: closest beacon is at x=2977835, y=3592946
+Sensor at x=3279053, y=3984688: closest beacon is at x=2977835, y=3592946
+Sensor at x=2968162, y=3938490: closest beacon is at x=2977835, y=3592946
+Sensor at x=1772120, y=2862246: closest beacon is at x=2017966, y=3158243
+Sensor at x=3283241, y=2619168: closest beacon is at x=3172577, y=2521434
+Sensor at x=2471642, y=3890150: closest beacon is at x=2977835, y=3592946
+Sensor at x=3163348, y=3743489: closest beacon is at x=2977835, y=3592946
+Sensor at x=2933313, y=2919047: closest beacon is at x=3172577, y=2521434
+Sensor at x=2780640, y=3629927: closest beacon is at x=2977835, y=3592946
+Sensor at x=3986978, y=2079918: closest beacon is at x=3998497, y=2812428
+Sensor at x=315464, y=370694: closest beacon is at x=-550536, y=260566
+Sensor at x=3957316, y=3968366: closest beacon is at x=3772294, y=3485243
+Sensor at x=2118533, y=1074658: closest beacon is at x=2348729, y=1239977
+Sensor at x=3494855, y=3378533: closest beacon is at x=3772294, y=3485243
+Sensor at x=2575727, y=210553: closest beacon is at x=2348729, y=1239977
+Sensor at x=3999990, y=2813525: closest beacon is at x=3998497, y=2812428
+Sensor at x=3658837, y=3026912: closest beacon is at x=3998497, y=2812428
+Sensor at x=1551619, y=1701155: closest beacon is at x=2348729, y=1239977
+Sensor at x=2625855, y=3330422: closest beacon is at x=2977835, y=3592946
+Sensor at x=3476946, y=2445098: closest beacon is at x=3172577, y=2521434
+Sensor at x=2915568, y=1714113: closest beacon is at x=2348729, y=1239977
+Sensor at x=729668, y=3723377: closest beacon is at x=-997494, y=3617758
+Sensor at x=3631681, y=3801747: closest beacon is at x=3772294, y=3485243
+Sensor at x=2270816, y=3197807: closest beacon is at x=2017966, y=3158243
+Sensor at x=3999999, y=2810929: closest beacon is at x=3998497, y=2812428
+Sensor at x=3978805, y=3296024: closest beacon is at x=3772294, y=3485243
+Sensor at x=1054910, y=811769: closest beacon is at x=2348729, y=1239977