 # shmibs's solution

## to Change in the Elixir Track

Published at Jul 13 2018 · 1 comment
Instructions
Test suite
Solution

#### Note:

This solution was written on an old version of Exercism. The tests below might not correspond to the solution code, and the exercise may have changed since this code was written.

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:

``````\$ elixir change_test.exs
``````

### 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
``````

For more detailed information about the Elixir track, please see the help page.

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

``````if !System.get_env("EXERCISM_TEST_EXAMPLES") do
end

ExUnit.start()
ExUnit.configure(exclude: :pending, trace: true)

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``````
``````defmodule Change do
@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 if it is not possible to compute the right amount of coins.
Otherwise returns the tuple {:ok, map_of_coins}

## Examples

iex> Change.generate(3, [5, 10, 15])
:error

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

"""

@spec generate(integer, list) :: {:ok, map} | :error
def generate(amount, values) do
generate_sub amount, Enum.sort(values, &(&1 > &2) ), %{}
end
defp generate_sub(amount, _, _) when amount < 0, do: :error
defp generate_sub(_, [], _), do: :error
defp generate_sub(amount, [vh|vt], zeroed) do
{remain, m} = Enum.reduce([vh|vt], {amount, %{}}, &coin_count/2)
cond do
remain != 0 -> generate_sub amount, vt, Map.merge(%{vh => 0}, zeroed)
true -> {:ok, Map.merge(zeroed, m)}
end
end

defp coin_count(csize, {left, m}) when csize > left do
{left, Map.put(m, csize, 0)}
end
defp coin_count(csize, {left, m}) do
{c, s} = Stream.iterate({1, csize}, fn {c, s} -> {c+1, s+csize} end)
|> Stream.take_while( fn {_,s} -> left - s >= 0 end )
|> Enum.at(-1)
{ left - s, Map.put(m, csize, c) }
end
end`````` Solution Author