export type State = "." | "#" | "?";
export class Solver {
    private memo = new Map<string, number>();

    constructor(public map: State[], public groups: number[]) { }

    private everyInRange(start: number, end: number, fn: (ch: string) => boolean): boolean {
        for (let i = start; i < end; i++) {
            if (!fn(this.map[i])) {
                return false;
            }
        }
        return true;
    }

    solve(mapStartIndex: number, groupsStartIndex: number): number {
        const memoKey = `${mapStartIndex},${groupsStartIndex}`;
        if (this.memo.has(memoKey)) {
            return this.memo.get(memoKey)!;
        }

        // const map = this.map.slice(mapStartIndex);
        // console.log("solve", mapStartIndex, groupsStartIndex, map.join(""), this.groups.slice(groupsStartIndex).join(","));
        if (this.groups.length <= groupsStartIndex) {
            const result = this.everyInRange(mapStartIndex, this.map.length, ch => ch != "#") ? 1 : 0;
            this.memo.set(memoKey, result);
            return result;
        }
        // advance while '.' is ended.
        let idx = mapStartIndex;
        while (idx < this.map.length && this.map[idx] == '.') {
            idx++;
        }
        if (idx > mapStartIndex) {
            // console.log(`eat '.' ${idx} times`)
            const result = this.solve(idx, groupsStartIndex);
            this.memo.set(memoKey, result);
            return result;
        }

        // so, first element must not be '.'
        const group = this.groups[groupsStartIndex];
        // locate group
        if (this.map.length - mapStartIndex < group) {
            this.memo.set(memoKey, 0);
            return 0;
        }

        let misf = 0;
        if (
            this.everyInRange(mapStartIndex, mapStartIndex + group, ch => ch != ".") &&
            // this.map.slice(mapStartIndex, mapStartIndex + group).every(x => x != '.') &&
            (this.map.length - mapStartIndex <= group || this.map[group + mapStartIndex] != "#")) {
            // console.log(`locate # ${group} at ${this.groups.slice(groupsStartIndex).join(",")}`);
            misf = this.solve(mapStartIndex + group + 1, groupsStartIndex + 1);
        }
        // if map starts with '#', group must be placed.
        if (this.map[mapStartIndex] == "#") {
            this.memo.set(memoKey, misf);
            return misf;
        }
        // or we add ways not to place group at first element.
        const result = misf + this.solve(1 + mapStartIndex, groupsStartIndex);
        this.memo.set(memoKey, result);
        return result;
    }
}