path: root/day10.zig

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, 
    fn opp(self: Direction) Direction {
        return switch (self) {
            .north => .south,
            .east => .west,
            .south => .north,
            .west => .east,
        };
    }
};

const Cell = enum(u8) {
    NS = '|',
    WE = '-',
    NE = 'L',
    NW = 'J',
    SW = '7',
    SE = 'F',
    Ground = '.',
    Start = 'S',
    _,

    fn next(self: Cell, whence: Direction) ?Direction {
        // return switch (self) {
        //     .NS => switch (whence) {
        //         .north => .South,
        //         .south => .North,
        //         else => null,
        //     },
        //     else => null,
        // };
        // std.log.warn("whence {} cell {}", .{whence, self});
        return switch (whence) {
            .north => switch (self) {
                .NS => .south,
                .NE => .east,
                .NW => .west,
                else => null,
            },
            .east => switch (self) {
                .WE => .west,
                .NE => .north,
                .SE => .south,
                else => null,
            },
            .south => switch (self) {
                .NS => .north,
                .SW => .west,
                .SE => .east,
                else => null,
            },
            .west => switch (self) {
                .WE => .east,
                .NW => .north,
                .SW => .south,
                else => null,
            },
        };
    }

    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 {
    x: i64,
    y: i64,

    fn move(self: Coord, dir: Direction) Coord {
        return switch (dir) {
            .north => .{ .x = self.x, .y = self.y - 1 },
            .south => .{ .x = self.x, .y = self.y + 1 },
            .east => .{ .x = self.x + 1, .y = self.y },
            .west => .{ .x = self.x - 1, .y = self.y },
        };
    }
};

const Path = struct {
    grid: *const Grid,
    current: Coord,
    // Doesn't include .current
    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 {
        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 {
        if (c.x < 0) return null;
        if (c.y < 0) return null;
        if (c.x >= self.width) return null;
        if (c.y >= self.height) return null;
        return @enumFromInt(self.data[@intCast(c.x + (c.y * (@as(i64, @intCast(self.width)) + 1)))]); // skip the newline
    }

    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;
            }
        } else {
            return error.NoLoop;
        };    
    }
};



fn solve_pt1(a: std.mem.Allocator, input: []const u8) !u64 {
    const grid = try Grid.parse(input);
    var loop = try grid.findLoop(a);
    defer loop.deinit();
    return loop.trail.unmanaged.entries.len / 2;
}

test "pt1_1" {
    try std.testing.expectEqual(@as(u64, 4), try solve_pt1(std.testing.allocator, test_input1));
}

const test_input1 =
    \\.....
    \\.S-7.
    \\.|.|.
    \\.L-J.
    \\.....
;

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");