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);
}