diff options
| -rw-r--r-- | day10.zig | 275 |
1 files changed, 212 insertions, 63 deletions
@@ -2,6 +2,7 @@ const std = @import("std"); pub fn main() !void { try std.fmt.format(std.io.getStdOut().writer(), "day 10 pt1: {}\n", .{try solve_pt1(std.heap.page_allocator, puzzle_input)}); + try std.fmt.format(std.io.getStdOut().writer(), "day 10 pt2: {}\n", .{try solve_pt2(std.heap.page_allocator, puzzle_input)}); } const Direction = enum { north, east, south, west, @@ -63,6 +64,35 @@ const Cell = enum(u8) { }, }; } + + fn from(d1: Direction, d2: Direction) !Cell { + return switch (d1) { + .north => switch (d2) { + .east => .NE, + .south => .NS, + .west => .NW, + else => error.Foo, + }, + .east => switch (d2) { + .north => .NE, + .south => .SE, + .west => .WE, + else => error.Foo, + }, + .south => switch (d2) { + .north => .NS, + .east => .SE, + .west => .SW, + else => error.Foo, + }, + .west => switch (d2) { + .north => .NW, + .east => .WE, + .south => .SW, + else => error.Foo, + } + }; + } }; const Coord = struct { @@ -83,22 +113,68 @@ const Path = struct { grid: *const Grid, current: Coord, // Doesn't include .current - trail: std.ArrayList(Coord), + trail: std.AutoArrayHashMap(Coord, bool), // direction we travelled to get to .current whence: Direction, + + // Figure out what the start cell _should_ be to complete the path + // essentially it's a wildcard. Should be a combination of the initial + // direction plus the final one... + start_equiv: Cell = Cell.Start, + + fn deinit(self: *Path) void { + self.trail.deinit(); + } + + // return a ray from x=0.. to the supplied coordinate. + // including only cells which are part of the trail + // and are not tangents (i.e. `-`) + fn ray(self: Path, a: std.mem.Allocator, c: Coord) ![]const Cell { + var al = std.ArrayList(Cell).init(a); + defer al.deinit(); + for (0..@intCast(c.x)) |x| { + const cp: Coord = .{.x = @intCast(x), .y = c.y}; + if (self.is_path(cp)) { + var cpp = self.grid.get(cp) orelse @panic("borken path"); + if (cpp == .Start) { + cpp = self.start_equiv; + } + if (cpp == .WE) { // skip + continue; + } + try al.append(cpp); + } + } + return try al.toOwnedSlice(); + } + + fn is_path(self: Path, c: Coord) bool { + return self.trail.getKey(c) != null; + } }; const Grid = struct { data: []const u8, width: usize, height: usize, + start: Coord, fn parse(input: []const u8) !Grid { - return .{ - .data = input, - .width = std.mem.indexOfScalar(u8, input, '\n') orelse return error.Foo, - .height = std.mem.count(u8, input, "\n") + 1, + var grid: Grid = undefined; + grid.data = input; + grid.width = std.mem.indexOfScalar(u8, input, '\n') orelse return error.Foo; + grid.height = std.mem.count(u8, input, "\n") + 1; + grid.start = lp1: for (0..grid.width) |x| { + for (0..grid.height) |y| { + const coord: Coord = .{ .x = @intCast(x), .y = @intCast(y) }; + if (grid.get(coord) == .Start) { + break :lp1 coord; + } + } + } else { + return error.NoStart; }; + return grid; } fn get(self: Grid, c: Coord) ?Cell { @@ -109,70 +185,56 @@ const Grid = struct { return @enumFromInt(self.data[@intCast(c.x + (c.y * (@as(i64, @intCast(self.width)) + 1)))]); // skip the newline } - fn findStart(self: Grid) ?Coord { - for (0..self.width) |x| { - for (0..self.height) |y| { - const coord: Coord = .{ .x = @intCast(x), .y = @intCast(y) }; - //std.log.warn("checking {any} for start", .{coord}); - if (self.get(coord) == .Start) { - return coord; - } + fn findLoop(self: *const Grid, a: std.mem.Allocator) !Path { + return lp1: for (std.enums.values(Direction)) |dir| { + const st = self.start.move(dir); + // std.log.warn("st {any}", .{st}); + _ = self.get(st) orelse continue :lp1; + var trail = std.AutoArrayHashMap(Coord, bool).init(a); + defer trail.deinit(); + try trail.put(self.start, true); + var path: Path = .{ + .current = st, + .grid = self, + .trail = trail, + .whence = dir.opp(), + }; + while (true) { + const cell: Cell = self.get(path.current) orelse { + // std.log.warn("out of bounds", .{}); + continue :lp1; + }; // out of bounds + if (cell == .Start) { + break :lp1 Path{ + .current = path.current, + .grid = path.grid, + .trail = try trail.clone(), + .whence = path.whence, + .start_equiv = try Cell.from(dir, path.whence), + }; + } // we found it yay + const dirn = cell.next(path.whence) orelse { + // std.log.warn("pipe mismatch", .{}); + continue :lp1; + }; // pipes don't match up + const newpos = path.current.move(dirn); + path.whence = dirn.opp(); + try trail.put(path.current, true); + path.current = newpos; } - } - return null; + } else { + return error.NoLoop; + }; } }; + + fn solve_pt1(a: std.mem.Allocator, input: []const u8) !u64 { - // read the Grid - // find the start pos - // setup 4 Paths on each NESW from S and follow them through, one of them - // will link up back to S. - // half the trail length gives the answer. const grid = try Grid.parse(input); - // std.log.warn("grid width {} height {}", .{ grid.width, grid.height }); - - const start: Coord = grid.findStart() orelse return error.NoStart; - - const loop: Path = lp1: for (std.enums.values(Direction)) |dir| { - const st = start.move(dir); - // std.log.warn("st {any}", .{st}); - _ = grid.get(st) orelse continue :lp1; - var trail = std.ArrayList(Coord).init(a); - defer trail.deinit(); - try trail.append(start); - var path: Path = .{ - .current = st, - .grid = &grid, - .trail = trail, - .whence = dir.opp(), - }; - while (true) { - const cell: Cell = grid.get(path.current) orelse { - // std.log.warn("out of bounds", .{}); - continue :lp1; - }; // out of bounds - if (cell == .Start) break :lp1 Path{ - .current = path.current, - .grid = path.grid, - .trail = try trail.clone(), - .whence = path.whence, - }; // we found it yay - const dirn = cell.next(path.whence) orelse { - // std.log.warn("pipe mismatch", .{}); - continue :lp1; - }; // pipes don't match up - const newpos = path.current.move(dirn); - path.whence = dirn.opp(); - try trail.append(path.current); - path.current = newpos; - } - } else { - return error.NoLoop; - }; - defer loop.trail.deinit(); - // std.log.warn("loop {any}", .{loop}); - return loop.trail.items.len / 2; + var loop = try grid.findLoop(a); + defer loop.deinit(); + return loop.trail.unmanaged.entries.len / 2; } test "pt1_1" { @@ -187,4 +249,91 @@ const test_input1 = \\..... ; +fn solve_pt2(a: std.mem.Allocator, input: []const u8) !u64 { + const grid = try Grid.parse(input); + var loop = try grid.findLoop(a); + defer loop.deinit(); + // scan the grid, raycast + var res: u64 = 0; + var enclosed_coords = std.AutoArrayHashMap(Coord, bool).init(a); + defer enclosed_coords.deinit(); + for (0..grid.width) |x| for (0..grid.height) |y| { + const c: Coord = .{.x = @intCast(x), .y = @intCast(y)}; + // Skip any coords which are actually part of the path + if (loop.is_path(c)) continue; + const ray = try loop.ray(a, c); + //std.log.warn("checking ray {any}", .{ray}); + defer a.free(ray); + // F7 counts 0 + // LJ counts 0 + // L7 counts 1 + // FJ counts 1 + // | counts 1 + // so we could iterate, and only count J / 7 if they are preceeded by F / L + var ct: usize = 0; + for (ray, 0..) |cell, ix| { + if (cell == .NS) { + ct += 1; + } else if (cell == .SW) { + if (ix > 0) { + const prev = ray[ix-1]; + if (prev == .NE) { + ct += 1; + } + } + } else if (cell == .NW) { + if (ix > 0) { + const prev = ray[ix-1]; + if (prev == .SE) { + ct += 1; + } + } + } + } + if (@mod(ct, 2) == 1) { + // it's a inside cell + //std.log.warn("{any}", .{ray}); + try enclosed_coords.put(c, true); + res += 1; + } else { + // it's a outside cell, ignore it! + } + }; + + // debug print + // var w = std.io.getStdOut().writer(); + // for (0..grid.height) |y| { + // for (0..grid.width) |x| { + // const c: Coord = .{.x = @intCast(x), .y = @intCast(y)}; + // const cell:u8 = if (enclosed_coords.getKey(c) == null) + // @intFromEnum(grid.get(c) orelse @panic("bork")) + // else + // 'I' + // ; + // try w.writeByte(cell); + // } + // try w.writeByte('\n'); + // } + return res; +} + +test "pt2" { + try std.testing.expectEqual(@as(u64, 1), try solve_pt2(std.testing.allocator, test_input1)); +} +test "pt2_2" { + try std.testing.expectEqual(@as(u64, 10), try solve_pt2(std.testing.allocator, test_input2)); +} + +const test_input2 = +\\FF7FSF7F7F7F7F7F---7 +\\L|LJ||||||||||||F--J +\\FL-7LJLJ||||||LJL-77 +\\F--JF--7||LJLJ7F7FJ- +\\L---JF-JLJ.||-FJLJJ7 +\\|F|F-JF---7F7-L7L|7| +\\|FFJF7L7F-JF7|JL---7 +\\7-L-JL7||F7|L7F-7F7| +\\L.L7LFJ|||||FJL7||LJ +\\L7JLJL-JLJLJL--JLJ.L +; const puzzle_input = @embedFile("day10.in"); |