Forum Discussion
Solving 'The Change-making problem' with a formula
The Change-making problem
I have seen this problem appear on many coding challenge web sites. There are variations of the Change-making problem such as "The Coin Problem" or "The Coin Collector's Problem", etc. For this task, I decided to use US currency (and even included denominations no longer in print to make things interesting.).
The Rules
You have a list of denominations available. Presume the amount of bills available is unlimited. Given an amount, return as few bills as possible to cover the amount due.
Methods
My research into this problem found the three most common approaches to this problem:
-generate all combinations = amount due and select the one with fewest elements
-Dynamic programming with a probabilistic convolution tree
-The Greedy algorithm
The first method has been discussed on this forum in several threads. The second method would require more research into making it transferrable to Excel. The Greedy algorithm stood out to me because it seemed like the most sensible way to tackle this problem.
My first thought was to create the Greedy algorithm as a recursive Lambda. I picked at it a bit and tried solutions, but it seemed contorted. Seemed like I was purposely disregarding more powerful functions available to make something work. I went with dynamic arrays...
My solution:
Solve
=LAMBDA(denom,owed,LET(
keep, XMATCH(owed, denom, -1),
bills, SORT(TAKE(denom, keep), , -1),
largest_bill, MAX(bills),
c, MAX(5, ROUNDUP(owed / largest_bill, 0)),
bill_matrix, bills * SEQUENCE(, c, 1, 0),
GetGreedy, LAMBDA(acc, v,
LET(stack, VSTACK(acc, v), IF(SUM(stack) > owed, DROP(stack, -1), stack))
),
bill_stack, REDUCE(, bill_matrix, GetGreedy),
return, XLOOKUP(bill_stack, denom, BillPix, ""),
tendered, SUM(bill_stack),
accuracy_check, HSTACK("Amount tendered:", tendered, IF(Amt_Due = tendered, "☑", "X"), ""),
IFERROR(VSTACK(accuracy_check, WRAPROWS(return, 4, "")), "")
))
I welcome any solutions using formulas, PowerQuery, and even Python in Excel. Please no AI contributions.
How would you solve the Change-making problem?
Workbooks attached: I have included (2) versions. ‘Image Version’ makes use of the 365 feature to place pictures in cell. I also included a version without images that returns the amounts as an array of numbers.
References
The Change-making problem
https://dl.acm.org/doi/10.1145/321864.321874
Greedy algorithm
5 Replies
Patrick2788 My first thought was also to use a recursive Lambda. Seems like the easiest way to go; plus, iteration limits aren't a concern, as the amount is being reduced down to zero. I didn't research the fore-mentioned algorithms, but I'm guessing this is what's meant by the "Greedy" method:
CHANGEDUE: =LAMBDA(amount_due,denominations,[change_due], LET( v, IF(ISOMITTED(change_due), MAX((denominations<=amount_due)*denominations), change_due), a, ROUND(amount_due-SUM(v), 2), IF(a>0, CHANGEDUE(amount_due, denominations, VSTACK(v, MAX((denominations<=a)*denominations))), v) ) )I went to 2 decimal places here to include coins in the denominations. Again, I'm not entirely sure how the new GROUPBY function works, but perhaps it could be used to generate a summary of the denominations needed:
=LET( due, CHANGEDUE(Amt_Due, denominations), GROUPBY(due, due, COUNT, 0, 0) )For the workbook with images, the final output could be:
=LET( due, CHANGEDUE(Amt_Due, denominations), total, SUM(due), IFNA(VSTACK(HSTACK("Amount tendered:", total, IF(total = Amt_Due, "☑", "X")), WRAPROWS(XLOOKUP(due, denominations, BillPix), 4)), "") )Your solution is very economical and elegant at the same. It performs very well up to a little over $200 million before it reaches recursion limits. I think it definitely takes after the greedy algorithim approach and could probably be used to solve similar problems which have multiple solutions.
I'll have to check the GROUPBY part later on my home computer. At work I'm without insider so no GROUPBY/PIVOTBY/PERCENTOF for me.
Patrick2788 Yes, I didn't take into account extremely large amounts, which will hit the recursion limits. To overcome this, and to reduce the number of iterations down to a bare minimum, the formula can be modified to take the maximum number of the maximum denominations each time around:
CHANGEDUE: =LAMBDA(amount_due,denominations,[change_due], LET( v, IF(ISOMITTED(change_due), LET(m, MAX((denominations<=amount_due)*denominations), IF(SEQUENCE(IFERROR(INT(amount_due/m), 1)), m)), change_due), a, ROUND(amount_due-SUM(v), 2), IF(a>0, LET(m, MAX((denominations<=a)*denominations), CHANGEDUE(amount_due, denominations, VSTACK(v, IF(SEQUENCE(INT(a/m)), m)))), v) ) )This will work up to the maximum number of rows allowed by SEQUENCE (1,048,576), so it will accept an amount due of up to 100 Billion. 🙂
EDIT: after posting the modified formula above, a lightbulb went off as I realized the same logic can simply be applied to the REDUCE function:
=LET( a, Amt_Due, d, SORT(denominations,, -1), m, MAX((d<=a)*d), IF(m=0, 0, REDUCE(IF(SEQUENCE(INT(a/m)), m), d, LAMBDA(v,n, LET( b, a-SUM(v), IF(n<=b, VSTACK(v, IF(SEQUENCE(INT(b/n)), n)), v))))) )So, to generate the final output for the workbook with the images:
=LET( a, Amt_Due, d, SORT(denominations,, -1), m, MAX((d<=a)*d), due, IF(m=0, 0, REDUCE(IF(SEQUENCE(INT(a/m)), m), d, LAMBDA(v,n, LET( b, a-SUM(v), IF(n<=b, VSTACK(v, IF(SEQUENCE(INT(b/n)), n)), v))))), total, SUM(due), IFNA(VSTACK(HSTACK("Amount tendered:", total, IF(total=a, "☑", "X")), WRAPROWS(XLOOKUP(due, denominations, BillPix, ""), 4)), "") )Cheers!
