Code Kata: Coin Counters

Problem:

There are four types of common coins in US currency:
  quarters (25 cents)
  dimes (10 cents)
  nickels (5 cents)
  pennies (1 cent)

There are 6 ways to make change for 15 cents:
  A dime and a nickel;
  A dime and 5 pennies;
  3 nickels;
  2 nickels and 5 pennies;
  A nickel and 10 pennies;
  15 pennies.

How many ways are there to make change for a dollar
using these common coins? (1 dollar = 100 cents).

Solution:

The idea is to work out the composition of the coins to make up an amount from the higher to the lower value coins. The remainder amount can be determined recursively.

Source Code:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace _03_Count_Coins
{
    class CountCoins
    {
        private static readonly int[] CoinValues = { 25, 10, 5, 1 };
        private static int _waysToMakeUp;

        static void Main(string[] args)
        {
            int amountInCents = 100;
            Debug.WriteLine(string.Format("There are {0} ways to make up {1} cents", WaysToMakeUpValue(amountInCents), amountInCents));
        }

        private static int WaysToMakeUpValue(int cents)
        {
            MakeUpValueBy(cents, 0, "");
            return _waysToMakeUp;
        }

        private static void MakeUpValueBy(int cents, int coinValueIndex, string outputPrefix)
        {
            for (int i = coinValueIndex; i < CoinValues.Length; i++)
            {
                Coin coin = new Coin(CoinValues[i]);
                List<coinnumberandremainder> cnrList = coin.GetCoinNumberAndRemainders(cents);
                foreach (CoinNumberAndRemainder cnr in cnrList)
                {
                    if (cnr.remainder == 0)
                    {
                        coin.printLine(outputPrefix, cnr.coinNumber);
                        _waysToMakeUp++;
                    }
                    else
                        MakeUpValueBy(cnr.remainder, i + 1, coin.ToString(outputPrefix, cnr.coinNumber));
                }
            }
        }
    }

    class Coin
    {
        private int _value;

        public Coin(int value)
        {
            _value = value;
        }

        public List<coinnumberandremainder> GetCoinNumberAndRemainders(int amount)
        {
            int numberOfCoins = amount / _value;

            if (_value == 1)
                return new List<coinnumberandremainder>() { GenerateCoinNumberAndRemainder(amount, numberOfCoins) };

            List<coinnumberandremainder> list = new List<coinnumberandremainder>();

            for (int i = numberOfCoins; i > 0; i--)
                list.Add(GenerateCoinNumberAndRemainder(amount, i));

            return list;
        }

        private CoinNumberAndRemainder GenerateCoinNumberAndRemainder(int amount, int numberOfCoins)
        {
            int remainder = amount - (numberOfCoins * _value);
            CoinNumberAndRemainder cnr = new CoinNumberAndRemainder()
            {
                coinNumber = numberOfCoins,
                remainder = remainder
            };
            return cnr;
        }

        public void printLine(string prefix, int coinNumber)
        {
            Debug.WriteLine(ToString(prefix, coinNumber));
        }

        public string ToString(string prefix, int coinNumber)
        {
            if (!string.IsNullOrEmpty(prefix))
                prefix += ", ";

            return prefix + string.Format("{0} cents with {1} coins", _value, coinNumber);
        }
    }

    struct CoinNumberAndRemainder
    {
        public int coinNumber;
        public int remainder;
    }
}