change.ex

defmodule Change do
  # A intuição para resolver este problema é entender que
  # quando você vai fazer troco para um valor, dado um certo
  # conjunto de moedas, você tem duas escolhas:
  #
  # 1. Você pode usar a moeda de maior valor que você tem
  # 2. Você pode fazer troco sem usar essa moeda.
  #
  # Se você escolher a opção 1, você está implicitamente dizendo
  # que você vai usar pelo menos 1 moeda daquele tipo.
  #
  # Portanto, o problema de "fazer troco para X centavos, usando moedas
  # onde o maior valor é M" pode ser reduzido aos problemas:
  #
  # 1. Fazer troco para X - M centavos, usando todas as moedas que tenho
  #    (i.e. usar pelo menos uma moeda da maior denominação)
  # 2. Fazer troco para X centavos, sem usar a moeda de maior denominação
  #
  # Isso sugere uma solução recursiva - mas o problema é que, como o
  # nosso problema faz 2 chamadas recursivas a cada nível, isso
  # precisaria de O(2^N) chamadas recursivas, uma quantia que cresce muito
  # rápido e faria com que casos grandes fossem inviáveis.
  #
  # Todavia, há uma propriedade que podemos explorar - ao seguir
  # essa estratégia, vários casos aparecerão repetidamente. A gente irá
  # precisar consultar o valor para os mesmos pares {valor, denominação mais alta}
  # várias vezes. Daí podemos usar o clássico truque de programação dinâmica
  # para problemas com essas características, que consiste em indexar
  # em uma estrutura chave-valor (um mapa em Elixir) os valores
  # que serão consultados repetidamente para que possam ser consultados.
  #
  # Assim, reduzimos a quantidade de chamadas que precisam ser feitas de
  # O(2^N) para O(N*M), onde N é o valor alvo e M o número de moedas.
  #
  # Em geral, se vê mais programação dinâmica em linguagens imperativas,
  # mas abaixo demonstramos uma técnica possível em código funcional,
  # onde usamos o clássico truque de receber o estado como argumento
  # nas funções que precisam ter estado e retornar o estado atualizado
  # juntamente ao resultado.

  def count_ways(value, coins) do
    sorted_coins = Enum.sort(coins, :desc)
    # Quando a quantia for 0, sempre há uma solução
    # independentemente de qual seja a maior denominação ainda disponível
    solution_map = Map.new(coins, fn coin -> {{0, coin}, 1} end)
    {ways, _final_state} = dynamic_count_ways(value, sorted_coins, solution_map)

    ways
  end

  # Se não temos mais moedas, mas o valor é 0, há uma solução (não usar nenhuma moeda)
  def dynamic_count_ways(0, [], solution_map) do
    {1, solution_map}
  end

  # Se o valor não é 0 e acabaram as moedas, não há soluções para esse caso
  def dynamic_count_ways(_amount, [], solution_map) do
    {0, solution_map}
  end

  # Se o valor é menor do que a maior denominação, só podemos resolver sem usar
  # essa denominação
  def dynamic_count_ways(value, [coin | others], solution_map) when value < coin do
    dynamic_count_ways(value, others, solution_map)
  end

  # Em todos os outros casos, seguimos a lógica assinalada acima, mas incluindo
  # a lógica de atualizar e retornar o mapa de resultados intermediários
  def dynamic_count_ways(value, [coin | others] = coins, solution_map) do    
    case solution_map[{value, coin}] do
      nil ->
        {ways_with_coin, solution_map} = dynamic_count_ways(value - coin, coins, solution_map)
        {ways_without_coin, solution_map} = dynamic_count_ways(value, others, solution_map)
        total_ways = ways_with_coin + ways_without_coin

        {total_ways, Map.put(solution_map, {value, coin}, total_ways)}

      solution ->
        {solution, solution_map}
    end
  end
end