day14

3 files changed, 207 insertions, 16 deletions

diff --git a/day13/solution.zig b/day13/solution.zig
index e3139fc..3b83d0e 100644
--- a/day13/solution.zig
+++ b/day13/solution.zig
@@ -23,6 +23,22 @@ fn cnt_diff(lhs: []const u8, rhs: []const u8) i64 {
     return cnt;
 }
 
+fn transpose(map: Map) Map {
+    var transposed = allocator.alloc([]u8, map[0].len) catch unreachable;
+
+    for (transposed) |*trow| {
+        trow.* = allocator.alloc(u8, map.len) catch unreachable;
+    }
+
+    for (map, 0..) |row, i| {
+        for (row, 0..) |c, j| {
+            transposed[j][i] = c;
+        }
+    }
+
+    return transposed;
+}
+
 fn check_eql(map: Map, i_: usize, j_: usize, tolerance_: i64) bool {
     var i = i_;
     var j = j_;
@@ -41,22 +57,6 @@ fn check_eql(map: Map, i_: usize, j_: usize, tolerance_: i64) bool {
     return tolerance == 0;
 }
 
-fn transpose(map: Map) Map {
-    var transposed = allocator.alloc([]u8, map[0].len) catch unreachable;
-
-    for (transposed) |*trow| {
-        trow.* = allocator.alloc(u8, map.len) catch unreachable;
-    }
-
-    for (map, 0..) |row, i| {
-        for (row, 0..) |c, j| {
-            transposed[j][i] = c;
-        }
-    }
-
-    return transposed;
-}
-
 fn evaluate(map: Map, tolerance: i64) u64 {
     const h = map.len;
     const w = map[0].len;
diff --git a/day14/example.txt b/day14/example.txt
new file mode 100644
index 0000000..5a24dce
--- /dev/null
+++ b/day14/example.txt
@@ -0,0 +1,10 @@
+O....#....
+O.OO#....#
+.....##...
+OO.#O....O
+.O.....O#.
+O.#..O.#.#
+..O..#O..O
+.......O..
+#....###..
+#OO..#....
diff --git a/day14/solution.zig b/day14/solution.zig
new file mode 100644
index 0000000..5509bdc
--- /dev/null
+++ b/day14/solution.zig
@@ -0,0 +1,181 @@
+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 Map = []const []u8;
+
+fn column_wise(map: Map, begin: isize, end: isize, step: isize) u64 {
+    const h = map.len;
+    const w = map[0].len;
+    var ans: u64 = 0;
+
+    for (0..w) |j| {
+        var next_free = begin;
+        var i = begin;
+        while (i != end) : (i += step) {
+            switch (map[@bitCast(i)][j]) {
+                '.' => {},
+                'O' => {
+                    ans += h - @as(u64, @bitCast(next_free));
+                    map[@bitCast(i)][j] = '.';
+                    map[@bitCast(next_free)][j] = 'O';
+                    next_free += step;
+                },
+                '#' => {
+                    next_free = i + step;
+                },
+                else => unreachable,
+            }
+        }
+    }
+
+    return ans;
+}
+
+fn row_wise(map: Map, begin: isize, end: isize, step: isize) u64 {
+    const h = map.len;
+    var ans: u64 = 0;
+
+    for (0..h) |i| {
+        var next_free = begin;
+        var j = begin;
+        while (j != end) : (j += step) {
+            switch (map[i][@bitCast(j)]) {
+                '.' => {},
+                'O' => {
+                    ans += h - i;
+                    map[i][@bitCast(j)] = '.';
+                    map[i][@bitCast(next_free)] = 'O';
+                    next_free += step;
+                },
+                '#' => {
+                    next_free = j + step;
+                },
+                else => unreachable,
+            }
+        }
+    }
+
+    return ans;
+}
+
+fn north(map: Map) u64 {
+    const h = map.len;
+    return column_wise(map, 0, @bitCast(h), 1);
+}
+
+fn west(map: Map) u64 {
+    const w = map[0].len;
+    return row_wise(map, 0, @bitCast(w), 1);
+}
+
+fn south(map: Map) u64 {
+    const h = map.len;
+    return column_wise(map, @bitCast(h - 1), -1, -1);
+}
+
+fn east(map: Map) u64 {
+    const w = map[0].len;
+    return row_wise(map, @bitCast(w - 1), -1, -1);
+}
+
+fn round(map: Map) u64 {
+    _ = north(map);
+    _ = west(map);
+    _ = south(map);
+    return east(map);
+}
+
+const MapCtx = struct {
+    pub fn hash(_: @This(), map: []const []u8) u64 {
+        var h: u64 = 0;
+
+        for (map, 0..) |row, i| {
+            for (row, 0..) |c, j| {
+                if (c == 'O') {
+                    h ^= @shlExact(i, 16) | (j);
+                }
+            }
+        }
+        h *= 1231231557;
+        h ^= (h >> 32);
+        return h;
+    }
+
+    pub fn eql(_: @This(), lhs: []const []u8, rhs: []const []u8) bool {
+        for (lhs, rhs) |l, r| {
+            if (!mem.eql(u8, l, r)) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+};
+
+fn mapdup(map: []const []const u8) Map {
+    const h = map.len;
+    const w = map[0].len;
+    const new = allocator.alloc([]u8, h) catch unreachable;
+
+    for (new, map) |*row, srcrow| {
+        row.* = allocator.alloc(u8, w) catch unreachable;
+        @memcpy(row.*, srcrow);
+    }
+
+    return new;
+}
+
+fn part1(map: []const []const u8) void {
+    const ans = north(mapdup(map));
+
+    print("{d}\n", .{ans});
+}
+
+fn part2(map_: []const []const u8) void {
+    var ans: u64 = 0;
+    var visited = HashMap(Map, u64, MapCtx, 80).init(allocator);
+    const map = mapdup(map_);
+    const reps = 1_000_000_000;
+    var upto: u64 = 0;
+
+    for (0..reps) |p| {
+        ans = round(map);
+        if (visited.get(map)) |s| {
+            const start = s;
+            const period = p - s;
+            upto = (reps - start - 1) % period;
+            break;
+        }
+        visited.put(mapdup(map), p) catch unreachable;
+    }
+
+    for (0..upto) |_| {
+        ans = round(map);
+    }
+
+    print("{d}\n", .{ans});
+}
+
+pub fn solve(map: []const []const u8) void {
+    part1(map);
+    part2(map);
+}
+
+pub fn main() !void {
+    var splitLines = mem.splitScalar(u8, fin, '\n');
+    var map = ArrayList([]const u8).init(allocator);
+
+    while (splitLines.next()) |line| {
+        try map.append(line);
+    }
+
+    solve(map.items);
+}