voroskoi/aoc2023-zig - Change TD4SGIRCNYDNS236UXIX45QYRWQ7RXUDNFZYBBQT2ZBHX2DXQDZQC

Solve day10 part 2

Created by voroskoi on August 20, 2024

TD4SGIRCNYDNS236UXIX45QYRWQ7RXUDNFZYBBQT2ZBHX2DXQDZQC

Dependencies

[2] ZDMTU27LTEU62GCEHHEDXWMUW2YJUS4U3FFN7G5624XGXIQL3Z5QC

In channels

main

Change contents

Insertion in src/day10.zig at line 7 [2.123]

[2.233]

const COST_ROWS = GRID_ROWS;
const COST_COLS = GRID_COLS;

Replacement in src/day10.zig at line 11 [2.123]
B:BD[2.255] → [2.255:278]
```
const Pipes = struct {
```
[2.255]
[2.278]
```
const Maze = struct {
```
Insertion in src/day10.zig at line 13 [2.123]
[2.314]
[2.314]
```
    visited: [GRID_ROWS][GRID_COLS]bool,
```
Insertion in src/day10.zig at line 20 [2.123]
[2.502]
[2.502]
```
    var maze = try parseInput(input);
```

Replacement in src/day10.zig at line 23 [2.123]

B:BD[2.503] → [2.503:542]

    var pipes = try parseInput(input);

[2.503]

[2.542]

    var cost_grid = [_][COST_COLS]CostType{[_]CostType{std.math.maxInt(CostType)} ** COST_COLS} ** COST_ROWS;
    cost_grid[maze.start[0]][maze.start[1]] = 0;

Replacement in src/day10.zig at line 26 [2.123]

B:BD[2.543] → [2.543:704]

    var cost_grid = [_][GRID_COLS]CostType{[_]CostType{std.math.maxInt(CostType)} ** GRID_COLS} ** GRID_ROWS;
    cost_grid[pipes.start[0]][pipes.start[1]] = 0;

[2.543]

[2.704]

    const start_pipe = try detectStart(maze);
    maze.grid[maze.start[0]][maze.start[1]] = start_pipe; // set proper S value

Replacement in src/day10.zig at line 29 [2.123]

B:BD[2.705] → [2.705:768]

    try dijkstra(std.heap.page_allocator, &pipes, &cost_grid);

[2.705]

[2.768]

    try dijkstra(allocator, &maze, &cost_grid);

Insertion in src/day10.zig at line 47 [2.123]
[2.1203]
[2.1203]
```
    var maze = try parseInput(input);
```

Replacement in src/day10.zig at line 50 [2.123]

B:BD[2.1204] → [2.1204:1218]

    return 1;

[2.1204]

[2.1218]

    var cost_grid = [_][COST_COLS]CostType{[_]CostType{std.math.maxInt(CostType)} ** COST_COLS} ** COST_ROWS;
    cost_grid[maze.start[0]][maze.start[1]] = 0;
    const start_pipe = try detectStart(maze);
    maze.grid[maze.start[0]][maze.start[1]] = start_pipe; // set proper S value
    try dijkstra(allocator, &maze, &cost_grid);
    var enclosed: usize = 0;
    for (cost_grid, 0..) |line, row| {
        for (line, 0..) |_, col| {
            if (maze.visited[row][col]) {
                // std.debug.print("{c}", .{maze.grid[row][col]});
                continue; // only check items _NOT_ in the main loop
            }
            var cuts: usize = 0;
            for (0..col) |c| {
                if (!maze.visited[row][c]) continue; // only count cuts with the main loop
                switch (maze.grid[row][c]) {
                    '|', 'J', 'L' => cuts += 1,
                    else => {},
                }
            }
            if (cuts % 2 == 1) {
                enclosed += 1;
                // std.debug.print("{c}", .{'%'});
            } else {
                // std.debug.print("{c}", .{maze.grid[row][col]});
            }
        }
        // std.debug.print("{c}", .{'\n'});
    }
    return enclosed;

Replacement in src/day10.zig at line 93 [2.123]

B:BD[2.1341] → [2.1341:1424]

    try std.testing.expectEqual(@as(usize, 1), try second(std.testing.allocator));

[2.1341]

[2.1424]

    try std.testing.expectEqual(@as(usize, 471), try second(std.testing.allocator));

Replacement in src/day10.zig at line 96 [2.123]
B:BD[2.1427] → [2.1427:1469]
```
fn parseInput(input: []const u8) !Pipes {
```
[2.1427]
[2.1469]
```
fn parseInput(input: []const u8) !Maze {
```
Replacement in src/day10.zig at line 99 [2.123]
B:BD[2.1524] → [2.1524:1558]
```
    var pipes: Pipes = undefined;
```
[2.1524]
[2.1558]
```
    var maze: Maze = undefined;
```

Replacement in src/day10.zig at line 106 [2.123]

B:BD[2.1701] → [2.1701:1845]

            pipes.grid[row][col] = ch;
            if (ch == 'S') {
                pipes.start[0] = row;
                pipes.start[1] = col;

[2.1701]

[2.1845]

            maze.grid[row][col] = ch;
            switch (ch) {
                'S' => {
                    maze.start[0] = row;
                    maze.start[1] = col;
                },
                else => {},

Replacement in src/day10.zig at line 117 [2.123]
B:BD[2.1876] → [2.1876:1894]
```
    return pipes;
```
[2.1876]
[2.1894]
```
    return maze;
```

Replacement in src/day10.zig at line 120 [2.123]

B:BD[2.1897] → [2.1897:1962]

const QueueType = struct {
    state: [2]usize,
    cost: usize,

[2.1897]

[2.1962]

/// Determines the true shape of the 'S' pipe
fn detectStart(maze: Maze) !u8 {
    const Pipes = enum {
        north_south,
        east_west,
        north_east,
        north_west,
        south_east,
        south_west,
        fn char(self: @This()) u8 {
            return switch (self) {
                .north_south => '|',
                .east_west => '-',
                .north_east => 'J',
                .north_west => 'L',
                .south_east => '7',
                .south_west => 'F',
            };
        }
    };
    var options = std.EnumSet(Pipes).initFull();
    const start_directions = enum { north, south, west, east };
    for (std.enums.values(start_directions)) |dir| {
        const d: [2]i2 = switch (dir) {
            .north => .{ -1, 0 },
            .south => .{ 1, 0 },
            .west => .{ 0, -1 },
            .east => .{ 0, 1 },
        };
        const diffrow = @as(isize, @intCast(maze.start[0])) + d[0];
        if (diffrow < 0 or diffrow >= GRID_ROWS) continue;
        const dr = @as(usize, @intCast(diffrow));
        const diffcol = @as(isize, @intCast(maze.start[1])) + d[1];
        if (diffcol < 0 or diffcol >= GRID_COLS) continue;
        const dc = @as(usize, @intCast(diffcol));
        const next = maze.grid[dr][dc];

Replacement in src/day10.zig at line 162 [2.123]

B:BD[2.1963] → [2.1963:2151]

    fn lessThan(context: void, a: @This(), b: @This()) std.math.Order {
        _ = context;
        if (a.cost < b.cost) return .lt else if (a.cost == b.cost) return .eq else return .gt;

[2.1963]

[2.2151]

        switch (dir) {
            .north => {
                switch (next) {
                    '|', '7', 'F' => {
                        options.remove(.east_west);
                        options.remove(.south_east);
                        options.remove(.south_west);
                    },
                    else => {},
                }
            },
            .south => {
                switch (next) {
                    '|', 'L', 'J' => {
                        options.remove(.east_west);
                        options.remove(.north_east);
                        options.remove(.north_west);
                    },
                    else => {},
                }
            },
            .east => {
                switch (next) {
                    '-', 'L', 'F' => {
                        options.remove(.north_south);
                        options.remove(.south_west);
                        options.remove(.north_west);
                    },
                    else => {},
                }
            },
            .west => {
                switch (next) {
                    '-', '7', 'J' => {
                        options.remove(.north_south);
                        options.remove(.south_east);
                        options.remove(.north_east);
                    },
                    else => {},
                }
            },
        }

Replacement in src/day10.zig at line 205 [2.123]

B:BD[2.2157] → [2.2157:2160]

};

[2.2157]

[2.2160]


    std.debug.assert(options.count() == 1);
    var it = options.iterator();
    return it.next().?.char();
}

Replacement in src/day10.zig at line 214 [2.123]

B:BD[2.2208] → [2.2208:2275]

    pipes: *Pipes,
    cost_grid: *[GRID_ROWS][GRID_COLS]CostType,

[2.2208]

[2.2275]

    maze: *Maze,
    cost_grid: *[COST_ROWS][COST_COLS]CostType,

Insertion in src/day10.zig at line 217 [2.123]

[2.2285]

    const QueueType = struct {
        state: [2]usize,
        cost: usize,
        fn lessThan(context: void, a: @This(), b: @This()) std.math.Order {
            _ = context;
            if (a.cost < b.cost) return .lt else if (a.cost == b.cost) return .eq else return .gt;
        }
    };

Replacement in src/day10.zig at line 230 [2.123]

B:BD[2.2413] → [2.2413:2794]

    { // Handle start position and its neighbors
        const start_directions = enum { north, south, west, east };
        for (std.enums.values(start_directions)) |dir| {
            const d: [2]i2 = switch (dir) {
                .north => .{ -1, 0 },
                .south => .{ 1, 0 },
                .west => .{ 0, -1 },
                .east => .{ 0, 1 },
            };

[2.2413]

[2.2794]

    // Add start item
    try queue.add(.{ .state = .{ maze.start[0], maze.start[1] }, .cost = 0 });

Replacement in src/day10.zig at line 233 [2.123]

B:BD[2.2795] → [2.2795:2985]

            const diffrow = @as(isize, @intCast(pipes.start[0])) + d[0];
            if (diffrow < 0 or diffrow >= GRID_ROWS) continue;
            const dr = @as(usize, @intCast(diffrow));

[2.2795]

[2.2985]

    while (queue.removeOrNull()) |curr| {
        // mark this grid item visited
        maze.visited[curr.state[0]][curr.state[1]] = true;

Deletion in src/day10.zig at line 237 [2.123]

B:BD[2.2986] → [2.2986:4454]

            const diffcol = @as(isize, @intCast(pipes.start[1])) + d[1];
            if (diffcol < 0 or diffcol >= GRID_COLS) continue;
            const dc = @as(usize, @intCast(diffcol));
            switch (dir) {
                .north => {
                    switch (pipes.grid[dr][dc]) {
                        '|', '7', 'F' => {},
                        '.', '-', 'L', 'J' => continue,
                        else => unreachable,
                    }
                },
                .south => {
                    switch (pipes.grid[dr][dc]) {
                        '|', 'L', 'J' => {},
                        '.', '-', '7', 'F' => continue,
                        else => unreachable,
                    }
                },
                .west => {
                    switch (pipes.grid[dr][dc]) {
                        '-', 'L', 'F' => {},
                        '.', '|', 'J', '7' => continue,
                        else => unreachable,
                    }
                },
                .east => {
                    switch (pipes.grid[dr][dc]) {
                        '-', 'J', '7' => {},
                        '.', '|', 'L', 'F' => continue,
                        else => unreachable,
                    }
                },
            }
            cost_grid[dr][dc] = 1;
            try queue.add(.{ .state = .{ dr, dc }, .cost = 1 });
        }
    }
    // Dijkstra...
    while (queue.removeOrNull()) |curr| {

Replacement in src/day10.zig at line 238 [2.123]

B:BD[2.4518] → [2.4518:4590]

        const dir = switch (pipes.grid[curr.state[0]][curr.state[1]]) {

[2.4518]

[2.4590]

        const dir = switch (maze.grid[curr.state[0]][curr.state[1]]) {

Insertion in src/day10.zig at line 283 [2.123]

[2.5819]


const test_input3 =
    \\.F----7F7F7F7F-7....
    \\.|F--7||||||||FJ....
    \\.||.FJ||||||||L7....
    \\FJL7L7LJLJ||LJ.L-7..
    \\L--J.L7...LJS7F-7L7.
    \\....F-J..F7FJ|L7L7L7
    \\....L7.F7||L7|.L7L7|
    \\.....|FJLJ|FJ|F7|.LJ
    \\....FJL-7.||.||||...
    \\....L---J.LJ.LJLJ...
;
const test_input4 =
    \\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
;