Avatar of paulfioravanti

paulfioravanti's solution

to Change in the Elixir Track

Published at Aug 25 2019 · 0 comments
Instructions
Test suite
Solution

Correctly determine the fewest number of coins to be given to a customer such that the sum of the coins' value would equal the correct amount of change.

For example

  • An input of 15 with [1, 5, 10, 25, 100] should return one nickel (5) and one dime (10) or [0, 1, 1, 0, 0]
  • An input of 40 with [1, 5, 10, 25, 100] should return one nickel (5) and one dime (10) and one quarter (25) or [0, 1, 1, 1, 0]

Edge cases

  • Does your algorithm work for any given set of coins?
  • Can you ask for negative change?
  • Can you ask for a change value smaller than the smallest coin value?

Running tests

Execute the tests with:

$ mix test

Pending tests

In the test suites, all but the first test have been skipped.

Once you get a test passing, you can unskip the next one by commenting out the relevant @tag :pending with a # symbol.

For example:

# @tag :pending
test "shouting" do
  assert Bob.hey("WATCH OUT!") == "Whoa, chill out!"
end

Or, you can enable all the tests by commenting out the ExUnit.configure line in the test suite.

# ExUnit.configure exclude: :pending, trace: true

If you're stuck on something, it may help to look at some of the available resources out there where answers might be found.

Source

Software Craftsmanship - Coin Change Kata https://web.archive.org/web/20130115115225/http://craftsmanship.sv.cmu.edu:80/exercises/coin-change-kata

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

change_test.exs

defmodule ChangeTest do
  use ExUnit.Case

  # @tag :pending
  test "single coin change" do
    coins = [1, 5, 10, 25, 100]
    expected = [25]
    assert Change.generate(coins, 25) == {:ok, expected}
  end

  @tag :pending
  test "multiple coin change" do
    coins = [1, 5, 10, 25, 100]
    expected = [5, 10]
    assert Change.generate(coins, 15) == {:ok, expected}
  end

  @tag :pending
  test "change with Lilliputian Coins" do
    coins = [1, 4, 15, 20, 50]
    expected = [4, 4, 15]
    assert Change.generate(coins, 23) == {:ok, expected}
  end

  @tag :pending
  test "change with Lower Elbonia Coins" do
    coins = [1, 5, 10, 21, 25]
    expected = [21, 21, 21]
    assert Change.generate(coins, 63) == {:ok, expected}
  end

  @tag :pending
  test "large target values" do
    coins = [1, 2, 5, 10, 20, 50, 100]
    expected = [2, 2, 5, 20, 20, 50, 100, 100, 100, 100, 100, 100, 100, 100, 100]
    assert Change.generate(coins, 999) == {:ok, expected}
  end

  @tag :pending
  test "possible change without unit coins available" do
    coins = [2, 5, 10, 20, 50]
    expected = [2, 2, 2, 5, 10]
    assert Change.generate(coins, 21) == {:ok, expected}
  end

  @tag :pending
  test "no coins make 0 change" do
    coins = [1, 5, 10, 21, 25]
    expected = []
    assert Change.generate(coins, 0) == {:ok, expected}
  end

  @tag :pending
  test "error testing for change smaller than the smallest of coins" do
    coins = [5, 10]
    assert Change.generate(coins, 3) == {:error, "cannot change"}
  end

  @tag :pending
  test "error if no combination can add up to target" do
    coins = [5, 10]
    assert Change.generate(coins, 94) == {:error, "cannot change"}
  end

  @tag :pending
  test "cannot find negative change values" do
    coins = [1, 2, 5]
    assert Change.generate(coins, -5) == {:error, "cannot change"}
  end
end

test_helper.exs

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)
defmodule Change do
  @error_message "cannot change"

  @doc """
    Determine the least number of coins to be given to the user such
    that the sum of the coins' value would equal the correct amount of change.
    It returns {:error, "cannot change"} if it is not possible to compute the
    right amount of coins. Otherwise returns the tuple {:ok, list_of_coins}

    ## Examples

      iex> Change.generate([5, 10, 15], 3)
      {:error, "cannot change"}

      iex> Change.generate([1, 5, 10], 18)
      {:ok, [1, 1, 1, 5, 10]}

  """

  @spec generate(list, integer) :: {:ok, list} | {:error, String.t()}
  def generate(_coins, 0), do: {:ok, []}
  def generate(_coins, target) when target < 0, do: {:error, @error_message}

  def generate(coins, target) do
    if target < Enum.min(coins) do
      {:error, @error_message}
    else
      {_coins, change_candidates, _acc} =
        coins
        |> generate_useable_coins(target)
        |> generate_change_candidates(target)

      case change_candidates do
        [] ->
          {:error, @error_message}

        _ ->
          fewest_coin_set = Enum.min_by(change_candidates, &length/1)
          {:ok, fewest_coin_set}
      end
    end
  end

  defp generate_useable_coins(coins, target) do
    coins
    |> Enum.filter(&(&1 <= target))
    |> Enum.sort(&(&1 >= &2))
  end

  defp generate_change_candidates(coins, target) do
    coins
    |> Enum.reduce({coins, [], []}, &generate_change(coins, target, &1, &2))
  end

  defp generate_change(coins, target, coin, {change_coins, candidates, acc}) do
    combination = [coin | acc]
    sum = Enum.sum(combination)

    cond do
      sum > target ->
        case change_coins do
          [] ->
            handle_possible_change_without_unit_coins(coins, candidates, acc)

          [head | []] ->
            generate_change(coins, target, head, {[], candidates, acc})

          [_head | tail] ->
            generate_change(coins, target, hd(tail), {tail, candidates, acc})
        end

      sum == target ->
        change_coins =
          if Enum.empty?(change_coins) do
            []
          else
            tl(change_coins)
          end

        {change_coins, [combination | candidates], []}

      # sum < target
      true ->
        generate_change(
          coins,
          target,
          coin,
          {change_coins, candidates, combination}
        )
    end
  end

  defp handle_possible_change_without_unit_coins(coins, candidates, acc) do
    case length(candidates) do
      0 ->
        {coins, candidates, Enum.drop(acc, 1)}

      _ ->
        {[], candidates, acc}
    end
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?