Task — Making change

Compute the number of ways to make change of the given amount of cents. By using the coins Penny, Nickel, Dime, Quarter and Half-dollar, in how many distinct ways can the total value be equal to the given amount? The order of coin selection does not matter.

• A penny (P) is equal to 1 cent.
• A nickel (N) is equal to 5 cents.
• A dime (D) is equal to 10 cents.
• A quarter (Q) is equal to 25 cents.
• A half-dollar (H) is equal to 50 cents.

Examples

Example 1
Input: $amount = 9
Output: 2
1: 9P
2: N + 4P

Example 2
Input: $amount = 15
Output: 6
1: D + 5P
2: D + N
3: 3N
4: 2N + 5P
5: N + 10P
6: 15P

Example 3
Input: $amount = 100
Output: 292

Analysis

I tried various ways of doing this, and concluded, probably wrongly, that a restricted enumeration of all plausible combinations was the way to go. It gets the correct answer 292 for 100 cents in milliseconds, and 500 cents takes only a few seconds to come up with an answer of 59 576.

My method uses 5 nested loops over the 5 possible coins. That may seem inefficient, but it will be faster than doing this using recursion, which is quite slow in Perl. It is possible that there is a more analytic solution, but if so, my aging brain failed to find it.

Each of my loops starts with 0 of a coin type and adds additional coins of the same type until the value of the sum plus that of any of the enclosing loops equals or exceeds the given total. If the innermost loop finds equality, we have a solution. Note that the upper bound of the loop is set to 1e6 - each loop is guaranteed to hit its last statement. Perhaps a while would have been better.

So, for example, for an input of 100 cents my solution first finds 100 pennies and then successively adds nickels, dimes and quarters to the solution, ending up with 2 half-dollars.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2024-09-02
use utf8;     # Week 285 - task 2 - Making change
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';

making_change(9);
making_change(15);
making_change(100);
making_change(500);

sub making_change {
    
    my ($cents, $h, $q, $d, $n, $p, @sum, $count, $explain);
    
    # initialise
    $cents = $_[0];
    $count = 0;
    $explain = '';
    
    # intelligently loop over all combs
    H: for $h (0 .. 1e6) {
        $sum[0] = $h * 50;
        last H if $sum[0] > $cents;

        Q: for $q (0 .. 1e6) {
            $sum[1] = $sum[0] + $q * 25;
            last Q if $sum[1] > $cents;

            D: for $d (0 .. 1e6) {
                $sum[2] = $sum[1] + $d * 10;
                last D if $sum[2] > $cents;

                N: for $n (0 .. 1e6) {
                    $sum[3] = $sum[2] + $n * 5;
                    last N if $sum[3] > $cents;

                    P: for $p (0 .. 1e6) {
                        $sum[4] = $sum[3] + $p;
                        
                        # found a valid combination
                        if ($sum[4] == $cents) {
                            $count ++;
                            $explain .= qq[  $count: ${h}H + ${q}Q + ${d}D + ${n}N + ${p}P\n];
                        }
                        last P if $sum[4] >= $cents;
                    }
                }
            }
        }
    }
    
    # output
    say qq[\nInput:  \$cents = $cents];
    $explain = qq[\n] if $count > 300;
    $explain =~ s| \+ 0.||gm;
    $explain =~ s|0H \+ ||gm;
    print qq[Output: $count\n$explain]; 
}

Output

Input:  $cents = 9
Output: 2
  1: 9P
  2: 1N + 4P

Input:  $cents = 15
Output: 6
  1: 15P
  2: 1N + 10P
  3: 2N + 5P
  4: 3N
  5: 1D + 5P
  6: 1D + 1N

Input:  $cents = 100
Output: 292
  1: 100P
  2: 1N + 95P
  3: 2N + 90P
  4: 3N + 85P
  5: 4N + 80P
  6: 5N + 75P
  7: 6N + 70P
  8: 7N + 65P
  9: 8N + 60P
  10: 9N + 55P
  11: 10N + 50P
  12: 11N + 45P
  13: 12N + 40P
  14: 13N + 35P
  15: 14N + 30P
  16: 15N + 25P
  17: 16N + 20P
  18: 17N + 15P
  19: 18N + 10P
  20: 19N + 5P
  21: 20N
  22: 1D + 90P
  23: 1D + 1N + 85P
  24: 1D + 2N + 80P
  25: 1D + 3N + 75P
  26: 1D + 4N + 70P
  27: 1D + 5N + 65P
  28: 1D + 6N + 60P
  29: 1D + 7N + 55P
  30: 1D + 8N + 50P
  31: 1D + 9N + 45P
  32: 1D + 10N + 40P
  33: 1D + 11N + 35P
  34: 1D + 12N + 30P
  35: 1D + 13N + 25P
  36: 1D + 14N + 20P
  37: 1D + 15N + 15P
  38: 1D + 16N + 10P
  39: 1D + 17N + 5P
  40: 1D + 18N
  41: 2D + 80P
  42: 2D + 1N + 75P
  43: 2D + 2N + 70P
  44: 2D + 3N + 65P
  45: 2D + 4N + 60P
  46: 2D + 5N + 55P
  47: 2D + 6N + 50P
  48: 2D + 7N + 45P
  49: 2D + 8N + 40P
  50: 2D + 9N + 35P
  51: 2D + 10N + 30P
  52: 2D + 11N + 25P
  53: 2D + 12N + 20P
  54: 2D + 13N + 15P
  55: 2D + 14N + 10P
  56: 2D + 15N + 5P
  57: 2D + 16N
  58: 3D + 70P
  59: 3D + 1N + 65P
  60: 3D + 2N + 60P
  61: 3D + 3N + 55P
  62: 3D + 4N + 50P
  63: 3D + 5N + 45P
  64: 3D + 6N + 40P
  65: 3D + 7N + 35P
  66: 3D + 8N + 30P
  67: 3D + 9N + 25P
  68: 3D + 10N + 20P
  69: 3D + 11N + 15P
  70: 3D + 12N + 10P
  71: 3D + 13N + 5P
  72: 3D + 14N
  73: 4D + 60P
  74: 4D + 1N + 55P
  75: 4D + 2N + 50P
  76: 4D + 3N + 45P
  77: 4D + 4N + 40P
  78: 4D + 5N + 35P
  79: 4D + 6N + 30P
  80: 4D + 7N + 25P
  81: 4D + 8N + 20P
  82: 4D + 9N + 15P
  83: 4D + 10N + 10P
  84: 4D + 11N + 5P
  85: 4D + 12N
  86: 5D + 50P
  87: 5D + 1N + 45P
  88: 5D + 2N + 40P
  89: 5D + 3N + 35P
  90: 5D + 4N + 30P
  91: 5D + 5N + 25P
  92: 5D + 6N + 20P
  93: 5D + 7N + 15P
  94: 5D + 8N + 10P
  95: 5D + 9N + 5P
  96: 5D + 10N
  97: 6D + 40P
  98: 6D + 1N + 35P
  99: 6D + 2N + 30P
  100: 6D + 3N + 25P
  101: 6D + 4N + 20P
  102: 6D + 5N + 15P
  103: 6D + 6N + 10P
  104: 6D + 7N + 5P
  105: 6D + 8N
  106: 7D + 30P
  107: 7D + 1N + 25P
  108: 7D + 2N + 20P
  109: 7D + 3N + 15P
  110: 7D + 4N + 10P
  111: 7D + 5N + 5P
  112: 7D + 6N
  113: 8D + 20P
  114: 8D + 1N + 15P
  115: 8D + 2N + 10P
  116: 8D + 3N + 5P
  117: 8D + 4N
  118: 9D + 10P
  119: 9D + 1N + 5P
  120: 9D + 2N
  121: 10D
  122: 1Q + 75P
  123: 1Q + 1N + 70P
  124: 1Q + 2N + 65P
  125: 1Q + 3N + 60P
  126: 1Q + 4N + 55P
  127: 1Q + 5N + 50P
  128: 1Q + 6N + 45P
  129: 1Q + 7N + 40P
  130: 1Q + 8N + 35P
  131: 1Q + 9N + 30P
  132: 1Q + 10N + 25P
  133: 1Q + 11N + 20P
  134: 1Q + 12N + 15P
  135: 1Q + 13N + 10P
  136: 1Q + 14N + 5P
  137: 1Q + 15N
  138: 1Q + 1D + 65P
  139: 1Q + 1D + 1N + 60P
  140: 1Q + 1D + 2N + 55P
  141: 1Q + 1D + 3N + 50P
  142: 1Q + 1D + 4N + 45P
  143: 1Q + 1D + 5N + 40P
  144: 1Q + 1D + 6N + 35P
  145: 1Q + 1D + 7N + 30P
  146: 1Q + 1D + 8N + 25P
  147: 1Q + 1D + 9N + 20P
  148: 1Q + 1D + 10N + 15P
  149: 1Q + 1D + 11N + 10P
  150: 1Q + 1D + 12N + 5P
  151: 1Q + 1D + 13N
  152: 1Q + 2D + 55P
  153: 1Q + 2D + 1N + 50P
  154: 1Q + 2D + 2N + 45P
  155: 1Q + 2D + 3N + 40P
  156: 1Q + 2D + 4N + 35P
  157: 1Q + 2D + 5N + 30P
  158: 1Q + 2D + 6N + 25P
  159: 1Q + 2D + 7N + 20P
  160: 1Q + 2D + 8N + 15P
  161: 1Q + 2D + 9N + 10P
  162: 1Q + 2D + 10N + 5P
  163: 1Q + 2D + 11N
  164: 1Q + 3D + 45P
  165: 1Q + 3D + 1N + 40P
  166: 1Q + 3D + 2N + 35P
  167: 1Q + 3D + 3N + 30P
  168: 1Q + 3D + 4N + 25P
  169: 1Q + 3D + 5N + 20P
  170: 1Q + 3D + 6N + 15P
  171: 1Q + 3D + 7N + 10P
  172: 1Q + 3D + 8N + 5P
  173: 1Q + 3D + 9N
  174: 1Q + 4D + 35P
  175: 1Q + 4D + 1N + 30P
  176: 1Q + 4D + 2N + 25P
  177: 1Q + 4D + 3N + 20P
  178: 1Q + 4D + 4N + 15P
  179: 1Q + 4D + 5N + 10P
  180: 1Q + 4D + 6N + 5P
  181: 1Q + 4D + 7N
  182: 1Q + 5D + 25P
  183: 1Q + 5D + 1N + 20P
  184: 1Q + 5D + 2N + 15P
  185: 1Q + 5D + 3N + 10P
  186: 1Q + 5D + 4N + 5P
  187: 1Q + 5D + 5N
  188: 1Q + 6D + 15P
  189: 1Q + 6D + 1N + 10P
  190: 1Q + 6D + 2N + 5P
  191: 1Q + 6D + 3N
  192: 1Q + 7D + 5P
  193: 1Q + 7D + 1N
  194: 2Q + 50P
  195: 2Q + 1N + 45P
  196: 2Q + 2N + 40P
  197: 2Q + 3N + 35P
  198: 2Q + 4N + 30P
  199: 2Q + 5N + 25P
  200: 2Q + 6N + 20P
  201: 2Q + 7N + 15P
  202: 2Q + 8N + 10P
  203: 2Q + 9N + 5P
  204: 2Q + 10N
  205: 2Q + 1D + 40P
  206: 2Q + 1D + 1N + 35P
  207: 2Q + 1D + 2N + 30P
  208: 2Q + 1D + 3N + 25P
  209: 2Q + 1D + 4N + 20P
  210: 2Q + 1D + 5N + 15P
  211: 2Q + 1D + 6N + 10P
  212: 2Q + 1D + 7N + 5P
  213: 2Q + 1D + 8N
  214: 2Q + 2D + 30P
  215: 2Q + 2D + 1N + 25P
  216: 2Q + 2D + 2N + 20P
  217: 2Q + 2D + 3N + 15P
  218: 2Q + 2D + 4N + 10P
  219: 2Q + 2D + 5N + 5P
  220: 2Q + 2D + 6N
  221: 2Q + 3D + 20P
  222: 2Q + 3D + 1N + 15P
  223: 2Q + 3D + 2N + 10P
  224: 2Q + 3D + 3N + 5P
  225: 2Q + 3D + 4N
  226: 2Q + 4D + 10P
  227: 2Q + 4D + 1N + 5P
  228: 2Q + 4D + 2N
  229: 2Q + 5D
  230: 3Q + 25P
  231: 3Q + 1N + 20P
  232: 3Q + 2N + 15P
  233: 3Q + 3N + 10P
  234: 3Q + 4N + 5P
  235: 3Q + 5N
  236: 3Q + 1D + 15P
  237: 3Q + 1D + 1N + 10P
  238: 3Q + 1D + 2N + 5P
  239: 3Q + 1D + 3N
  240: 3Q + 2D + 5P
  241: 3Q + 2D + 1N
  242: 4Q
  243: 1H + 50P
  244: 1H + 1N + 45P
  245: 1H + 2N + 40P
  246: 1H + 3N + 35P
  247: 1H + 4N + 30P
  248: 1H + 5N + 25P
  249: 1H + 6N + 20P
  250: 1H + 7N + 15P
  251: 1H + 8N + 10P
  252: 1H + 9N + 5P
  253: 1H + 10N
  254: 1H + 1D + 40P
  255: 1H + 1D + 1N + 35P
  256: 1H + 1D + 2N + 30P
  257: 1H + 1D + 3N + 25P
  258: 1H + 1D + 4N + 20P
  259: 1H + 1D + 5N + 15P
  260: 1H + 1D + 6N + 10P
  261: 1H + 1D + 7N + 5P
  262: 1H + 1D + 8N
  263: 1H + 2D + 30P
  264: 1H + 2D + 1N + 25P
  265: 1H + 2D + 2N + 20P
  266: 1H + 2D + 3N + 15P
  267: 1H + 2D + 4N + 10P
  268: 1H + 2D + 5N + 5P
  269: 1H + 2D + 6N
  270: 1H + 3D + 20P
  271: 1H + 3D + 1N + 15P
  272: 1H + 3D + 2N + 10P
  273: 1H + 3D + 3N + 5P
  274: 1H + 3D + 4N
  275: 1H + 4D + 10P
  276: 1H + 4D + 1N + 5P
  277: 1H + 4D + 2N
  278: 1H + 5D
  279: 1H + 1Q + 25P
  280: 1H + 1Q + 1N + 20P
  281: 1H + 1Q + 2N + 15P
  282: 1H + 1Q + 3N + 10P
  283: 1H + 1Q + 4N + 5P
  284: 1H + 1Q + 5N
  285: 1H + 1Q + 1D + 15P
  286: 1H + 1Q + 1D + 1N + 10P
  287: 1H + 1Q + 1D + 2N + 5P
  288: 1H + 1Q + 1D + 3N
  289: 1H + 1Q + 2D + 5P
  290: 1H + 1Q + 2D + 1N
  291: 1H + 2Q
  292: 2H

Input:  $cents = 500
Output: 59576