 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 = 
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