summaryrefslogtreecommitdiff
path: root/src/day12.zig
diff options
context:
space:
mode:
authorXander Bil <xander@biltopia.org>2024-12-13 22:17:20 +0100
committerXander Bil <xander@biltopia.org>2024-12-13 22:17:20 +0100
commit7579dfa5138906e627c50177d25de7f5d9f147f1 (patch)
tree2e2c149cf053f410bfb1566ac00f2d3b7068fd42 /src/day12.zig
parent45bd0d906ecc1864c42402fd88288666ec4b46ab (diff)
downloadaoc2024-main.tar.xz
aoc2024-main.zip
add solution day12HEADmain
Diffstat (limited to 'src/day12.zig')
-rw-r--r--src/day12.zig143
1 files changed, 143 insertions, 0 deletions
diff --git a/src/day12.zig b/src/day12.zig
new file mode 100644
index 0000000..32fca4b
--- /dev/null
+++ b/src/day12.zig
@@ -0,0 +1,143 @@
+const std = @import("std");
+const mecha = @import("mecha");
+const print = std.debug.print;
+
+pub fn solve(part: []u8, buffer: []u8, allocator: std.mem.Allocator) !void {
+ if (std.mem.eql(u8, part, "1")) {
+ try part1(buffer, allocator);
+ } else {
+ try part2(buffer, allocator);
+ }
+}
+
+fn recursive(mapped: [][]bool, grid: [][]const u8, r: i32, c: i32, region: u8) std.meta.Tuple(&.{ usize, usize }) {
+ if (r >= 0 and r < grid.len and c >= 0 and c < grid[@intCast(r)].len and grid[@intCast(r)][@intCast(c)] == region) {
+ if (!mapped[@intCast(r)][@intCast(c)]) {
+ mapped[@intCast(r)][@intCast(c)] = true;
+ const up = recursive(mapped, grid, r - 1, c, region);
+ const down = recursive(mapped, grid, r + 1, c, region);
+ const left = recursive(mapped, grid, r, c - 1, region);
+ const right = recursive(mapped, grid, r, c + 1, region);
+ return .{ 1 + up[0] + down[0] + left[0] + right[0], up[1] + down[1] + left[1] + right[1] };
+ } else {
+ return .{ 0, 0 };
+ }
+ } else {
+ return .{ 0, 1 };
+ }
+}
+
+fn part1(buffer: []const u8, allocator: std.mem.Allocator) !void {
+ var lines = std.mem.splitScalar(u8, buffer, '\n');
+
+ var grid = std.ArrayList([]const u8).init(allocator);
+ defer grid.deinit();
+
+ var mapped = std.ArrayList([]bool).init(allocator);
+ defer mapped.deinit();
+
+ while (lines.next()) |line| {
+ try grid.append(line);
+
+ const mapped_row = try allocator.alloc(bool, line.len);
+ @memset(mapped_row, false);
+ try mapped.append(mapped_row);
+ }
+
+ var output: usize = 0;
+ for (grid.items, 0..) |row, ri| {
+ for (row, 0..) |item, ci| {
+ if (!mapped.items[ri][ci]) {
+ const plot = recursive(mapped.items, grid.items, @intCast(ri), @intCast(ci), item);
+ output += plot[0] * plot[1];
+ }
+ }
+ }
+
+ for (mapped.items) |mapped_row| {
+ allocator.free(mapped_row);
+ }
+
+ print("{d}\n", .{output});
+}
+
+//----------------------------------PART2-----------------------------
+
+fn recursive2(mapped: [][]bool, grid: [][]const u8, pr: i32, pc: i32, r: i32, c: i32, region: u8, perimeters: *std.AutoHashMap(std.meta.Tuple(&.{ bool, i32, i32, i32, i32 }), void)) !usize {
+ if (r >= 0 and r < grid.len and c >= 0 and c < grid[@intCast(r)].len and grid[@intCast(r)][@intCast(c)] == region) {
+ if (!mapped[@intCast(r)][@intCast(c)]) {
+ mapped[@intCast(r)][@intCast(c)] = true;
+ const up = try recursive2(mapped, grid, r, c, r - 1, c, region, perimeters);
+ const down = try recursive2(mapped, grid, r, c, r + 1, c, region, perimeters);
+ const left = try recursive2(mapped, grid, r, c, r, c - 1, region, perimeters);
+ const right = try recursive2(mapped, grid, r, c, r, c + 1, region, perimeters);
+ return 1 + up + down + left + right;
+ } else {
+ return 0;
+ }
+ } else {
+ const key: std.meta.Tuple(&.{ bool, i32, i32, i32, i32 }) = .{ (c < pc or r < pr), r, c, @intCast(@abs(c - pc)), @intCast(@abs(r - pr)) };
+ try perimeters.put(key, {});
+ return 0;
+ }
+}
+
+fn find_edge(b: bool, rr: i32, cc: i32, dr: i32, dc: i32, perimeters: std.AutoHashMap(std.meta.Tuple(&.{ bool, i32, i32, i32, i32 }), void), seen: *std.AutoHashMap(std.meta.Tuple(&.{ bool, i32, i32, i32, i32 }), void)) !void {
+ var r = rr + dr;
+ var c = cc + dc;
+ var key: std.meta.Tuple(&.{ bool, i32, i32, i32, i32 }) = .{ b, r, c, @intCast(@abs(dr)), @intCast(@abs(dc)) };
+ while (perimeters.contains(key) and !seen.contains(key)) : (key = .{ b, r, c, @intCast(@abs(dr)), @intCast(@abs(dc)) }) {
+ try seen.put(key, {});
+ r += dr;
+ c += dc;
+ }
+}
+
+fn part2(buffer: []const u8, allocator: std.mem.Allocator) !void {
+ var lines = std.mem.splitScalar(u8, buffer, '\n');
+
+ var grid = std.ArrayList([]const u8).init(allocator);
+ defer grid.deinit();
+
+ var mapped = std.ArrayList([]bool).init(allocator);
+ defer mapped.deinit();
+
+ while (lines.next()) |line| {
+ if (line.len == 0) break;
+ try grid.append(line);
+
+ const mapped_row = try allocator.alloc(bool, line.len);
+ @memset(mapped_row, false);
+ try mapped.append(mapped_row);
+ }
+
+ var output: usize = 0;
+ for (grid.items, 0..) |row, ri| {
+ for (row, 0..) |item, ci| {
+ if (!mapped.items[ri][ci]) {
+ var perimeters = std.AutoHashMap(std.meta.Tuple(&.{ bool, i32, i32, i32, i32 }), void).init(allocator);
+ defer perimeters.deinit();
+
+ const area = try recursive2(mapped.items, grid.items, @intCast(ri), @intCast(ci), @intCast(ri), @intCast(ci), item, &perimeters);
+ var seen = std.AutoHashMap(std.meta.Tuple(&.{ bool, i32, i32, i32, i32 }), void).init(allocator);
+ defer seen.deinit();
+ var iterator = perimeters.keyIterator();
+ var edge_count: usize = 0;
+ while (iterator.next()) |key| {
+ if (!seen.contains(key.*)) {
+ try find_edge(key[0], key[1], key[2], key[3], key[4], perimeters, &seen);
+ try find_edge(key[0], key[1], key[2], -1 * key[3], -1 * key[4], perimeters, &seen);
+ edge_count += 1;
+ }
+ }
+ output += area * edge_count;
+ }
+ }
+ }
+
+ for (mapped.items) |mapped_row| {
+ allocator.free(mapped_row);
+ }
+
+ print("{d}\n", .{output});
+}