Avatar of shmibs

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
  Code.load_file("change.exs", __DIR__)
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 = [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
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

Community comments

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

not particularly efficient, though, so should rewrite properly

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?