Maximize score in 15-sum card game

## Problem A deck has **36 cards**: 4 suits × ranks 1 through 9 (so there are exactly four `1`s, four `2`s, …, four `9`s). 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).