Strategy/algorithm to divide pot to chips

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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]

Answer 5

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

Answer 6

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
      result.Add(highest, quantity);

      //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);

Console.WriteLine("Each player receives:");

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

Console.WriteLine("Leave in pot:");

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

Answer 7

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..

Answer 8

The basic algorithm is take the largest denomination, divide the pot by it, throw away the remainder, and that's your chip count for that denom. The subtract the chip count * denom from the pot. Then repeat with the next-highest denom, until finished.

As for the Result[7,5] thing, it could be easily implemented in Javascript as follows:

var denoms = [1, 5, 10, 25, 100, 500, 1000, 5000, 10000];

var getResult = function(indices, pot) {
    var total = pot;
    for (var i = 0; i < indices.length; i++) {
        var index = indices[i];
        var denom = denoms[index];
        var chipCount = Math.floor(total / denom);
        total -= chipCount * denom;
        console.log(chipCount + "x $" + denom + " chips");
    }
};

// test run
getResult([7,5], 17500);
// output
// 3x $5000 chips
// 5x $500 chips

I chose Javascript because you can just open the developer console on whatever browser you are running to read this and copy and paste the code in to test it. :)

Minimum chips is similar, because you just loop through each denomination, starting with the largest and do the same thing:

var getMinChips = function(pot) {
    var total = pot;
    // denoms assumed sorted in ascending order
    for (var i = denoms.length - 1; i >= 0; i--) { // loop backwards through array
        var denom = denoms[i];
        var chipCount = Math.floor(total / denom);
        if (chipCount > 0) {
            total -= chipCount * denom;
            console.log(chipCount + "x $" + denom + " chips");
        }
    }
};

// test
getMinChips(17500);
// output
// 1x $10000 chips
// 1x $5000 chips
// 2x $1000 chips
// 1x $500 chips

If you wanted to do something even more useful, you could also incorporate pot splits (where more than one player had the highest hand) by taking the denom and multiplying it by the number of players before dividing the pot by it. If you have a left-over chip after the lowest denomination, it's typically "thrown away" (by being left in the pot for the next hand).