Maximize score in 15-sum card game

Problem

A deck has 36 cards: 4 suits × ranks 1 through 9 (so there are exactly four 1s, four 2s, …, four 9s). Suits do not affect scoring; only ranks matter.

A game proceeds as follows:

1. The deck is shuffled into a fixed order. The first 16 cards are dealt face-up onto the table (the “board”). The remaining cards stay in the draw pile.
2. While possible, you may repeatedly:
   • Choose three cards currently on the board whose ranks sum to 15 .
   • Remove those three cards and gain 15 points .
   • Draw cards from the draw pile to restore the board back to 16 cards (draw exactly 3 if available; otherwise draw as many as remain).
3. The game ends when either:
   • The draw pile is empty and no further 15-sum triple exists on the board, or
   • No 15-sum triple exists on the board (even if cards remain in the pile, you cannot draw unless you remove a triple).

The theoretical maximum score is 180 (12 triples × 15 points) because there are 36 cards.

Task

Given the full shuffled deck order, compute the maximum total score achievable by choosing triples optimally.

Input

• A list deck of length 36. Each element is an integer rank in [1..9] .
• The multiset of ranks in deck satisfies: each rank 1..9 appears exactly 4 times.

Output

• An integer: the maximum score achievable.

Examples (illustrative)

• If the initial 16-card board contains no triple summing to 15, output is 0 .
• If an optimal play can remove 12 triples, output is 180 .

Follow-ups (if time)

1. Implement a baseline greedy strategy (e.g., pick any available 15-sum triple).
2. Write a test that runs the game for 100 random shuffles and reports how often the strategy achieves 180.

Constraints

• Deck size is fixed (36), but the branching factor can be high; design an approach that avoids exponential blow-ups where possible (e.g., memoization).