day17

3 files changed, 126 insertions, 0 deletions

diff --git a/day17/example1.txt b/day17/example1.txt
new file mode 100644
index 0000000..f400d6e
--- /dev/null
+++ b/day17/example1.txt
@@ -0,0 +1,13 @@
+2413432311323
+3215453535623
+3255245654254
+3446585845452
+4546657867536
+1438598798454
+4457876987766
+3637877979653
+4654967986887
+4564679986453
+1224686865563
+2546548887735
+4322674655533
diff --git a/day17/example2.txt b/day17/example2.txt
new file mode 100644
index 0000000..e456899
--- /dev/null
+++ b/day17/example2.txt
@@ -0,0 +1,5 @@
+111111111111
+999999999991
+999999999991
+999999999991
+999999999991
diff --git a/day17/solution.zig b/day17/solution.zig
new file mode 100644
index 0000000..00591ff
--- /dev/null
+++ b/day17/solution.zig
@@ -0,0 +1,108 @@
+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 math = std.math;
+
+const fin = mem.trim(u8, @embedFile("./input.txt"), &std.ascii.whitespace);
+var gpa = std.heap.GeneralPurposeAllocator(.{}){};
+const allocator = gpa.allocator();
+
+const move = [_][2]i64{
+    [_]i64{ -1, 0 },
+    [_]i64{ 0, 1 },
+    [_]i64{ 1, 0 },
+    [_]i64{ 0, -1 },
+};
+
+const Point = struct {
+    i: usize,
+    j: usize,
+    best: [4]u64,
+
+    pub fn Cmp(_: void, lhs: Point, rhs: Point) math.Order {
+        return std.math.order(mem.min(u64, &lhs.best), mem.min(u64, &rhs.best));
+    }
+};
+
+const inf: u64 = math.maxInt(u32);
+const MAXSIZE = 200;
+
+fn evaluate(grid: []const []const u8, comptime min_dist: u64, comptime max_dist: u64) !u64 {
+    var dp = [_][MAXSIZE][4]u64{[_][4]u64{[_]u64{inf} ** 4} ** MAXSIZE} ** MAXSIZE;
+    const w = grid[0].len;
+    const h = grid.len;
+    var pq = std.PriorityQueue(Point, void, Point.Cmp).init(allocator, {});
+
+    dp[0][0] = [_]u64{0} ** 4;
+
+    try pq.add(Point{
+        .i = 0,
+        .j = 0,
+        .best = dp[0][0],
+    });
+
+    while (pq.removeOrNull()) |curr| {
+        for (move, 0..) |m, dirTo| {
+            const dirFrom = dirTo ^ 0b10;
+            const dpbest = res: {
+                var best: u64 = inf;
+
+                for (0..4) |dir| {
+                    if (dir != dirFrom and dir != dirTo) {
+                        best = @min(best, dp[curr.i][curr.j][dir]);
+                    }
+                }
+
+                break :res best;
+            };
+
+            var s: u64 = 0;
+            for (1..max_dist + 1) |dist| {
+                const ni: u64 = @bitCast(@as(i64, @bitCast(curr.i)) + m[0] * @as(i64, @bitCast(dist)));
+                const nj: u64 = @bitCast(@as(i64, @bitCast(curr.j)) + m[1] * @as(i64, @bitCast(dist)));
+
+                if (ni >= h or nj >= w) {
+                    break;
+                }
+
+                s += grid[ni][nj] - '0';
+
+                if (dist < min_dist) {
+                    continue;
+                }
+
+                if (dp[ni][nj][dirFrom] > dpbest + s) {
+                    dp[ni][nj][dirFrom] = dpbest + s;
+                    try pq.add(Point{
+                        .i = ni,
+                        .j = nj,
+                        .best = dp[ni][nj],
+                    });
+                }
+            }
+        }
+    }
+    return mem.min(u64, &dp[h - 1][w - 1]);
+}
+
+pub fn solve(grid: []const []const u8) !void {
+    const part1 = try evaluate(grid, 1, 3);
+    print("{d}\n", .{part1});
+
+    const part2 = try evaluate(grid, 4, 10);
+    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);
+}