day12 revamped

thanks anemo

1 files changed, 33 insertions, 131 deletions

diff --git a/day12/solution.zig b/day12/solution.zig
index bb335ba..30b0926 100644
--- a/day12/solution.zig
+++ b/day12/solution.zig
@@ -14,139 +14,45 @@ const Record = struct {
     arrangement: []const u64,
 };
 
-const State = struct {
-    i: u8,
-    j: u8,
-    streak: u8,
-    prev: u8,
-
-    pub fn print(self: @This(), springs: []const u8, arrangement: []const u64) void {
-        std.debug.print("streak = {d}, prev = {c} springs = '{s}' | ", .{ self.streak, self.prev, springs[self.i..] });
-        if (self.j <= arrangement.len) {
-            for (arrangement[self.j..]) |arr| {
-                std.debug.print("{d}, ", .{arr});
-            }
-            std.debug.print("\n", .{});
-        }
-    }
+// Credit: https://github.com/RestrictedPower/Advent-of-Code-2023/blob/main/Day12/main.py
+fn evaluate(springs: []const u8, arrangement: []const u64) u64 {
+    const DPSIZE = 200;
+    var dp = [_][DPSIZE][2]u64{[_][2]u64{[_]u64{0} ** 2} ** DPSIZE} ** DPSIZE;
 
-    pub const ctx = struct {
-        pub fn hash(_: @This(), s: State) u64 {
-            return (@as(u32, s.i) << 24 | @as(u32, s.j) << 16 | @as(u32, s.prev) << 8 | s.streak);
-        }
+    dp[0][0][0] = 1;
 
-        pub fn eql(_: @This(), lhs: State, rhs: State) bool {
-            return lhs.i == rhs.i and
-                lhs.j == rhs.j and
-                lhs.prev == rhs.prev and
-                lhs.streak == rhs.streak;
+    for (springs, 1..) |c, i| {
+        if (c == '.' or c == '?') {
+            for (0..arrangement.len + 1) |j| {
+                dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
+            }
         }
-    };
-};
-
-const DPHashMap = HashMap(State, u64, State.ctx, 80);
 
-fn evaluate(dp: *DPHashMap, springs: []const u8, arrangement: []const u64, state: State) u64 {
-    var ans: u64 = 0;
-    var prev = state.prev;
-    var streak = state.streak;
-    var j = state.j;
-
-    if (dp.get(state)) |val| {
-        return val;
-    }
-
-    defer {
-        dp.put(state, ans) catch unreachable;
-    }
-
-    if (j > arrangement.len or
-        j == arrangement.len and streak > 0 or
-        j < arrangement.len and streak > arrangement[j])
-    {
-        ans = 0;
-        return 0;
-    }
+        for (arrangement, 1..) |n, j| {
+            const begidx: u64 = if (i >= n) i - n else 0;
+            const segment = springs[begidx..i];
+            const possible = mem.indexOfScalar(u8, segment, '.') == null;
 
-    for (springs[state.i..], state.i..) |c, i| {
-        switch (c) {
-            '?' => {
-                // Assume current = '.'
-                const e1 = if (prev == '.')
-                    evaluate(dp, springs, arrangement, State{
-                        .i = @as(u8, @intCast(i)) + 1,
-                        .j = j,
-                        .streak = 0,
-                        .prev = '.',
-                    })
-                else if (j < arrangement.len and streak == arrangement[j])
-                    evaluate(dp, springs, arrangement, State{
-                        .i = @as(u8, @intCast(i)) + 1,
-                        .j = j + 1,
-                        .streak = 0,
-                        .prev = '.',
-                    })
-                else
-                    0;
-
-                // Assume current = '#'
-                const e2 = evaluate(dp, springs, arrangement, State{
-                    .i = @as(u8, @intCast(i)) + 1,
-                    .j = j,
-                    .streak = streak + 1,
-                    .prev = '#',
-                });
-
-                ans = e1 + e2;
-                return ans;
-            },
-            '#' => {
-                streak += 1;
-            },
-            '.' => {
-                if (prev == '#') {
-                    if (j < arrangement.len and streak != arrangement[j] or j >= arrangement.len) {
-                        ans = 0;
-                        return ans;
-                    }
-                    j += 1;
-                }
-                streak = 0;
-            },
-            else => unreachable,
+            if (possible and i >= n) {
+                dp[i][j][1] = dp[begidx][j - 1][0];
+            }
         }
-
-        prev = c;
     }
 
-    ans = if (j >= arrangement.len and streak == 0 or
-        j == arrangement.len - 1 and streak == arrangement[j])
-        1
-    else
-        0;
-
-    return ans;
+    return dp[springs.len][arrangement.len][0] +
+        dp[springs.len][arrangement.len][1];
 }
 
-pub fn solve(records: []const Record) !void {
-    var part1: u64 = 0;
-
+fn part1(records: []const Record) void {
+    var ans: u64 = 0;
     for (records) |record| {
-        const state = State{
-            .i = 0,
-            .j = 0,
-            .streak = 0,
-            .prev = '.',
-        };
-        var dp = DPHashMap.init(allocator);
-        const e = evaluate(&dp, record.springs, record.arrangement, state);
-        part1 += e;
+        ans += evaluate(record.springs, record.arrangement);
     }
+    print("{d}\n", .{ans});
+}
 
-    print("{d}\n", .{part1});
-
-    var part2: u64 = 0;
-
+fn part2(records: []const Record) !void {
+    var ans: u64 = 0;
     for (records) |record| {
         const unfolded_springs = try allocator.alloc(u8, record.springs.len * 5 + 4);
         _ = try std.fmt.bufPrint(unfolded_springs, "{s}?{s}?{s}?{s}?{s}", .{
@@ -161,18 +67,14 @@ pub fn solve(records: []const Record) !void {
         for (0..5) |_| {
             try unfolded_arrangement.appendSlice(record.arrangement);
         }
-
-        const state = State{
-            .i = 0,
-            .j = 0,
-            .streak = 0,
-            .prev = '.',
-        };
-        var dp = DPHashMap.init(allocator);
-        const e = evaluate(&dp, unfolded_springs, unfolded_arrangement.items, state);
-        part2 += e;
+        ans += evaluate(unfolded_springs, unfolded_arrangement.items);
     }
-    print("{d}\n", .{part2});
+    print("{d}\n", .{ans});
+}
+
+pub fn solve(records: []const Record) !void {
+    part1(records);
+    try part2(records);
 }
 
 pub fn main() !void {