The blog of dlaa.me

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!

Seriously: Stop now. Spoilers ahead...

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/

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

    // Input
    private readonly int _target;
    private readonly int[] _values;
    // State
    private readonly int[] _counts;
    private int _ways;

    public BreakADollar(int target, int[] values)
    {
        // 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();
    }
}