# The blog of dlaa.me

## A quick programming challenge with money [Counting and enumerating the ways to break a \$1 bill]

Sunday evening I happened across a blog post by Josh Smith about finding all the ways to break a \$1 bill. Specifically, the goal is to:

Count the number of ways to combine coins worth 100, 50, 25, 10, 5, and 1 cent for a total value of 100 cents

As Josh says, it's a fun challenge and I encourage you to stop reading now and solve it!

I took his advice and sat down with pen, paper, and a self-imposed 30 minute time limit. I came up with the C# solution below just before time ran out. As I note in the code, I forgot one line (though I caught it when typing up the solution). Less embarrassingly, this implementation worked correctly the first time I ran it. What's more, it's flexible with regard to the target amount and number/value of the coins (both of which are passed as parameters to the constructor). For bonus points, it outputs all the combinations it finds along the way.

I've added some comments to the code to outline the general algorithm. There are some opportunities to refactor for clarity and an implicit assumption values are passed in decreasing order, but otherwise I'm pretty happy with how it turned out.

If you take on the challenge and come up with something interesting, please leave a note - I'd love to see other approaches!

``````using System;

// Problem: Count (and output) all ways to make \$1 with U.S. coins (100, 50, 25, 10, 5, 1 cents).
// Inspiration: http://ijoshsmith.com/2014/11/30/getting-into-functional-programming-with-swift/

{
public static void Main()
{
// Entry point/test harness
Console.WriteLine("Total possibilities: {0}",
100,
new[] { 100, 50, 25, 10, 5, 1 })
.Invoke());
}

// Input
// State
private int _ways;

{
// Initialize
_target = target;
_values = values;
_counts = new int[values.Length];
_ways = 0;
}

public int Invoke()
{
// Start the recursive process and return the result
Recurse(0, 0);
return _ways;
}

private bool Recurse(int i, int sum)
{
if (_target == sum)
{
// Met the target, done here
ShowCounts();
_ways++;
return false;
}
else if (i == _counts.Length)
{
// Out of values, keep looking
return true;
}
else if (sum < _target)
{
// Search, using increasing counts of current value
while (Recurse(i + 1, sum))
{
_counts[i]++; // Note: Missed this line at first
sum += _values[i];
}
// Reset and continue
_counts[i] = 0;
return true;
}
else
{
// Exceeded the target, done here
return false;
}
}

private void ShowCounts()
{
// Show the count for each value
for (var i = 0; i < _counts.Length; i++)
{
Console.Write("{0}:{1} ", _values[i], _counts[i]);
}
Console.WriteLine();
}
}
``````