Back to Repositories

Testing Coin Change Algorithm Implementations in williamfiset/Algorithms

This test suite validates the coin change dynamic programming algorithm implementations in the Algorithms repository. It verifies both standard and space-efficient solutions for finding the minimum number of coins needed to make a given amount, along with tracking the selected coins.

Test Coverage Overview

The test suite provides comprehensive coverage of the coin change algorithm implementations:

Tests standard, space-efficient, and recursive implementations
Validates minimum coin count calculations
Verifies selected coin tracking functionality
Tests with random coin values and target amounts
Handles edge cases with invalid combinations

Implementation Analysis

The testing approach employs JUnit 5 with systematic validation of multiple algorithm implementations. It uses randomized testing with 100 iterations per test case, comparing results between different implementations to ensure consistency. The tests leverage Google Truth assertions for cleaner verification syntax.

Key patterns include parallel implementation testing, solution equivalence verification, and selected coin validation.

Technical Details

Testing tools and configuration:

JUnit Jupiter for test execution
Google Truth for assertions
Google Guava for primitive array handling
Custom TestUtils for random test data generation
Loops constant set to 100 iterations

Best Practices Demonstrated

The test suite exemplifies several testing best practices:

Randomized testing for broad input coverage
Cross-implementation verification
Separate test methods for distinct functionality
Thorough validation of output properties
Clear test method naming and organization

williamfiset/algorithms

src/test/java/com/williamfiset/algorithms/dp/CoinChangeTest.java

            
package com.williamfiset.algorithms.dp;

import static com.google.common.truth.Truth.assertThat;

import com.google.common.primitives.Ints;
import com.williamfiset.algorithms.utils.TestUtils;
import java.util.*;
import org.junit.jupiter.api.*;

public class CoinChangeTest {

  static final int LOOPS = 100;

  @Test
  public void testCoinChange() {
    for (int i = 1; i < LOOPS; i++) {
      List<Integer> values = TestUtils.randomIntegerList(i, 1, 1000);
      int[] coinValues = Ints.toArray(values);

      int amount = TestUtils.randValue(1, 1000);

      CoinChange.Solution solution1 = CoinChange.coinChange(coinValues, amount);
      CoinChange.Solution solution2 = CoinChange.coinChangeSpaceEfficient(coinValues, amount);
      int v1 = solution1.minCoins.isPresent() ? solution1.minCoins.get() : -1;
      int v2 = solution2.minCoins.isPresent() ? solution2.minCoins.get() : -1;
      int v3 = CoinChange.coinChangeRecursive(coinValues, amount);

      assertThat(v1).isEqualTo(v2);
      assertThat(v2).isEqualTo(v3);
    }
  }

  @Test
  public void testCoinChangeSelectedCoins() {
    for (int i = 1; i < LOOPS; i++) {
      List<Integer> values = TestUtils.randomIntegerList(i, 1, 1000);
      int[] coinValues = Ints.toArray(values);

      int amount = TestUtils.randValue(1, 1000);

      CoinChange.Solution solution = CoinChange.coinChange(coinValues, amount);
      int selectedCoinsSum = 0;
      for (int v : solution.selectedCoins) {
        selectedCoinsSum += v;
      }
      if (!solution.minCoins.isPresent()) {
        assertThat(solution.selectedCoins.size()).isEqualTo(0);
      } else {
        // Verify that the size of the selected coins is equal to the optimal solution.
        assertThat(solution.selectedCoins.size()).isEqualTo(solution.minCoins.get());

        // Further verify that the sum of the selected coins equals the amount we want to make.
        assertThat(selectedCoinsSum).isEqualTo(amount);
      }
    }
  }

  @Test
  public void testCoinChangeSpaceEfficientSelectedCoins() {
    for (int i = 1; i < LOOPS; i++) {
      List<Integer> values = TestUtils.randomIntegerList(i, 1, 1000);
      int[] coinValues = Ints.toArray(values);

      int amount = TestUtils.randValue(1, 1000);

      CoinChange.Solution solution = CoinChange.coinChangeSpaceEfficient(coinValues, amount);
      int selectedCoinsSum = 0;
      for (int v : solution.selectedCoins) {
        selectedCoinsSum += v;
      }
      if (!solution.minCoins.isPresent()) {
        assertThat(solution.selectedCoins.size()).isEqualTo(0);
      } else {
        // Verify that the size of the selected coins is equal to the optimal solution.
        assertThat(solution.selectedCoins.size()).isEqualTo(solution.minCoins.get());

        // Further verify that the sum of the selected coins equals the amount we want to make.
        assertThat(selectedCoinsSum).isEqualTo(amount);
      }
    }
  }
}