Skip to content

Commit c4a2639

Browse files
kolosovpetrosiriak
kolosovpetro
and
siriak
authored
Add coin change problem (TheAlgorithms#280)
Co-authored-by: Andrii Siriak <siryaka@gmail.com>
1 parent c95d8aa commit c4a2639

File tree

6 files changed

+353
-0
lines changed

6 files changed

+353
-0
lines changed

‎Algorithms.Tests/Problems/CoinChange/Dynamic/GenerateChangesDictionaryTests.cs

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
using System.Linq;
2+
using Algorithms.Problems.CoinChange;
3+
using FluentAssertions;
4+
using NUnit.Framework;
5+
6+
namespace Algorithms.Tests.Problems.CoinChange.Dynamic
7+
{
8+
[TestFixture]
9+
public class GenerateChangesDictionaryTests
10+
{
11+
[Test]
12+
public void GenerateChangesDictionaryTest_Success()
13+
{
14+
const int coin = 6;
15+
var coins = new[] { 1, 3, 4 };
16+
var changeDictionary = DynamicCoinChangeSolver.GenerateChangesDictionary(coin, coins);
17+
18+
changeDictionary[1].SequenceEqual(new[] { 0 }).Should().BeTrue();
19+
changeDictionary[2].SequenceEqual(new[] { 1 }).Should().BeTrue();
20+
changeDictionary[3].SequenceEqual(new[] { 0, 2 }).Should().BeTrue();
21+
changeDictionary[4].SequenceEqual(new[] { 0, 1, 3 }).Should().BeTrue();
22+
changeDictionary[5].SequenceEqual(new[] { 1, 2, 4 }).Should().BeTrue();
23+
changeDictionary[6].SequenceEqual(new[] { 2, 3, 5 }).Should().BeTrue();
24+
}
25+
}
26+
}

‎Algorithms.Tests/Problems/CoinChange/Dynamic/GenerateSingleCoinChangesTests.cs

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
using System;
2+
using System.Linq;
3+
using Algorithms.Problems.CoinChange;
4+
using FluentAssertions;
5+
using NUnit.Framework;
6+
7+
namespace Algorithms.Tests.Problems.CoinChange.Dynamic
8+
{
9+
[TestFixture]
10+
public class GenerateSingleCoinChangesTests
11+
{
12+
[Test]
13+
public void GenerateSingleCoinChangesTests_Success()
14+
{
15+
DynamicCoinChangeSolver
16+
.GenerateSingleCoinChanges(6, new[] { 1, 2, 3 })
17+
.SequenceEqual(new[] { 3, 4, 5 })
18+
.Should().BeTrue();
19+
20+
DynamicCoinChangeSolver
21+
.GenerateSingleCoinChanges(10, new[] { 1, 2, 3, 7, 12, 15, 14 })
22+
.SequenceEqual(new[] { 3, 7, 8, 9 })
23+
.Should().BeTrue();
24+
25+
DynamicCoinChangeSolver
26+
.GenerateSingleCoinChanges(1, new[] { 1, 2, 3, 7, 12, 15, 14 })
27+
.SequenceEqual(new[] { 0 })
28+
.Should().BeTrue();
29+
30+
DynamicCoinChangeSolver
31+
.GenerateSingleCoinChanges(2, new[] { 1, 2, 3, 7, 12, 15, 14 })
32+
.SequenceEqual(new[] { 0, 1 })
33+
.Should().BeTrue();
34+
}
35+
36+
[Test]
37+
public void GenerateSingleCoinChangesTests_ShouldThrow_CoinCannotBeLesserOrEqualZero()
38+
{
39+
const int coin = 0;
40+
var arr = new[] { 1, 2, 3 };
41+
42+
Func<int[]> act = () => DynamicCoinChangeSolver.GenerateSingleCoinChanges(coin, arr);
43+
44+
act.Should().Throw<InvalidOperationException>()
45+
.WithMessage($"The coin cannot be lesser or equal to zero {nameof(coin)}.");
46+
}
47+
48+
[Test]
49+
public void GenerateSingleCoinChangesTests_ShouldThrow_CoinsArrayCannotBeEmpty()
50+
{
51+
const int coin = 10;
52+
var coinsAsArray = Array.Empty<int>();
53+
54+
Func<int[]> act = () => DynamicCoinChangeSolver.GenerateSingleCoinChanges(coin, coinsAsArray);
55+
56+
act.Should().Throw<InvalidOperationException>()
57+
.WithMessage($"Coins array cannot be empty {nameof(coinsAsArray)}.");
58+
}
59+
60+
[Test]
61+
public void GenerateSingleCoinChangesTests_ShouldThrow_CoinsArrayMustContainOne()
62+
{
63+
const int coin = 10;
64+
var coinsAsArray = new[] { 2, 3, 4 };
65+
66+
Func<int[]> act = () => DynamicCoinChangeSolver.GenerateSingleCoinChanges(coin, coinsAsArray);
67+
68+
act.Should().Throw<InvalidOperationException>()
69+
.WithMessage($"Coins array must contain coin 1 {nameof(coinsAsArray)}.");
70+
}
71+
72+
[Test]
73+
public void GenerateSingleCoinChangesTests_ShouldThrow_CoinsArrayCannotContainNegativeValues()
74+
{
75+
const int coin = 10;
76+
var coinsAsArray = new[] { 1, 2, -3, 4 };
77+
78+
Func<int[]> act = () => DynamicCoinChangeSolver.GenerateSingleCoinChanges(coin, coinsAsArray);
79+
80+
act.Should().Throw<InvalidOperationException>()
81+
.WithMessage($"{nameof(coinsAsArray)} cannot contain numbers less than or equal to zero");
82+
}
83+
84+
[Test]
85+
public void GenerateSingleCoinChangesTests_ShouldThrow_CoinsArrayCannotContainDuplicates()
86+
{
87+
const int coin = 10;
88+
var coinsAsArray = new[] { 1, 2, 3, 3, 4 };
89+
90+
Func<int[]> act = () => DynamicCoinChangeSolver.GenerateSingleCoinChanges(coin, coinsAsArray);
91+
92+
act.Should().Throw<InvalidOperationException>()
93+
.WithMessage($"Coins array cannot contain duplicates {nameof(coinsAsArray)}.");
94+
}
95+
}
96+
}

‎Algorithms.Tests/Problems/CoinChange/Dynamic/GetMinimalNextCoinTests.cs

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
using Algorithms.Problems.CoinChange;
2+
using FluentAssertions;
3+
using NUnit.Framework;
4+
5+
namespace Algorithms.Tests.Problems.CoinChange.Dynamic
6+
{
7+
public class GetMinimalNextCoinTests
8+
{
9+
[Test]
10+
public void GetMinimalNextCoinTest_Success()
11+
{
12+
const int coin = 6;
13+
var coins = new[] { 1, 3, 4 };
14+
var exchangeDict = DynamicCoinChangeSolver.GenerateChangesDictionary(coin, coins);
15+
var nextCoin = DynamicCoinChangeSolver.GetMinimalNextCoin(6, exchangeDict);
16+
17+
nextCoin.Should().Be(3);
18+
}
19+
}
20+
}

‎Algorithms.Tests/Problems/CoinChange/Dynamic/MakeCoinChangeDynamicTests.cs

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
using System.Linq;
2+
using Algorithms.Problems.CoinChange;
3+
using FluentAssertions;
4+
using NUnit.Framework;
5+
6+
namespace Algorithms.Tests.Problems.CoinChange.Dynamic
7+
{
8+
[TestFixture]
9+
public class MakeCoinChangeDynamicTests
10+
{
11+
[Test]
12+
public void MakeCoinChangeDynamicTest_Success()
13+
{
14+
DynamicCoinChangeSolver
15+
.MakeCoinChangeDynamic(6, new[] { 1, 3, 4 })
16+
.SequenceEqual(new[] { 3, 3 })
17+
.Should().BeTrue();
18+
19+
DynamicCoinChangeSolver
20+
.MakeCoinChangeDynamic(8, new[] { 1, 3, 4 })
21+
.SequenceEqual(new[] { 4, 4 })
22+
.Should().BeTrue();
23+
24+
DynamicCoinChangeSolver
25+
.MakeCoinChangeDynamic(25, new[] { 1, 3, 4, 12, 13, 14 })
26+
.SequenceEqual(new[] { 13, 12 })
27+
.Should().BeTrue();
28+
29+
DynamicCoinChangeSolver
30+
.MakeCoinChangeDynamic(26, new[] { 1, 3, 4, 12, 13, 14 })
31+
.SequenceEqual(new[] { 14, 12 })
32+
.Should().BeTrue();
33+
}
34+
}
35+
}

‎Algorithms/Problems/CoinChange/DynamicCoinChangeSolver.cs

Lines changed: 174 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,174 @@
1+
using System;
2+
using System.Collections.Generic;
3+
using System.Linq;
4+
5+
namespace Algorithms.Problems.CoinChange
6+
{
7+
public static class DynamicCoinChangeSolver
8+
{
9+
/// <summary>
10+
/// Generates an array of changes for current coin.
11+
/// For instance, having coin C = 6 and array A = [1,3,4] it returns an array R = [2,3,5].
12+
/// Because, 6 - 4 = 2, 6 - 3 = 3, 6 - 1 = 5.
13+
/// </summary>
14+
/// <param name="coin">The value of the coin to be exchanged.</param>
15+
/// <param name="coins">An array of available coins.</param>
16+
/// <returns>Array of changes of current coins by available coins.</returns>
17+
public static int[] GenerateSingleCoinChanges(int coin, int[] coins)
18+
{
19+
ValidateCoin(coin);
20+
ValidateCoinsArray(coins);
21+
22+
var coinsArrayCopy = new int[coins.Length];
23+
24+
Array.Copy(coins, coinsArrayCopy, coins.Length);
25+
Array.Sort(coinsArrayCopy);
26+
Array.Reverse(coinsArrayCopy);
27+
28+
var list = new List<int>();
29+
30+
foreach (var item in coinsArrayCopy)
31+
{
32+
if (item > coin)
33+
{
34+
continue;
35+
}
36+
37+
var difference = coin - item;
38+
39+
list.Add(difference);
40+
}
41+
42+
var result = list.ToArray();
43+
44+
return result;
45+
}
46+
47+
/// <summary>
48+
/// Given a positive integer N, such as coin.
49+
/// Generates a change dictionary for all values [1,N].
50+
/// Used in so-called backward induction in search of the minimum exchange.
51+
/// </summary>
52+
/// <param name="coin">The value of coin.</param>
53+
/// <param name="coins">Array of available coins.</param>
54+
/// <returns>Change dictionary for all values [1,N], where N is the coin.</returns>
55+
public static Dictionary<int, int[]> GenerateChangesDictionary(int coin, int[] coins)
56+
{
57+
var dict = new Dictionary<int, int[]>();
58+
var currentCoin = 1;
59+
60+
while (currentCoin <= coin)
61+
{
62+
var changeArray = GenerateSingleCoinChanges(currentCoin, coins);
63+
dict[currentCoin] = changeArray;
64+
currentCoin++;
65+
}
66+
67+
return dict;
68+
}
69+
70+
/// <summary>
71+
/// Gets a next coin value, such that changes array contains the minimal change overall possible changes.
72+
/// For example, having coin N = 6 and A = [1,3,4] coins array.
73+
/// The minimum next coin for 6 will be 3, because changes of 3 by A = [1,3,4] contains 0, the minimal change.
74+
/// </summary>
75+
/// <param name="coin">Coin to be exchanged.</param>
76+
/// <param name="exchanges">Dictionary of exchanges for [1, coin].</param>
77+
/// <returns>Index of the next coin with minimal exchange.</returns>
78+
public static int GetMinimalNextCoin(int coin, Dictionary<int, int[]> exchanges)
79+
{
80+
var nextCoin = int.MaxValue;
81+
var minChange = int.MaxValue;
82+
83+
var coinChanges = exchanges[coin];
84+
85+
foreach (var change in coinChanges)
86+
{
87+
if (change == 0)
88+
{
89+
return 0;
90+
}
91+
92+
var currentChange = exchanges[change];
93+
var min = currentChange.Min();
94+
95+
var minIsLesser = min < minChange;
96+
97+
if (minIsLesser)
98+
{
99+
nextCoin = change;
100+
minChange = min;
101+
}
102+
}
103+
104+
return nextCoin;
105+
}
106+
107+
/// <summary>
108+
/// Performs a coin change such that an amount of coins is minimal.
109+
/// </summary>
110+
/// <param name="coin">The value of coin to be exchanged.</param>
111+
/// <param name="coins">An array of available coins.</param>
112+
/// <returns>Array of exchanges.</returns>
113+
public static int[] MakeCoinChangeDynamic(int coin, int[] coins)
114+
{
115+
var changesTable = GenerateChangesDictionary(coin, coins);
116+
var list = new List<int>();
117+
118+
var currentCoin = coin;
119+
var nextCoin = int.MaxValue;
120+
121+
while (nextCoin != 0)
122+
{
123+
nextCoin = GetMinimalNextCoin(currentCoin, changesTable);
124+
var difference = currentCoin - nextCoin;
125+
list.Add(difference);
126+
currentCoin = nextCoin;
127+
}
128+
129+
var result = list.ToArray();
130+
131+
return result;
132+
}
133+
134+
private static void ValidateCoin(int coin)
135+
{
136+
if (coin <= 0)
137+
{
138+
throw new InvalidOperationException($"The coin cannot be lesser or equal to zero {nameof(coin)}.");
139+
}
140+
}
141+
142+
private static void ValidateCoinsArray(int[] coinsArray)
143+
{
144+
var coinsAsArray = coinsArray.ToArray();
145+
146+
if (coinsAsArray.Length == 0)
147+
{
148+
throw new InvalidOperationException($"Coins array cannot be empty {nameof(coinsAsArray)}.");
149+
}
150+
151+
var coinsContainOne = coinsAsArray.Any(x => x == 1);
152+
153+
if (!coinsContainOne)
154+
{
155+
throw new InvalidOperationException($"Coins array must contain coin 1 {nameof(coinsAsArray)}.");
156+
}
157+
158+
var containsNonPositive = coinsAsArray.Any(x => x <= 0);
159+
160+
if (containsNonPositive)
161+
{
162+
throw new InvalidOperationException(
163+
$"{nameof(coinsAsArray)} cannot contain numbers less than or equal to zero");
164+
}
165+
166+
var containsDuplicates = coinsAsArray.GroupBy(x => x).Any(g => g.Count() > 1);
167+
168+
if (containsDuplicates)
169+
{
170+
throw new InvalidOperationException($"Coins array cannot contain duplicates {nameof(coinsAsArray)}.");
171+
}
172+
}
173+
}
174+
}

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -124,6 +124,8 @@ This repository contains algorithms and data structures implemented in C# for ed
124124
* [Gale-Shapley](./Algorithms/Problems/StableMarriage/GaleShapley.cs)
125125
* [N-Queens](./Algorithms/Problems/NQueens)
126126
* [Backtracking](./Algorithms/Problems/NQueens/BacktrackingNQueensSolver.cs)
127+
* [Dynamic Coin Change](./Algorithms/Problems/CoinChange)
128+
* [Dynamic](./Algorithms/Problems/CoinChange/DynamicCoinChangeSolver.cs)
127129

128130
* [Data Structures](./DataStructures)
129131
* [Bit Array](./DataStructures/BitArray.cs)

0 commit comments

Comments
 (0)