Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
8  
"Result = [7, 5] means that I have to take 3 * $5.000 + 5 * $500" eh? –  Baqueta Jul 19 '12 at 16:16
6  
Is this homework, it sure seems like it. –  CaffGeek Jul 19 '12 at 16:44
1  
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

8 Answers 8

up vote 8 down vote accepted
+50

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.

share|improve this answer
3  
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.

share|improve this 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. –  MinimeDJ 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
1  
@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
4  
@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

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

share|improve this answer

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]
share|improve this answer
    
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

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
share|improve this answer
    
+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

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);
share|improve this answer

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

share|improve this answer
1  
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. –  Vain Fellowman Jul 26 '12 at 12:33

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.