From cd5600dfec9d59a8054cab53ff31c25be789ce9c Mon Sep 17 00:00:00 2001 From: Orfeas <38209077+0xfea5@users.noreply.github.com> Date: Mon, 11 Dec 2023 22:16:01 +0200 Subject: day10 --- day10/example1.txt | 5 ++ day10/example2.txt | 9 ++++ day10/example3.txt | 10 ++++ day10/example4.txt | 10 ++++ day10/solution.zig | 133 +++++++++++++++++++++++++++++++++++++++++++++++++++++ day11/solution.zig | 23 +++++++++ 6 files changed, 190 insertions(+) create mode 100644 day10/example1.txt create mode 100644 day10/example2.txt create mode 100644 day10/example3.txt create mode 100644 day10/example4.txt create mode 100644 day10/solution.zig create mode 100644 day11/solution.zig diff --git a/day10/example1.txt b/day10/example1.txt new file mode 100644 index 0000000..682499d --- /dev/null +++ b/day10/example1.txt @@ -0,0 +1,5 @@ +..F7. +.FJ|. +SJ.L7 +|F--J +LJ... diff --git a/day10/example2.txt b/day10/example2.txt new file mode 100644 index 0000000..bd9cdf5 --- /dev/null +++ b/day10/example2.txt @@ -0,0 +1,9 @@ +........... +.S-------7. +.|F-----7|. +.||.....||. +.||.....||. +.|L-7.F-J|. +.|..|.|..|. +.L--J.L--J. +........... diff --git a/day10/example3.txt b/day10/example3.txt new file mode 100644 index 0000000..adaae96 --- /dev/null +++ b/day10/example3.txt @@ -0,0 +1,10 @@ +.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... diff --git a/day10/example4.txt b/day10/example4.txt new file mode 100644 index 0000000..8f950ae --- /dev/null +++ b/day10/example4.txt @@ -0,0 +1,10 @@ +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 diff --git a/day10/solution.zig b/day10/solution.zig new file mode 100644 index 0000000..8028c94 --- /dev/null +++ b/day10/solution.zig @@ -0,0 +1,133 @@ +const std = @import("std"); +const print = std.debug.print; +const assert = std.debug.assert; +const ArrayList = std.ArrayList; +const HashMap = std.HashMap; +const mem = std.mem; + +const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace); +var gpa = std.heap.GeneralPurposeAllocator(.{}){}; +const allocator = gpa.allocator(); + +const Pair = struct { + row: isize, + col: isize, + + pub fn eql(lhs: @This(), rhs: @This()) bool { + return lhs.col == rhs.col and lhs.row == rhs.row; + } +}; + +const Direction = enum(u4) { + N = 0, + U = 1 << 0, + R = 1 << 1, + D = 1 << 2, + L = 1 << 3, +}; + +const c2dir = blk: { + var res: [256]u4 = undefined; + res['S'] = + @intFromEnum(Direction.U) | @intFromEnum(Direction.R) | + @intFromEnum(Direction.D) | @intFromEnum(Direction.L); + res['|'] = @intFromEnum(Direction.U) | @intFromEnum(Direction.D); + res['J'] = @intFromEnum(Direction.U) | @intFromEnum(Direction.L); + res['L'] = @intFromEnum(Direction.U) | @intFromEnum(Direction.R); + res['7'] = @intFromEnum(Direction.D) | @intFromEnum(Direction.L); + res['F'] = @intFromEnum(Direction.D) | @intFromEnum(Direction.R); + res['-'] = @intFromEnum(Direction.L) | @intFromEnum(Direction.R); + res['.'] = @intFromEnum(Direction.N); + break :blk res; +}; + +const dir2off = blk: { + var res: [256][2]i64 = undefined; + res[@intFromEnum(Direction.U)] = .{ -1, 0 }; + res[@intFromEnum(Direction.R)] = .{ 0, 1 }; + res[@intFromEnum(Direction.D)] = .{ 1, 0 }; + res[@intFromEnum(Direction.L)] = .{ 0, -1 }; + break :blk res; +}; + +pub fn solve(grid: []const []const u8) !void { + const height = grid.len; + const width = grid[0].len; + const start = find_start: { + for (grid, 0..) |row, i| { + if (mem.indexOfScalar(u8, row, 'S')) |j| { + break :find_start Pair{ + .row = @bitCast(i), + .col = @bitCast(j), + }; + } + } + unreachable; + }; + + var pathNodes = ArrayList(Pair).init(allocator); + defer pathNodes.deinit(); + try pathNodes.append(start); + var blocked: u4 = 0b0000; + + outer: while (true) { + const curr = pathNodes.getLast(); + const cdirs = c2dir[grid[@bitCast(curr.row)][@bitCast(curr.col)]]; + + for (0..4) |i| { + const d: u4 = @shlExact(@as(u4, 1), @intCast(i)); + const nrow: i64 = curr.row + dir2off[d][0]; + const ncol: i64 = curr.col + dir2off[d][1]; + + if (nrow < 0 or nrow >= height or ncol < 0 or ncol >= width) { + continue; + } + + const next = Pair{ + .row = nrow, + .col = ncol, + }; + const ndirs = std.math.rotl(u4, c2dir[grid[@bitCast(next.row)][@bitCast(next.col)]], @as(u2, 2)); + + if (d & cdirs & ndirs & ~blocked != 0) { + // Wrapped back to the beginning + if (next.eql(start)) { + break :outer; + } + blocked = std.math.rotl(u4, d, @as(u2, 2)); + try pathNodes.append(next); + break; + } + } else { + unreachable; + } + } + + const pathLen = pathNodes.items.len; + const part1 = pathLen / 2; + print("{d}\n", .{part1}); + + // Use shoelace formula to calculate the area of the polygon + // https://en.wikipedia.org/wiki/Shoelace_formula#Shoelace_formula + var a2: isize = 0; + for (pathNodes.items, 1..) |f, j| { + const s = pathNodes.items[j % pathLen]; + a2 += f.row * s.col - f.col * s.row; + } + const a: isize = @divTrunc(if (a2 > 0) a2 else -a2, 2); + // Use Pick's formula to find the number of internal points + // https://en.wikipedia.org/wiki/Pick's_theorem#Formula + const part2 = a - @as(isize, @bitCast(part1)) + 1; + + print("{d}\n", .{part2}); +} + +pub fn main() !void { + var splitLines = mem.splitScalar(u8, fin, '\n'); + var grid = ArrayList([]const u8).init(allocator); + + while (splitLines.next()) |line| { + try grid.append(line); + } + try solve(grid.items); +} diff --git a/day11/solution.zig b/day11/solution.zig new file mode 100644 index 0000000..059a120 --- /dev/null +++ b/day11/solution.zig @@ -0,0 +1,23 @@ +const std = @import("std"); +const print = std.debug.print; +const assert = std.debug.assert; +const ArrayList = std.ArrayList; +const HashMap = std.HashMap; +const mem = std.mem; + +const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace); +var gpa = std.heap.GeneralPurposeAllocator(.{}){}; +const allocator = gpa.allocator(); + +pub fn part1() void { + // Part 1 goes here +} + +pub fn part2() void { + // Part 2 goes here +} + +pub fn main() !void { + part1(); + part2(); +} -- cgit v1.2.3