3
\$\begingroup\$

Background and objective of the code

Based on this Dev.to challenge, I wrote the Python code below (TIO link also available).

The task was to return the least number of coins in a given denomination to from a specified amount of money. I generalised this into a function that gives all possible combinations of coins that form a specified amount of money. From that, it was easy to write a oneliner function that does exactly that.

Review questions and review scope

I'm happy with the code that I wrote, and I'd really like some feedback to improve my (amateur) Python coding skills and style.

I'm interested in a general review of the code and functions that I've written: style, clarity, documentation, etc. I'm not specifically interested if there is an other/better way to give the answer to the challenge (although of course, also this feedback is welcome!).

Specific review questions that I can think of:

  • is the split_in_denominations() function too long (too many lines)? If so: any suggestions to split it?
  • Am I nesting too deep?
  • Any comments/suggestions on the way I use a Numpy ndarray to store the intermediate results as a list of dicts?
  • Although not the main (pun!) focus of my review question: is there a "better" way to show the test cases in main()? I'm aware of Python's unittest module, but that adds a considerable amount of boilerplate code...

Here is my code:

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()

\$\endgroup\$
  • 3
    \$\begingroup\$ I'm not interested if there is an other/better way to give the answer to the challenge - Fine; but you might get an opinion on this anyway. Any insightful review is on-topic here. \$\endgroup\$ – Reinderien Jul 15 '20 at 2:28
  • \$\begingroup\$ @Reinderien: thank you for commenting. That sentence indeed reads more harsh than I intended. I rephrased it to a more friendly tone of voice and more welcoming to broader feedback. \$\endgroup\$ – agtoever Jul 15 '20 at 10:53
  • \$\begingroup\$ Is the table in the first comment correct? I wonder why the resulting array would contain a (zero) number of coin 2 (e.g. [{1:3,2:0}] for the amount of 3 in the first row) if the input says nothing about a coin 2 (the list of available coins is [1])... \$\endgroup\$ – CiaPan Jul 15 '20 at 11:10
  • \$\begingroup\$ Something is also wrong in the example result: {1: 3, 5: 0, 10: 1, 25: 0} is certainly NOT # 3 coins...\ \$\endgroup\$ – CiaPan Jul 15 '20 at 11:12
  • \$\begingroup\$ @CiaPan: Thanks for your comments! The first row only uses one denomination: [1]. The second row adds the second denominations. Hence, for the amount of 3, {1: 3, 2:0} is a valid (and only) answer, using only denomination [1]. Note that this table is used as an intermediate result for implementing the dynamic programming solution. The final result is in the last column of the bottom row. That's what the function is working towards. As for the number of coins in the example: you are completely correct. That comment should be 4 coins instead of 3 coins... \$\endgroup\$ – agtoever Jul 15 '20 at 11:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.