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

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 6

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 7

Please find the answer with help Binary Tree Algorithm:

using System;

namespace MinimumStack
{
    public class Node
    {
        public static long[] denominations = { 1L, 5L, 10L, 25L, 50, 100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L, 100000L, 500000L, 1000000L, 5000000L, 10000000L, 250000000L, 500000000L, 100000000L, 500000000L, 1000000000L };
        public long Data { get; set; }

        public long Denom { get; set; }
        public long Denom1 { get; set; }
        public long Denom2 { get; set; }


        public int denomChip1 { get; set; }
        public int denomChip2 { get; set; }

        public long ChipCount { get; set; }
        public Node Left { get; set; }
        public Node Right { get; set; }
        public Node()
        {

        }
        public Node(long data,int index,long chipCount1)
        {
            this.Data = data;
            this.ChipCount = chipCount1;


            if(index > 0)
            {
                this.Denom = denominations[index+1];
                this.Denom1 = denominations[index];
                if(data >= denominations[index] && data >0)
                {
                    long chipcount1 = data / denominations[index];

                    long newdata = data - denominations[index] * chipcount1;
                    //if(newdata>0)
                    Left = new Node(newdata, index - 1, chipcount1); 
                } 
            }

            if( index-1 > 0)
            {
                this.Denom2 = denominations[index - 1]; 

                if(data>= denominations[index-1] && data > 0)
                {
                    long chipcount1 = data / denominations[index-1];
                    Console.WriteLine(data+ " data ======== " +denominations[index-1]+" = "+chipcount1);
                    long newdata = data - denominations[index-1] * chipcount1;
                    //if(newdata>0)
                    Right = new Node(newdata, index - 2, chipcount1); 
                } 
            } 

            if(index == 0)
            {

                //this.ChipCount = data;
                this.Denom = denominations[index+1];
                this.Denom1 = denominations[index];
                Left = new Node(0, index - 1, data); 
            }
            if(index-1 == 0)
            {

                //this.ChipCount = data;
                this.Denom2 = denominations[index-1];
                Right = new Node(0, index - 2, data); 
            } 

            //Console.WriteLine("===========================*************=====================================");

//            Console.WriteLine("===============================******************=================================");

        }

       /* 
        private void InsertRec(Node root, Node newNode)
        {
            if (root == null)
                root = newNode;

            if (newNode.Data < root.Data)
            {
                if (root.Left == null)
                    root.Left = newNode;
                else
                    InsertRec(root.Left, newNode);

            }
            else
            {
                if (root.Right == null)
                    root.Right = newNode;
                else
                    InsertRec(root.Right, newNode);
            }
        }
        */
    }
    public class Program
    {
        private Node _root;
        public static void Main(string[] args)
        {//Your code goes here
            Program p = new Program();
            long amount = 14;//15L;
            long[] str1 = { 1L, 5L, 10L, 25L, 50L, 100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L, 100000L, 500000L, 1000000L, 5000000L, 10000000L, 250000000L, 500000000L, 100000000L, 500000000L, 1000000000L };
            //Console.WriteLine("Hello, world!" + p.GetMaxDenomination(44440L));
            for (int j = str1.Length - 1; j >= 0; j--)
            {
                if (amount >= str1[j] && str1[j] > 1)
                {
                    Console.WriteLine((4/1)+"Hello, world! " +j);
                    p._root = new Node(amount, j, 0L);
                    break;
                }
            }
            p.DisplayTree();
            Console.WriteLine("Do something test "+ 44440L/10L);
            Console.WriteLine("================================================================");
           // p.DoSomething();
        }
        private void DisplayTree(Node root,long count)
        {
            if (root == null)
            {
               // Console.WriteLine("ChipCount "+count); 
                return;
            }
            //Console.WriteLine("Denom " +root.Denom +" ChipCount " +(root.ChipCount)); 
            if(root.Data == 0)
                Console.WriteLine("ChipCount "+(count)); 
          //  Console.WriteLine("================================================================");
            if (root.Left != null)
            DisplayTree(root.Left,root.Left.ChipCount+count);

           /* System.Console.WriteLine(root.Data + "Root "+root.Denom1+ " : "+root.Denom2+" chipcount "+root.ChipCount+ "Chip Denomination: "+root.Denom);

            if(root.Left != null)
                System.Console.WriteLine(root.Left.Data + " left " +root.Left.ChipCount);
            if (root.Right != null)
                System.Console.WriteLine(root.Right.Data + " right "+root.Right.ChipCount);
            */
            if (root.Right != null)
            DisplayTree(root.Right,root.Right.ChipCount+count);
         //  Console.WriteLine("================================================================");
        }
        public void DisplayTree()
        {
            DisplayTree(_root,_root.ChipCount);
        }
        public long GetMaxDenomination(long value)
        {
            long[] denominations = {1L,5L,10L,25L,50,100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L,100000L, 500000L, 1000000L, 5000000L, 10000000L,250000000L,500000000L, 100000000L, 500000000L, 1000000000L };
            long maxDenomination = denominations[0];
            for (int i = 1; i < denominations.Length; i++)
            {
                float val = value/denominations[i];
                Console.WriteLine("value "+ val);
                if (val > 0)
                {
                    maxDenomination = denominations[i];
                }
            }
            return maxDenomination;
        }

        public void DoSomething()
        {//{1L,5L,10L,25L,50,100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L,100000L, 500000L, 1000000L, 5000000L, 10000000L,250000000L,500000000L, 100000000L, 500000000L, 1000000000L };
            long[] str1 = {1L,5L,10L,25L,50,100L, 500L, 1000L, 5000L, 10000L, 25000L, 50000L,100000L, 500000L, 1000000L, 5000000L, 10000000L,250000000L,500000000L, 100000000L, 500000000L, 1000000000L };
            for(long i = 44440L;i<=44440L; i++)//1000000000L
            {
                // print("\(i)")
                //if(i%5 == 0)
                {
                    var amount = i;
                    var chipcount = 0L;
                    for( int j = str1.Length-1;j>=0;j--)//.reversed()
                    {// print(j)
                        if(amount/str1[j] > 0 && str1[j]>1)
                        {
                            //Console.WriteLine(str1[j]+" reach "+ amount +" here "+amount/str1[j] );
                            chipcount += amount/str1[j];
                            var k = amount/str1[j];
                            amount = amount - str1[j]*k;
                        }
                        else if(str1[j]==1)
                        {
                            Console.WriteLine(str1[j]+" reach "+ amount +" here "+amount );
                             chipcount+=amount;amount =0;
                        }
                        if(amount == 0)
                            break;
                    }
                    if(chipcount > 11)
                    {
                        Console.WriteLine(i+" amount will have chip "+ chipcount);
                        // print("\(i) amount will have chip \(chipcount)")
                    }
                }
            }
        }
    }
}