Daily Challenge #262 - No One Likes Spare Change

const coins1 = [1, 5, 10, 25];
const coins2 = [1, 2, 5, 10, 20, 50];
const coins3 = [1, 5, 20, 25];
const coins4 = [2, 9, 5, 1];

const getChangeAsCoins = (coins, amount) => {
  coins = coins.sort((a, b) => a - b);
  let remaining = amount,
      index = coins.length - 1,
      change = {};

  while(remaining !== 0 || index !== -1) {
    numOfCoins = Math.floor(remaining / coins[index])
    change[coins[index]] = numOfCoins;
    remaining = remaining % coins[index];
    index--;
  }

  console.log(change);
}

getChangeAsCoins(coins1, 123);
/*
  {
    1: 3,
    5: 0,
    10: 2,
    25: 4
  }
*/
getChangeAsCoins(coins2, 123);
/*
  {
    1: 1,
    2: 1,
    5: 0,
    10: 0,
    20: 1,
    50: 2
  }
*/
getChangeAsCoins(coins1, 75);
/*
  {
    1: 0,
    5: 0,
    10: 0,
    25: 3
  }
*/
getChangeAsCoins(coins2, 75);
/*
  {
    1: 0,
    2: 0,
    5: 1,
    10: 0,
    20: 1,
    50: 1
  }
*/
getChangeAsCoins(coins3, 40);
/*
  {
    1: 0,
    5: 3,
    20: 0,
    25: 1
  }
*/
getChangeAsCoins(coins4, 53);
/*
  {
    1: 1,
    2: 1,
    5: 1,
    9: 5
  }
*/

from typing import List, Dict
import numpy


def split_in_denominations(amount: int,
                           denominations: List[int]) -> List[Dict[int, int]]:
    """ Gives all distinct ways to express amount in items from denominations

    The algorithm used is to find all solutions for each smaller amount and
    each smaller list of (sorted) denominations. For example, for the amount
    of 3 and denominations [1, 2], the following Numpy array is created:

             Amount:  |     0     |     1     |     2     |     3     |
    Denominations:    +-----------+-----------+-----------+-----------+
                  [1] |[{1:0,2:0}]|[{1:1,2:0}]|[{1:2,2:0}]|[{1:3,2:0}]|
                [1,2] |[{1:0,2:0}]|[{1:1,2:0}]|[{1:2,2:0},|[{1:3,2:0},|
                      |           |           | {1:0,2:1}]| {1:1,2:1}]|
                      +-----------+-----------+-----------+-----------+

    This result array is built row by row from the top left to the bottom
    right. For each cell, only two (disjunct!) solution sets have to be
    considered: the one directly above (not using the current denomination)
    and the one 1 of the denomination value to the left. For that latter set,
    you just need to count one extra of denomination.

    Arguments:
        amount: integer value that has to be expressed in denominations
        denominations: list of values

    Returns:
        List with all unique dicts with denomination as key and the count
        of that denomination as value. The list is sorted by the sum of
        the count of all denominations (the least number of coins)

    Raises:
        ValueError is the amount can't be expressed by denominations

    Examples:
        >>> split_in_denominations(13, [1, 5, 10, 25])
        [{1: 3, 5: 0, 10: 1, 25: 0},   # 3 coins
         {1: 3, 5: 2, 10: 0, 25: 0},   # 5 coins
         {1: 8, 5: 1, 10: 0, 25: 0},   # 9 coins
         {1: 13, 5: 0, 10: 0, 25: 0}]  # 13 coins
    """

    # Template solution: an empty dict with count 0 of each denominations
    zero_denom = {d: 0 for d in denominations}

    # Edge case: amount == 0
    if amount == 0:
        return [zero_denom]

    # result array with all intermediate solutions
    result = numpy.ndarray((amount + 1, len(denominations)), dtype=list)

    # Loop over the sorted denominations
    for denom_idx, denom in enumerate(sorted(denominations)):
        for amount_idx in range(amount + 1):
            # In the first iteration of denom, fill the first row of result
            if denom_idx == 0:
                # Start with a copy of the template solution
                result[amount_idx, 0] = [dict(zero_denom)]

                # If amount is divisible by denom, add that solution
                if amount_idx % denom == 0:
                    result[amount_idx, 0][0][denom] = amount_idx // denom

            # Now add the other denominations one by one in each loop
            else:
                # Copy the results from the previous denomination list
                result[amount_idx, denom_idx] = list(result[amount_idx,
                                                            denom_idx - 1])

                # Extend the result with the solutions from
                # amount_idx minus denom, with 1 extra count of denom
                if amount_idx >= denom:
                    for solution in result[amount_idx - denom, denom_idx]:
                        new_solution = dict(solution)
                        new_solution[denom] += 1
                        result[amount_idx, denom_idx].append(new_solution)

    # Check if there is a result (result does not only contain the template)
    if result[amount, len(denominations) - 1] == [zero_denom]:
        raise ValueError(f"{amount} can't be expressed in {denominations}")

    return sorted(result[amount, len(denominations) - 1],
                  key=lambda s: sum(s.values()))


def least_num_denominations(amount: float,
                            denominations: List[float]) -> int:
    """ Gives the least number of denominations that is needed to sum to amount

    Arguments:
        amount: numeric value that has to be expressed in denominations
        denominations: list of values

    Returns:
        The least number of denominations.
        Returns None of there is no possible split into denominations.

    Examples:
        >>> least_num_denominations(4, [1, 2, 3])  # (2, 2) or (1, 3)
        2
    """
    return sum(split_in_denominations(amount, denominations)[0].values())


def main():
    denominations = {'coins1': [1, 5, 10, 25],
                     'coins2': [1, 2, 5, 10, 20, 50],
                     'coins3': [1, 5, 20, 25],
                     }

    cases = [('coins1', 13),  # 123),
             ('coins2', 13),  # 123),
             ('coins1', 75),
             ('coins2', 75),
             ('coins3', 40),
             ]

    for den_name, amount in cases:
        d = denominations[den_name]
        print(f'Least split of {amount} in {d} is: ' +
              f'{least_num_denominations(amount, d)} (there are ' +
              f'{len(split_in_denominations(amount, d))} ways to split)')


if __name__ == '__main__':
    main()

import Data.List (sort)


minimumChange :: [Int] -> Int -> Int
minimumChange coins amount =
    minimumChange' (reverse $ sort coins) amount

    where
        minimumChange' :: [Int] -> Int -> Int
        minimumChange' [] _                  = 0
        minimumChange' _ 0                   = 0
        minimumChange' (coin : coins) amount =
            (div amount coin)
                + minimumChange' coins (mod amount coin)

function GreedyCoinCounterFactory(denominations){
  denominations.sort((x, y) => y-x);
  return (amount) => {
    return denominations.reduce((acc, curr) => {
      acc += Math.floor(amount / curr);
      amount %= curr;
      return acc;
    }, 0);
  }
}

let coins1 = GreedyCoinCounterFactory([1,5,10,25]);
let coins2 = GreedyCoinCounterFactory([1,2,5,10,20,50]);
let coins3 = GreedyCoinCounterFactory([1,5,20,25]);

console.log(coins1(123)); // 9
console.log(coins2(123)); // 5
console.log(coins1(75));  // 3
console.log(coins2(75));  // 3
console.log(coins3(40));  // 4

function DynamicCoinCounterFactory(denominations) {
  return (amount) => {
    let counts = [];
    counts.push(0);

    for(let i = counts.length; i <= amount; i++) {
      let min = amount;
      for(let j = 0; j < denominations.length; j++) {
        if (i >= denominations[j]) {
          min = Math.min(min, counts[i-denominations[j]]+1)
        }
      }
      counts.push(min);
    }
    return counts[counts.length-1];
  }
}

let coins1 = DynamicCoinCounterFactory([1,5,10,25]);
let coins2 = DynamicCoinCounterFactory([1,2,5,10,20,50]);
let coins3 = DynamicCoinCounterFactory([1,5,20,25]);

console.log(coins1(123)); // 9
console.log(coins2(123)); // 5
console.log(coins1(75));  // 3
console.log(coins2(75));  // 3
console.log(coins3(40));  // 2