Skip to content

Instantly share code, notes, and snippets.

@Porges

Porges/cards.ts

Created February 2, 2021 19:48
Download ZIP

Revisions

  1. Porges created this gist Feb 2, 2021.
    93 changes: 93 additions & 0 deletions cards.ts
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,93 @@
    type Card = number;

    function matches(card: Card, cs: readonly Card[]): boolean {
    function attempt(cs: readonly Card[], partialSum: number, unused: readonly Card[]): boolean {
    let noGood = [...unused];
    let toTry: Card[] = [...cs];

    for (let next = toTry.pop(); next !== undefined; next = toTry.pop()) {
    if (next === card) {
    continue; // cards that are equal are always okay
    } else if (next > card) {
    return false; // there is an unmatchable card, fail the whole thing
    } else {
    let sum = partialSum + next;
    if (sum === card) {
    // could be part of a valid solution, we have a capturing set
    // that equals the card
    // put all the no-good cards back into the set to try
    if (go([...toTry, ...noGood], 0, [])) {
    return true;
    }
    } else if (sum < card) {
    // could be part of a valid solution, we have a capturing set
    // that does not yet equal the card
    // keep matching with the current sum & no-good set
    if (go(toTry, sum, noGood)) {
    return true;
    }
    }

    // otherwise put it into the no-good set
    // we will try again later
    noGood.push(next);
    }
    }

    // run out of cards to try, we have suceeded if
    // there's nothing left to check
    return noGood.length === 0 && partialSum === 0;
    }

    const cache = new Map<string, boolean>();
    function go(cs: readonly Card[], partialSum: number, unused: readonly Card[]): boolean {
    const key = `${[...cs].sort().join()}|${partialSum}|${[...unused].sort().join()}`;
    const cached = cache.get(key);
    if (cached !== undefined) {
    return cached;
    }

    const result = attempt(cs, partialSum, unused);
    cache.set(key, result);
    return result;
    };

    return go(cs, 0, []);
    }

    const examples = [
    [10, [10, 10]],
    [10, [10, 5, 5]],
    [10, [10, 2, 8]],
    [10, [2, 8, 6, 2]],
    [5, [10]],
    [5, [2, 2, 2, 2, 2]],
    [5, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]],
    [5, [5, 5, 5, 5, 5, 5]],
    [10, [9, 9, 1, 1]],
    [10, [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
    [10, [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
    [10, [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
    [10, [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
    [10, [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
    [10, [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
    1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
    [10, [8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9,
    2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1]],
    [10, [8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9,
    2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]],
    [10, [8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9,
    2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]],
    ] as const;

    for (const [card, cards] of examples) {
    console.log(`${card} matches ${cards}: ${matches(card, cards)}`);
    }