solver.ts

type PyramidSlot = string | 0;

export type SolveResult =
    | [won: true, moves: string[]]
    | [won: false, moves: string[]];

class Card {
    private readonly rank: string;
    private readonly suit: string;

    constructor(cardString: string) {
        this.rank = cardString.charAt(0);
        this.suit = cardString.charAt(1);
    }

    get integerValue(): number {
        return "A23456789TJQK".indexOf(this.rank);
    }

    isSequential(card: Card): boolean {
        const difference = Math.abs(this.integerValue - card.integerValue);
        return difference === 1 || difference === 12;
    }

    get toString(): string {
        return this.rank + this.suit;
    }
}

class Pyramid {
    private readonly array: readonly PyramidSlot[];

    constructor(pyramidArray: readonly PyramidSlot[]) {
        this.array = pyramidArray;
    }

    get isCleared(): boolean {
        return this.array.every((card) => card === 0);
    }

    get mask(): number {
        let mask = 0;
        for (let index = 0; index < this.array.length; index++) {
            if (this.array[index] !== 0) {
                mask |= 1 << index;
            }
        }
        return mask;
    }

    get freeCardIndices(): number[] {
        const freeIndices: number[] = [];
        for (let index = this.array.length - 1; index >= 0; index--) {
            if (this.array[index] === 0) {
                continue;
            }

            if (index >= 18) {
                freeIndices.push(index);
            } else if (index >= 9) {
                if (this.array[index + 9] === 0 && this.array[index + 10] === 0) {
                    freeIndices.push(index);
                }
            } else if (index >= 3) {
                const offset = Math.floor((index - 3) / 2);
                if (
                    this.array[index + 6 + offset] === 0
                    && this.array[index + 7 + offset] === 0
                ) {
                    freeIndices.push(index);
                }
            } else if (
                this.array[index * 2 + 3] === 0
                && this.array[index * 2 + 4] === 0
            ) {
                freeIndices.push(index);
            }
        }
        return freeIndices;
    }
}

class MoveString {
    static gameWon(): string {
        return "You have won.";
    }

    static gameLost(): string {
        return "There are no more valid moves.";
    }

    static match(card: string): string {
        return "Move " + card + " onto the stock.";
    }

    static flipStock(): string {
        return "Draw a new stock card.";
    }
}

/**
 * Solves a Tri Peaks solitaire game.
 *
 * @param pyramidArray The 28 pyramid cards, ordered left-to-right and then top-to-bottom.
 * @param stockArray The stock cards, starting with the current face-up card.
 * @param stockIndex The index of the current face-up stock card.
 * @param moveArray The moves made to reach the current configuration.
 */
export function solve(
    pyramidArray: readonly string[],
    stockArray: readonly string[],
    stockIndex = 0,
    moveArray: readonly string[] = [],
): SolveResult {
    if (new Pyramid(pyramidArray).isCleared) {
        return [true, [...moveArray, MoveString.gameWon()]];
    }

    if (stockIndex < 0 || stockIndex >= stockArray.length) {
        return [false, [...moveArray, MoveString.gameLost()]];
    }

    const moves = findSolution(
        pyramidArray,
        stockArray,
        stockIndex + 1,
        new Card(stockArray[stockIndex]),
        new Set<number>(),
        new Map<number, number[]>(),
    );

    return moves === null
        ? [false, [...moveArray, MoveString.gameLost()]]
        : [true, [...moveArray, ...moves, MoveString.gameWon()]];
}

function findSolution(
    pyramidArray: readonly PyramidSlot[],
    stockArray: readonly string[],
    nextStockIndex: number,
    topStock: Card,
    deadStates: Set<number>,
    freeCardsByMask: Map<number, number[]>,
): string[] | null {
    const pyramid = new Pyramid(pyramidArray);
    if (pyramid.isCleared) {
        return [];
    }

    const pyramidMask = pyramid.mask;
    const stateKey = pyramidMask * 512 + nextStockIndex * 16 + topStock.integerValue;
    if (deadStates.has(stateKey)) {
        return null;
    }

    let freeCardIndices = freeCardsByMask.get(pyramidMask);
    if (freeCardIndices === undefined) {
        freeCardIndices = pyramid.freeCardIndices;
        freeCardsByMask.set(pyramidMask, freeCardIndices);
    }

    for (const cardIndex of freeCardIndices) {
        const card = new Card(pyramidArray[cardIndex] as string);
        if (!card.isSequential(topStock)) {
            continue;
        }

        const nextPyramid = [...pyramidArray];
        nextPyramid[cardIndex] = 0;

        const result = findSolution(
            nextPyramid,
            stockArray,
            nextStockIndex,
            card,
            deadStates,
            freeCardsByMask,
        );
        if (result !== null) {
            return [MoveString.match(card.toString), ...result];
        }
    }

    if (nextStockIndex < stockArray.length) {
        const result = findSolution(
            pyramidArray,
            stockArray,
            nextStockIndex + 1,
            new Card(stockArray[nextStockIndex]),
            deadStates,
            freeCardsByMask,
        );
        if (result !== null) {
            return [MoveString.flipStock(), ...result];
        }
    }

    deadStates.add(stateKey);
    return null;
}