day10.zig (10400B)
1 const std = @import("std"); 2 3 pub fn main() !void { 4 try std.fmt.format(std.io.getStdOut().writer(), "day 10 pt1: {}\n", .{try solve_pt1(std.heap.page_allocator, puzzle_input)}); 5 try std.fmt.format(std.io.getStdOut().writer(), "day 10 pt2: {}\n", .{try solve_pt2(std.heap.page_allocator, puzzle_input)}); 6 } 7 8 const Direction = enum { north, east, south, west, 9 fn opp(self: Direction) Direction { 10 return switch (self) { 11 .north => .south, 12 .east => .west, 13 .south => .north, 14 .west => .east, 15 }; 16 } 17 }; 18 19 const Cell = enum(u8) { 20 NS = '|', 21 WE = '-', 22 NE = 'L', 23 NW = 'J', 24 SW = '7', 25 SE = 'F', 26 Ground = '.', 27 Start = 'S', 28 _, 29 30 fn next(self: Cell, whence: Direction) ?Direction { 31 // return switch (self) { 32 // .NS => switch (whence) { 33 // .north => .South, 34 // .south => .North, 35 // else => null, 36 // }, 37 // else => null, 38 // }; 39 // std.log.warn("whence {} cell {}", .{whence, self}); 40 return switch (whence) { 41 .north => switch (self) { 42 .NS => .south, 43 .NE => .east, 44 .NW => .west, 45 else => null, 46 }, 47 .east => switch (self) { 48 .WE => .west, 49 .NE => .north, 50 .SE => .south, 51 else => null, 52 }, 53 .south => switch (self) { 54 .NS => .north, 55 .SW => .west, 56 .SE => .east, 57 else => null, 58 }, 59 .west => switch (self) { 60 .WE => .east, 61 .NW => .north, 62 .SW => .south, 63 else => null, 64 }, 65 }; 66 } 67 68 fn from(d1: Direction, d2: Direction) !Cell { 69 return switch (d1) { 70 .north => switch (d2) { 71 .east => .NE, 72 .south => .NS, 73 .west => .NW, 74 else => error.Foo, 75 }, 76 .east => switch (d2) { 77 .north => .NE, 78 .south => .SE, 79 .west => .WE, 80 else => error.Foo, 81 }, 82 .south => switch (d2) { 83 .north => .NS, 84 .east => .SE, 85 .west => .SW, 86 else => error.Foo, 87 }, 88 .west => switch (d2) { 89 .north => .NW, 90 .east => .WE, 91 .south => .SW, 92 else => error.Foo, 93 } 94 }; 95 } 96 }; 97 98 const Coord = struct { 99 x: i64, 100 y: i64, 101 102 fn move(self: Coord, dir: Direction) Coord { 103 return switch (dir) { 104 .north => .{ .x = self.x, .y = self.y - 1 }, 105 .south => .{ .x = self.x, .y = self.y + 1 }, 106 .east => .{ .x = self.x + 1, .y = self.y }, 107 .west => .{ .x = self.x - 1, .y = self.y }, 108 }; 109 } 110 }; 111 112 const Path = struct { 113 grid: *const Grid, 114 current: Coord, 115 // Doesn't include .current 116 trail: std.AutoArrayHashMap(Coord, bool), 117 // direction we travelled to get to .current 118 whence: Direction, 119 120 // Figure out what the start cell _should_ be to complete the path 121 // essentially it's a wildcard. Should be a combination of the initial 122 // direction plus the final one... 123 start_equiv: Cell = Cell.Start, 124 125 fn deinit(self: *Path) void { 126 self.trail.deinit(); 127 } 128 129 // return a ray from x=0.. to the supplied coordinate. 130 // including only cells which are part of the trail 131 // and are not tangents (i.e. `-`) 132 fn ray(self: Path, a: std.mem.Allocator, c: Coord) ![]const Cell { 133 var al = std.ArrayList(Cell).init(a); 134 defer al.deinit(); 135 for (0..@intCast(c.x)) |x| { 136 const cp: Coord = .{.x = @intCast(x), .y = c.y}; 137 if (self.is_path(cp)) { 138 var cpp = self.grid.get(cp) orelse @panic("borken path"); 139 if (cpp == .Start) { 140 cpp = self.start_equiv; 141 } 142 if (cpp == .WE) { // skip 143 continue; 144 } 145 try al.append(cpp); 146 } 147 } 148 return try al.toOwnedSlice(); 149 } 150 151 fn is_path(self: Path, c: Coord) bool { 152 return self.trail.getKey(c) != null; 153 } 154 }; 155 156 const Grid = struct { 157 data: []const u8, 158 width: usize, 159 height: usize, 160 start: Coord, 161 162 fn parse(input: []const u8) !Grid { 163 var grid: Grid = undefined; 164 grid.data = input; 165 grid.width = std.mem.indexOfScalar(u8, input, '\n') orelse return error.Foo; 166 grid.height = std.mem.count(u8, input, "\n") + 1; 167 grid.start = lp1: for (0..grid.width) |x| { 168 for (0..grid.height) |y| { 169 const coord: Coord = .{ .x = @intCast(x), .y = @intCast(y) }; 170 if (grid.get(coord) == .Start) { 171 break :lp1 coord; 172 } 173 } 174 } else { 175 return error.NoStart; 176 }; 177 return grid; 178 } 179 180 fn get(self: Grid, c: Coord) ?Cell { 181 if (c.x < 0) return null; 182 if (c.y < 0) return null; 183 if (c.x >= self.width) return null; 184 if (c.y >= self.height) return null; 185 return @enumFromInt(self.data[@intCast(c.x + (c.y * (@as(i64, @intCast(self.width)) + 1)))]); // skip the newline 186 } 187 188 fn findLoop(self: *const Grid, a: std.mem.Allocator) !Path { 189 return lp1: for (std.enums.values(Direction)) |dir| { 190 const st = self.start.move(dir); 191 // std.log.warn("st {any}", .{st}); 192 _ = self.get(st) orelse continue :lp1; 193 var trail = std.AutoArrayHashMap(Coord, bool).init(a); 194 defer trail.deinit(); 195 try trail.put(self.start, true); 196 var path: Path = .{ 197 .current = st, 198 .grid = self, 199 .trail = trail, 200 .whence = dir.opp(), 201 }; 202 while (true) { 203 const cell: Cell = self.get(path.current) orelse { 204 // std.log.warn("out of bounds", .{}); 205 continue :lp1; 206 }; // out of bounds 207 if (cell == .Start) { 208 break :lp1 Path{ 209 .current = path.current, 210 .grid = path.grid, 211 .trail = try trail.clone(), 212 .whence = path.whence, 213 .start_equiv = try Cell.from(dir, path.whence), 214 }; 215 } // we found it yay 216 const dirn = cell.next(path.whence) orelse { 217 // std.log.warn("pipe mismatch", .{}); 218 continue :lp1; 219 }; // pipes don't match up 220 const newpos = path.current.move(dirn); 221 path.whence = dirn.opp(); 222 try trail.put(path.current, true); 223 path.current = newpos; 224 } 225 } else { 226 return error.NoLoop; 227 }; 228 } 229 }; 230 231 232 233 fn solve_pt1(a: std.mem.Allocator, input: []const u8) !u64 { 234 const grid = try Grid.parse(input); 235 var loop = try grid.findLoop(a); 236 defer loop.deinit(); 237 return loop.trail.unmanaged.entries.len / 2; 238 } 239 240 test "pt1_1" { 241 try std.testing.expectEqual(@as(u64, 4), try solve_pt1(std.testing.allocator, test_input1)); 242 } 243 244 const test_input1 = 245 \\..... 246 \\.S-7. 247 \\.|.|. 248 \\.L-J. 249 \\..... 250 ; 251 252 fn solve_pt2(a: std.mem.Allocator, input: []const u8) !u64 { 253 const grid = try Grid.parse(input); 254 var loop = try grid.findLoop(a); 255 defer loop.deinit(); 256 // scan the grid, raycast 257 var res: u64 = 0; 258 var enclosed_coords = std.AutoArrayHashMap(Coord, bool).init(a); 259 defer enclosed_coords.deinit(); 260 for (0..grid.width) |x| for (0..grid.height) |y| { 261 const c: Coord = .{.x = @intCast(x), .y = @intCast(y)}; 262 // Skip any coords which are actually part of the path 263 if (loop.is_path(c)) continue; 264 const ray = try loop.ray(a, c); 265 //std.log.warn("checking ray {any}", .{ray}); 266 defer a.free(ray); 267 // F7 counts 0 268 // LJ counts 0 269 // L7 counts 1 270 // FJ counts 1 271 // | counts 1 272 // so we could iterate, and only count J / 7 if they are preceeded by F / L 273 var ct: usize = 0; 274 for (ray, 0..) |cell, ix| { 275 if (cell == .NS) { 276 ct += 1; 277 } else if (cell == .SW) { 278 if (ix > 0) { 279 const prev = ray[ix-1]; 280 if (prev == .NE) { 281 ct += 1; 282 } 283 } 284 } else if (cell == .NW) { 285 if (ix > 0) { 286 const prev = ray[ix-1]; 287 if (prev == .SE) { 288 ct += 1; 289 } 290 } 291 } 292 } 293 if (@mod(ct, 2) == 1) { 294 // it's a inside cell 295 //std.log.warn("{any}", .{ray}); 296 try enclosed_coords.put(c, true); 297 res += 1; 298 } else { 299 // it's a outside cell, ignore it! 300 } 301 }; 302 303 // debug print 304 // var w = std.io.getStdOut().writer(); 305 // for (0..grid.height) |y| { 306 // for (0..grid.width) |x| { 307 // const c: Coord = .{.x = @intCast(x), .y = @intCast(y)}; 308 // const cell:u8 = if (enclosed_coords.getKey(c) == null) 309 // @intFromEnum(grid.get(c) orelse @panic("bork")) 310 // else 311 // 'I' 312 // ; 313 // try w.writeByte(cell); 314 // } 315 // try w.writeByte('\n'); 316 // } 317 return res; 318 } 319 320 test "pt2" { 321 try std.testing.expectEqual(@as(u64, 1), try solve_pt2(std.testing.allocator, test_input1)); 322 } 323 test "pt2_2" { 324 try std.testing.expectEqual(@as(u64, 10), try solve_pt2(std.testing.allocator, test_input2)); 325 } 326 327 const test_input2 = 328 \\FF7FSF7F7F7F7F7F---7 329 \\L|LJ||||||||||||F--J 330 \\FL-7LJLJ||||||LJL-77 331 \\F--JF--7||LJLJ7F7FJ- 332 \\L---JF-JLJ.||-FJLJJ7 333 \\|F|F-JF---7F7-L7L|7| 334 \\|FFJF7L7F-JF7|JL---7 335 \\7-L-JL7||F7|L7F-7F7| 336 \\L.L7LFJ|||||FJL7||LJ 337 \\L7JLJL-JLJLJL--JLJ.L 338 ; 339 const puzzle_input = @embedFile("day10.in");