# Strategy/algorithm to divide pot to chips

I want to split poker pot to chips.

Example:

Pot = \$17.500.

I have the endless piles of chips. I have the following types of chips: ChipsTypes = [\$1, \$5, \$10, \$25, \$100, \$500, \$1.000, \$5.000, \$10.000, and so on]. Index starts from 0.

I want to get an array that says which chips I have to take to divide the pot and in which order to have minimum number of denominations and chips after pot-to-chips conversion. For example Result = [7, 5] means that I have to take 3 * \$5.000 + 5 * \$500 which \$17.500.

Is there is any strategy or algorithm that would suit my need?

-
"Result = [7, 5] means that I have to take 3 * \$5.000 + 5 * \$500" eh? – vaughandroid Jul 19 '12 at 16:16
Is this homework, it sure seems like it. – CaffGeek Jul 19 '12 at 16:44
It's unclear what you mean by "which chips I have to take to divide the pot" – Jon Lin Jul 19 '12 at 16:46
How are you weighting the number of denominations vs. the number of chips? With your \$17,500 example, we have several valid solutions. 1-10k, 1-5k, 2-1k, 1-500 (5 chips, 4 dens) or 3-5k, 2-1k, 1-500 (6 chips, 3 dens) or 17-1k, 1-500 (18 chips, 2 dens), etc... What's the optimal weighting? The first two solutions have an equal sum of chips and denominations, so are they equivalent in being correct? – GlenH7 Jul 26 '12 at 20:02
@Baqueta - period is used rather than comma in some locales as a thousands/millions/billions delimited. – Telastyn Jul 27 '12 at 18:31

It sounds to me like you are attempting to solve the Knapsack Problem if you want a general solution where any denominations would work.

Put in those terms this is an unbounded knapsack problem where all the values are -1 and the weights are the denomination of the chip.

You should be able to find lots about the problem online.

-
More specifically, it is the change-making/coin-change problem. While it is definitely analogous to the knapsack problem, it can be a little tough wrapping your head around the algorithm while thinking in terms of knapsacks and weight. – jalbee Jul 27 '12 at 22:39

In general, since this seems like a homework question and I don't want to give away the answer, here's the strategy to solving the problem.

• Find the largest denomination at or below the value of the pot and divide the pot by that denomination
• That's how many of that denomination of chip you require
• Take the remainder of the pot, and repeat these steps until the pot is \$0.00

For example

17.5 / 10 = 1 with 7.5 remaining (we need one \$10 chip)
7.5 / 5  = 1 with 2.5 remaining (we need one  \$5 chip)
...etc

...it appears I still pretty much gave away the answer.

-
This is straightforward approach which will definitely work but will result with many different denominations. It is already implemented by me. I am looking for strategy that will give me required/preferred number of denominations. – Worker Jul 20 '12 at 4:10
If you want fewer types of chips, and are using the denominations you list in your question, start with Chad's algorithm and then look for chances to "break" larger chips into smaller ones, i.e. if you've got one \$20 and a \$5 chip, and want them all in the same denomination, split the \$20 into four \$5's. – mjfgates Jul 20 '12 at 7:47
@MinimeDJ, you said you wanted "minimum number of denominations and chips", I gave you the way to get the minimum number of chips. To reduce denominations, you would need to look at any "small" stacks, and break it down to a smaller denomination that you already contain. – CaffGeek Jul 20 '12 at 13:35
@Chad: Your greedy algorithm does not work for all denominations. For example, if we the we only have \$5, \$20 and \$25 chips available then the greedy algorithm would split \$40 into [\$25, \$5, \$5, \$5] instead of the optimal [\$20, \$20]. – hugomg Jul 20 '12 at 17:30
@missingno, no casino would ever have a \$20 and \$25 dollar chip in the same game... – CaffGeek Jul 20 '12 at 17:51

A brute force approach is to modify @Chad's basic algorithm, but then once you have found a solution, start again but with one less chip in the pile of the biggest denomination left. Then rinse and repeat and throw away which ever result is less desirable. The end condition is where you run out of chip denominations, or you know you will always have more chips.

Simply trying to break chips apart doesn't take into account the divisibility of the chips, they could have no common factor (although they do in the example above).

So assuming you have to split \$37 and you have some weird chips sizes:

\$22, \$10, \$7, \$1

Decrement 22's
22*1 + 10*1 + 7*0 + 1*5  = 37 with 7  chips

Decrement 10's
22*0 + 10*3 + 7*1 + 1*0  = 37 with 4  chips
22*0 + 10*2 + 7*2 + 1*3  = 37 with 7  chips
22*0 + 10*1 + 7*3 + 1*6  = 37 with 10 chips

Decrement 7's
22*0 + 10*0 + 7*5 + 1*2  = 37 with 7  chips
22*0 + 10*0 + 7*4 + 1*9  = 37 with 13 chips
22*0 + 10*0 + 7*3 + 1*16 = 37 with 19 chips
22*0 + 10*0 + 7*2 + 1*23 = 37 with 25 chips
22*0 + 10*0 + 7*1 + 1*30 = 37 with 31 chips
22*0 + 10*0 + 7*0 + 1*37 = 37 with 35 chips
-
+1 I like the "incremental" approach to this. Brute force or not, this is most likely will solve the problem. It will also provide all multiple best answers. – Patkos Csaba Jul 26 '12 at 8:13
Just to check, what if I had to split \$37 and had weird chip sizes of: \$22, \$21, \$9, \$7, \$2, \$1 - would this algorithm find the \$21, \$9, \$7 solution? – David_001 Jul 26 '12 at 12:20
@David_001: Probably, because they are in a row, but at first glance it looks like a solution like a,2xc,e in a-e could be missed. – Guvante Jul 26 '12 at 15:04

Hmm.. What about prime factors? An Example:

40\$ = (2 * 2 * 2 * 5)\$
^ * ^ = 10, we have a 10\$ chip, move on

40\$ = (2 * 2 * 10)\$
^ * ^  = 20, we have a 20\$ chip, move on

40\$ = (2 * 20)\$
^ * ^  = 40, nope, no 40\$ chip. Optimal division found.

This doesn't work with primes itself, of course..

-
As a general solution I don't see how this could ever work - what if you had a \$35 chip? – David_001 Jul 26 '12 at 12:10
You are right.. I was overwhelmed by my example :D Herra Huu's approach sounds way better. – Bruno Schäpper Jul 26 '12 at 12:33

In general this problem can be stated as integer programming problem. So the task is

x_i = how many chip type i you have

maximize:

sum(-x_i)

subject to:

sum(chipvalue_i*x_i)=pot

x_i >= 0 and x_i is integer for all i

In general this kind of problems are NP-hard. But if the pot size isn't too big one relatively easy algorithm for the problem is so called branch-and-bound algorithm. For explanation of the algorithm see: http://web.mit.edu/15.053/www/AMP-Chapter-09.pdf, Chapter 9.5, page 289

-

O(n*c) dynamic programming algorithm in pseudocode, where n is the amount of money in dollars (or cents, if there are any chip values with a cent portion), and c is the number of chip sizes. Returns 0 if no chip formulation is found. This only provides the count of the chips. To get the actual chip counts, replace MoneyArray with an array of Lists of chipsizes, and mincount with a List of chipsizes.

fun GetMinChipCount(Array ChipSizes, Int MoneyCount)
MoneyArray = Int[1..MoneyCount]
for i = 1 to MoneyCount:
Int mincount = 0
foreach Chip in ChipSizes:
if Chip < i: continue
if Chip = i: mincount = 1
if Chip > i
Int CountVal = MoneyArray[Chip-i]
if CountVal = 0: continue;
if mincount == 0 or mincount > CountVal + 1: mincount = CountVal + 1
MoneyArray[i] = mincount;
return MoneyArray[MoneyCount]
-
Dynamic programming is definitely the correct approach. It is worth mentioning that, depending on the chip denominations, you may have multiple optimal solutions for a given pot size. If you require a result that returns all of the optimal solutions, you'll have to modify the result array (in this case, MoneyArray) to store a list of solutions (which will be arrays themselves). – jalbee Jul 27 '12 at 22:30

What you describe is less a "pot to chips" algorithm (in real poker, the winner simply rakes in the chips from the center of the table) and more of a "coloring up" algorithm (once a player's ready to leave, he gives his stash to the banker who reduces the chips to the minimum number required), which is basically a "change-making" algorithm using amounts larger than \$1.00.

Here's how I would write it in C#:

//I convert this enum to an array of its values, so you could skip this
public enum ChipDenom : int
{
One = 1,
Five = 5,
Ten = 10,
TwentyFive = 25,
OneHundred = 100,
FiveHundred = 500,
OneThousand = 1000,
FiveThousand = 5000,
TenThousand = 10000
}

public Dictionary<ChipDenom, int> ColorUp(int chipAmount)
{
int remainingAmount = chipAmount;

//you could instead define an int[] containing the dollar values;
var chipValues = Enum.GetValues()
.OfType<ChipDenom>()
.OrderByDescending(cd=>cd)
.ToArray();

//If you do, the return value of this method should be Dictionary<int,int>
var result = new Dictionary<ChipDenom, int>();

while(remainingAmount > 0)
{
//find the largest chip denomination less than the remaining amount
var highest = chipValues.First(cd=>(int)cd < remainingAmount);

//determine how many of that chip can be used
var quantity = remainingAmount / (int)highest;

//and add it to the chip stack

//and repeat with whatever's left over
remainingAmount %= (int)highest;
}

return result;
}

...

//Usage:

var winnings = 13579;

//to determine the chips to give to a single player:
var chips = ColorUp(winnings);

foreach(var kvp in chips)
Console.Writeline(String.Format("{0} : {1}", kvp.Key.ToString(), kvp.Value)

//to determine the chips to give to X players who split the pot:
var splitPlayers = 3;
var winnings = 13579;

var leftOver = winnings % splitPlayers;

var winningsPerPlayer = winnings / splitPlayers;

var playerChips = ColorUp(winningsPerPlayer);
var tableChips = ColorUp(leftOver);