diff options
| -rw-r--r-- | 2022/15-beacon-exclusion-zone/example | 14 | ||||
| -rw-r--r-- | 2022/15-beacon-exclusion-zone/first.zig | 71 | ||||
| -rw-r--r-- | 2022/15-beacon-exclusion-zone/input | 33 |
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 |