Very ugly p2 but i guess it fine for small inputs like this.
Part 1 & 2
const std = @import("std");
const util = @import("util.zig");
const gpa = util.gpa;
const data = @embedFile("data/day12.txt");
const Point = struct { x: usize, y: usize };
const lim = 140;
var grid = [_][lim]u8{[_]u8{undefined} ** lim} ** lim;
var visited = [_][lim]bool{[_]bool{false} ** lim} ** lim;
pub fn main() !void {
var p1: u32 = 0;
var p2: u32 = 0;
var idx: usize = 0;
var lines = std.mem.tokenizeScalar(u8, data, '\n');
while (lines.next()) |line| : (idx += 1) {
grid[idx] = line[0..lim].*;
}
for (0..lim) |i| {
for (0..lim) |j| {
const res = try region_cost(i, j);
p1 += res.p1;
p2 += res.p2;
}
}
std.debug.print("part1: {}\n", .{p1});
std.debug.print("part2: {}\n", .{p2});
}
fn region_cost(x_start: usize, y_start: usize) !struct { p1: u32, p2: u32 } {
if (visited[x_start][y_start]) return .{ .p1 = 0, .p2 = 0 };
var stack = std.ArrayList(Point).init(gpa);
try stack.append(Point{ .x = x_start, .y = y_start });
const char = grid[x_start][y_start];
visited[x_start][y_start] = true;
var area: u32 = 0;
var borders_count: u32 = 0;
var borders: [4]std.ArrayList(Point) = undefined;
for (0..4) |i| {
borders[i] = std.ArrayList(Point).init(gpa);
}
while (stack.items.len != 0) {
const current = stack.pop();
const x = current.x;
const y = current.y;
area += 1;
borders_count += try check_borders(x, y, char, &borders);
if (x > 0 and grid[x - 1][y] == char and !visited[x - 1][y]) {
visited[x - 1][y] = true;
try stack.append(.{ .x = x - 1, .y = y });
}
if (x < lim - 1 and grid[x + 1][y] == char and !visited[x + 1][y]) {
visited[x + 1][y] = true;
try stack.append(Point{ .x = x + 1, .y = y });
}
if (y > 0 and grid[x][y - 1] == char and !visited[x][y - 1]) {
visited[x][y - 1] = true;
try stack.append(Point{ .x = x, .y = y - 1 });
}
if (y < lim - 1 and grid[x][y + 1] == char and !visited[x][y + 1]) {
visited[x][y + 1] = true;
try stack.append(Point{ .x = x, .y = y + 1 });
}
}
std.mem.sort(Point, borders[0].items, {}, cmp_y);
std.mem.sort(Point, borders[0].items, {}, cmp_x);
std.mem.sort(Point, borders[1].items, {}, cmp_y);
std.mem.sort(Point, borders[1].items, {}, cmp_x);
std.mem.sort(Point, borders[2].items, {}, cmp_x);
std.mem.sort(Point, borders[2].items, {}, cmp_y);
std.mem.sort(Point, borders[3].items, {}, cmp_x);
std.mem.sort(Point, borders[3].items, {}, cmp_y);
var sides: u32 = 4;
for (0..4) |i| {
for (0..borders[i].items.len - 1) |j| {
if (i < 2) {
if (borders[i].items[j].y + 1 != borders[i].items[j + 1].y or borders[i].items[j].x != borders[i].items[j + 1].x)
sides += 1;
} else {
if (borders[i].items[j].x + 1 != borders[i].items[j + 1].x or borders[i].items[j].y != borders[i].items[j + 1].y)
sides += 1;
}
}
}
return .{ .p1 = area * borders_count, .p2 = area * sides };
}
fn check_borders(x: usize, y: usize, char: u8, borders: *[4]std.ArrayList(Point)) !u32 {
var borders_count: u32 = 0;
if (x == 0 or grid[x - 1][y] != char) {
try borders[0].append(Point{ .x = x, .y = y });
borders_count += 1;
}
if (x == lim - 1 or grid[x + 1][y] != char) {
try borders[1].append(Point{ .x = x, .y = y });
borders_count += 1;
}
if (y == 0 or grid[x][y - 1] != char) {
try borders[2].append(Point{ .x = x, .y = y });
borders_count += 1;
}
if (y == lim - 1 or grid[x][y + 1] != char) {
try borders[3].append(Point{ .x = x, .y = y });
borders_count += 1;
}
return borders_count;
}
fn cmp_x(_: void, a: Point, b: Point) bool {
return a.x < b.x;
}
fn cmp_y(_: void, a: Point, b: Point) bool {
return a.y < b.y;
}