Day 10 pt2, eventually.

It's not pretty

1 files changed, 212 insertions, 63 deletions

diff --git a/day10.zig b/day10.zig
index 3d52a1f..2eda042 100644
--- a/day10.zig
+++ b/day10.zig
@@ -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");