- Home /
How to divide a number by specific set of numbers so the result is always zero
Hey guys !
I am working on little roulette game where the player places chips and must reach a score with the lowest chips possible. The thing I am trying to accomplish is to make the game finds how many chips player must use to reach that score, for, in the end screen, display how player did and how the game would do it !
My values are 35, 17, 11, 8 and 5 ! I tried to divide my score with my first value, 35, if the score allows it so if its value is greater or equal to 35, then the logical path in my head would be using the remainder, divide by 17, 11, 8, or 5 if possible, but the thing is, sometimes this doesn't work, like for example if my score is 70, the game will find out that the lowest number of chips to use will be 2 as follow 2 x 35, right ? But it would do the same with 71, with 1 left since it doesn't fit any other values I set. However i want to reach 0 each time!. The lowest number of chips for 71 would be 1 x 35, 1 x 17, 1 x 11, 1 x 8, 0 x 5, so 4 in total ! I tried mixing % and / but can't get something working.. Here's something I tried at first
int myScore = some_value;
int remainder, chipNb35, chipNb17, chipNb11, chipNb8, chipNb5;
if (myScore >= 35)
{
chipNb35 = myScore / 35;
remainder = myScore % 35;
if (remainder < 35 && remainder >= 17)
{
chipNb17 = remainder / 17;
remainder = remainder % 17;
}
// and so on
}
I don't know if everything is clear enough to understand.. If it is, I would really appreciate having a main guide line for me to investigate and try by myself first before dying from a seizure and ask for serious help !
Thanks in advance :)
Answer by Bunny83 · Nov 02, 2021 at 05:15 PM
I've quickly implemented an bottom up solution that should work with any number of coins and should output the optimal solution:
public class CoinStack
{
public int coinValue;
public int totalCount;
public CoinStack next = null;
public override string ToString()
{
if (coinValue == 0)
return "No solution";
var sb = new System.Text.StringBuilder();
sb.Append(coinValue);
for (var cur = this.next; cur != null && cur.coinValue > 0; cur = cur.next)
sb.Append(", ").Append(cur.coinValue);
return sb.ToString();
}
public CoinStack[] Tally()
{
Dictionary<int, CoinStack> dict = new Dictionary<int, CoinStack>();
for (var current = this; current != null && current.coinValue > 0; current = current.next)
{
CoinStack c = null;
if (!dict.TryGetValue(current.coinValue, out c))
{
c = new CoinStack { coinValue = current.coinValue, totalCount = 0 };
dict.Add(current.coinValue, c);
}
c.totalCount++;
}
var values = dict.Values;
CoinStack[] result = new CoinStack[values.Count];
values.CopyTo(result,0);
return result;
}
}
public class CoinDB
{
private int[] coins;
private List<CoinStack> stack = new List<CoinStack>();
public CoinDB(params int[] aCoins)
{
coins = aCoins;
stack.Add(new CoinStack { coinValue=0, totalCount=0 });
}
public CoinStack GetChange(int aAmount)
{
if (aAmount < 1)
return null;
// requested number not yet in our DB
if (aAmount >= stack.Count)
{
// add missing values up to our current amount
for (int i = stack.Count; i <= aAmount; i++)
{
var newNode = new CoinStack { totalCount = aAmount + 1 };
stack.Add(newNode);
for (int n = 0; n < coins.Length; n++)
{
int coinValue = coins[n];
int remainder = i - coinValue;
// if the remainder is negative, there's no solution with this coin, so try the next
if (remainder < 0)
continue;
var prev = stack[remainder];
// if the remainder amount does not have a solution, try the next coin
if (prev.totalCount == -1)
continue;
// found solution of length "count"
int count = prev.totalCount + 1;
if (count < newNode.totalCount)
{
// the new solution is better than the old one, so replace it
newNode.coinValue = coinValue;
newNode.next = prev;
newNode.totalCount = count;
}
}
// if after we tried all coins we still have no solution, there is no solution for this value
if (newNode.coinValue == 0)
{
newNode.totalCount = -1;
}
}
}
return stack[aAmount];
}
}
Note the CoinDB class is meant to be created once for a set of coins. It will remember all intermediate values. You can call the "GetChange" method several times and the internal DB will grow if necessary. Yes, finding the optimal solution requires some memory, however it's not that much after all. The CoinStack instances will form a tree of nodes which when traversed give you the actual solution. I've added the "Tally" method to actually count each individual coin and provide a compact solution.
I've even tried it with a value around 1 million and it performs well on my pc. (ps: it takes almost 30000 coins with value of 35 to get over a million ^^).
My test code currently looks like this:
var sw = new System.Diagnostics.Stopwatch();
sw.Start();
var coinDB = new CoinDB(35, 17, 11, 8, 5);
var res = coinDB.GetChange(1046873);
sw.Stop();
var getChangeTime = sw.ElapsedMilliseconds;
sw.Start();
Debug.Log("CompleteSolution: " + res);
sw.Stop();
var debugPrintTime1 = sw.ElapsedMilliseconds;
sw.Start();
var coinList = res.Tally();
sw.Stop();
var TallyTime = sw.ElapsedMilliseconds;
sw.Start();
foreach (var c in coinList)
{
Debug.Log(""+c.totalCount + " x " + c.coinValue);
}
sw.Stop();
var debugPrintTime2 = sw.ElapsedMilliseconds;
Debug.Log(
"getChangeTime: " + getChangeTime + "\n"+
"debugPrintTime1: " + debugPrintTime1 + "\n" +
"TallyTime: " + TallyTime + "\n" +
"debugPrintTime2: " + debugPrintTime2 + "\n");
ps: the value of "1046873" can be split up into
29910 x 35
1 x 8
3 x 5
pps: don't try too many of those large numbers as the "CompleteSolution" debug log will actually log 29910 times the string "35, " into the editor log. The console window will trucate the message.
If someone is interested in how the first 5000 integers can be broken up into those coins, I created a list.
Answer by Eno-Khaon · Nov 01, 2021 at 06:59 PM
This sounds like a classic scenario for a "Change Calculator". Since your goal is finding the fewest necessary value units to reach your goal, you can use them accordingly.
Borrowing a reasonably-shortened formatting example, it might look something like this:
public struct Chip
{
string name;
int value;
public Chip(string name, int value)
{
this.name = name;
this.value = value;
}
}
// ...
public Chip[] chipTypes = new Chip[]
{
new Chip("chipNb35", 35),
new Chip("chipNb17", 17),
new Chip("chipNb11", 11),
new Chip("chipNb8", 8),
new Chip("chipNb5", 5),
new Chip("chipNb1", 1)
};
// ...
// When using it:
int[] minimumScore = new int[chipTypes.Length];
// Make a copy of the total before messing with it
int processedTotal = totalValue;
for(int i = 0; i < chipTypes.Length; i++)
{
minimumScore[i] = processedTotal / chipTypes[i].value;
// Since we stored the values already, a multiplication and subtraction
// should be cheaper to calculate than a division (modulo)
processedTotal -= minimumScore[i] * chipTypes[i].value;
}
// Simple example of showing the result
Debug.Log(string.Format("{0} can be broken down to:", totalValue));
for(int i = 0; i < chipTypes.Length; i++)
{
if(minimumScore[i] > 0)
{
Debug.Log(string.Format("{0} ({1}): {2} -> {3} chips", chipTypes[i].name, chipTypes[i].value, chipTypes[i].value * minimumScore[i], minimumScore[i]));
}
}
The output should look something like:
102 can be broken down to:
chipNb35 (35): 70 -> 2 chips
chipNb17 (17): 17 -> 1 chips
chipNb8 (8): 8 -> 1 chips
chipNb5 (5): 5 -> 1 chips
chipNb1 (1): 2 -> 2 chips
Another way of doing it ! Thanks man, I'll take a look at this too :)
Well, the question is what the exact goal is. Because this solution always uses up the highest elements first if they fit. That does not necessarily produce the fewest chips. Funnily your example of 102 is actually 6x17 so you only need 6 chips while your solution uses 7 chips.
Your approach does work for breaking down a number system that has regular intervals and no ambiguity (like any common number system such as binary or decimal or hexadecimal). However with such irregular steps between chips there are other solutions.
I can think of many examples where your approach would produce larger number of chips. For example "10". Your approach would pick 1x8, 2x1 which is 3 chips. Though you can pick 2x5 as well.
As far as I know there's no neat fast way to get to the optimal solution. You always have to evaluate all possibilities. Though depending on the approach certain solutions or whole trees can be eli$$anonymous$$ated quickly since we're only interested in the fewest amount of chips.
See this video which explains the problem and possible solutions.
Answer by Betina_art · Nov 01, 2021 at 02:43 PM
Hi! @Dawnou How about this:
If you get a remainder, you do the checks for if the remainder is greater than any of your chips. If it can't find any chips smaller than the remainder, it should take 1 off and add that chip's value to the remainder and do the checks again.
Like with the example that you gave of 71, after finding that none of the chips are greater/equal to 1, it will reduce the number of 35 chips from 2 to 1, and then the remainder will be 36. Then it will check the chips again (but leave 35 out of it of course)
Basically it should keep doing these checks in a while loop (while the remainder is not equal to 0).