aboutsummaryrefslogtreecommitdiff
path: root/2022/15-beacon-exclusion-zone
diff options
context:
space:
mode:
Diffstat (limited to '2022/15-beacon-exclusion-zone')
-rw-r--r--2022/15-beacon-exclusion-zone/example14
-rw-r--r--2022/15-beacon-exclusion-zone/first.zig71
-rw-r--r--2022/15-beacon-exclusion-zone/input33
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