DynamicCoinChangeSolver.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace Algorithms.Problems.CoinChange
{
    public static class DynamicCoinChangeSolver
    {
        /// <summary>
        /// Generates an array of changes for current coin.
        /// For instance, having coin C = 6 and array A = [1,3,4] it returns an array R = [2,3,5].
        /// Because, 6 - 4 = 2, 6 - 3 = 3, 6 - 1 = 5.
        /// </summary>
        /// <param name="coin">The value of the coin to be exchanged.</param>
        /// <param name="coins">An array of available coins.</param>
        /// <returns>Array of changes of current coins by available coins.</returns>
        public static int[] GenerateSingleCoinChanges(int coin, int[] coins)
        {
            ValidateCoin(coin);
            ValidateCoinsArray(coins);

            var coinsArrayCopy = new int[coins.Length];

            Array.Copy(coins, coinsArrayCopy, coins.Length);
            Array.Sort(coinsArrayCopy);
            Array.Reverse(coinsArrayCopy);

            var list = new List<int>();

            foreach (var item in coinsArrayCopy)
            {
                if (item > coin)
                {
                    continue;
                }

                var difference = coin - item;

                list.Add(difference);
            }

            var result = list.ToArray();

            return result;
        }

        /// <summary>
        /// Given a positive integer N, such as coin.
        /// Generates a change dictionary for all values [1,N].
        /// Used in so-called backward induction in search of the minimum exchange.
        /// </summary>
        /// <param name="coin">The value of coin.</param>
        /// <param name="coins">Array of available coins.</param>
        /// <returns>Change dictionary for all values [1,N], where N is the coin.</returns>
        public static Dictionary<int, int[]> GenerateChangesDictionary(int coin, int[] coins)
        {
            var dict = new Dictionary<int, int[]>();
            var currentCoin = 1;

            while (currentCoin <= coin)
            {
                var changeArray = GenerateSingleCoinChanges(currentCoin, coins);
                dict[currentCoin] = changeArray;
                currentCoin++;
            }

            return dict;
        }

        /// <summary>
        /// Gets a next coin value, such that changes array contains the minimal change overall possible changes.
        /// For example, having coin N = 6 and A = [1,3,4] coins array.
        /// The minimum next coin for 6 will be 3, because changes of 3 by A = [1,3,4] contains 0, the minimal change.
        /// </summary>
        /// <param name="coin">Coin to be exchanged.</param>
        /// <param name="exchanges">Dictionary of exchanges for [1, coin].</param>
        /// <returns>Index of the next coin with minimal exchange.</returns>
        public static int GetMinimalNextCoin(int coin, Dictionary<int, int[]> exchanges)
        {
            var nextCoin = int.MaxValue;
            var minChange = int.MaxValue;

            var coinChanges = exchanges[coin];

            foreach (var change in coinChanges)
            {
                if (change == 0)
                {
                    return 0;
                }

                var currentChange = exchanges[change];
                var min = currentChange.Min();

                var minIsLesser = min < minChange;

                if (minIsLesser)
                {
                    nextCoin = change;
                    minChange = min;
                }
            }

            return nextCoin;
        }

        /// <summary>
        /// Performs a coin change such that an amount of coins is minimal.
        /// </summary>
        /// <param name="coin">The value of coin to be exchanged.</param>
        /// <param name="coins">An array of available coins.</param>
        /// <returns>Array of exchanges.</returns>
        public static int[] MakeCoinChangeDynamic(int coin, int[] coins)
        {
            var changesTable = GenerateChangesDictionary(coin, coins);
            var list = new List<int>();

            var currentCoin = coin;
            var nextCoin = int.MaxValue;

            while (nextCoin != 0)
            {
                nextCoin = GetMinimalNextCoin(currentCoin, changesTable);
                var difference = currentCoin - nextCoin;
                list.Add(difference);
                currentCoin = nextCoin;
            }

            var result = list.ToArray();

            return result;
        }

        private static void ValidateCoin(int coin)
        {
            if (coin <= 0)
            {
                throw new InvalidOperationException($"The coin cannot be lesser or equal to zero {nameof(coin)}.");
            }
        }

        private static void ValidateCoinsArray(int[] coinsArray)
        {
            var coinsAsArray = coinsArray.ToArray();

            if (coinsAsArray.Length == 0)
            {
                throw new InvalidOperationException($"Coins array cannot be empty {nameof(coinsAsArray)}.");
            }

            var coinsContainOne = coinsAsArray.Any(x => x == 1);

            if (!coinsContainOne)
            {
                throw new InvalidOperationException($"Coins array must contain coin 1 {nameof(coinsAsArray)}.");
            }

            var containsNonPositive = coinsAsArray.Any(x => x <= 0);

            if (containsNonPositive)
            {
                throw new InvalidOperationException(
                    $"{nameof(coinsAsArray)} cannot contain numbers less than or equal to zero");
            }

            var containsDuplicates = coinsAsArray.GroupBy(x => x).Any(g => g.Count() > 1);

            if (containsDuplicates)
            {
                throw new InvalidOperationException($"Coins array cannot contain duplicates {nameof(coinsAsArray)}.");
            }
        }
    }
}