# Calculate odds that cards drawn from deck sum to at least some number ("Across the Obelisk" problem)

Here is a problem inspired by the game Across the Obelisk.

4 players have decks of cards. Each card has an integer value between 0-9 on it. The decks can be any size, and there's no other restriction on the card values - each possible card-value can be represented any number of times, including 0.

The game chooses an integer $$X$$, then each player shuffles their deck and draws one card. What are the chances the sum of those cards is $$\geq X$$?

Digging into the game's code, the developers solve this problem by generating every possible combination of cards and putting their sums into an array, then counting how many instances are $$\geq X$$. With deck size $$D$$, this is $$O(D^4)$$. This is only feasible because there's a low number of players and the deck sizes are small. Is there a solution that scales better?

Here's a solution I came up with that's $$O(PD + PV\log{P})$$, where

• $$D$$ = The size of the largest deck
• $$P$$ = The number of players (4 in the original problem)
• $$V$$ = The max card-value (9 in the original problem)

The main ideas of this algorithm are:

• We can treat any deck, no matter how large, as a discrete probability distribution containing only the $$V+1$$ values $$0$$ thru $$V$$, each with its own probability of being chosen.
• Because each deck is independent, we can treat the two cards coming from any two decks as though it were a single card coming from a single larger probability distribution, whose value lies in the range $$0$$ thru $$2V$$
• Any card-value $$\geq X$$ (the integer we want our sum to beat) can be replaced by $$X$$ without changing the result

Combining these ideas, we get the following algorithm:

1. For each deck, create a probability table mapping each card-value to its probability of being drawn

2. Combine two tables $$A,B$$ into a new table $$AB$$, using the rule $$AB(N) = A(0)B(N) + A(1)B(N-1) + ... + A(N-1)B(1) + A(N)B(0)$$

In other words, the probability of their sum being exactly $$N$$ is the $$Prob(Card_1 = 0, Card_2 = N) + Prob(Card_1 = 1, Card_2 = N-1) + ...$$

2a. (Optional): Combine all the entries $$\geq X$$ into a single entry by summing their values

3. Keep combining tables like this until there is only one left, always combining the two smallest tables. The sum of all values $$\geq X$$ then gives the answer.

Asymptotic analysis:

Step 1 takes time $$PD$$ to calculate, plus $$PV$$ to initialize the arrays, for an overall $$O(PD + PV)$$

Step 2 does one multiplication for each combination of cards, for a total of $$|A||B|$$.

Step 3 has step 2 repeating a total of P-1 times. The first P/2 times, the tables will each have size V. The next P/4 times, the tables will have size 2V. The next P/8 times, the tables will have size 4V, etc. So the total number of multiplications is $$(P/2)(V+V) + (P/4)(2V+2V) + (P/8)(4V+4V) + ...$$$$= PV + PV + PV + ...(\log_2{P}\text{ times})$$

for an overall $$O(PV\log{P})$$