day12

2 files changed, 205 insertions, 0 deletions

diff --git a/day12/example.txt b/day12/example.txt
new file mode 100644
index 0000000..e925935
--- /dev/null
+++ b/day12/example.txt
@@ -0,0 +1,6 @@
+???.### 1,1,3
+.??..??...?##. 1,1,3
+?#?#?#?#?#?#?#? 1,3,1,6
+????.#...#... 4,1,1
+????.######..#####. 1,6,5
+?###???????? 3,2,1
diff --git a/day12/solution.zig b/day12/solution.zig
new file mode 100644
index 0000000..bb335ba
--- /dev/null
+++ b/day12/solution.zig
@@ -0,0 +1,199 @@
+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 Record = struct {
+    springs: []const u8,
+    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", .{});
+        }
+    }
+
+    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);
+        }
+
+        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;
+        }
+    };
+};
+
+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 (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,
+        }
+
+        prev = c;
+    }
+
+    ans = if (j >= arrangement.len and streak == 0 or
+        j == arrangement.len - 1 and streak == arrangement[j])
+        1
+    else
+        0;
+
+    return ans;
+}
+
+pub fn solve(records: []const Record) !void {
+    var part1: 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;
+    }
+
+    print("{d}\n", .{part1});
+
+    var part2: 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}", .{
+            record.springs,
+            record.springs,
+            record.springs,
+            record.springs,
+            record.springs,
+        });
+
+        var unfolded_arrangement = ArrayList(u64).init(allocator);
+        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;
+    }
+    print("{d}\n", .{part2});
+}
+
+pub fn main() !void {
+    var splitLines = mem.splitScalar(u8, fin, '\n');
+    var records = ArrayList(Record).init(allocator);
+    defer records.deinit();
+
+    while (splitLines.next()) |line| {
+        var toks = mem.tokenizeAny(u8, line, " ,");
+
+        const springs = toks.next().?;
+        var arrangement = ArrayList(u64).init(allocator);
+
+        while (toks.next()) |tok| {
+            try arrangement.append(try std.fmt.parseInt(u64, tok, 10));
+        }
+
+        try records.append(.{
+            .springs = springs,
+            .arrangement = arrangement.items,
+        });
+    }
+    try solve(records.items);
+}