Probably overkill but it works and is pretty fast for big numbers with British coins

1 files changed, 31 insertions, 0 deletions

diff --git a/challenge-075/simon-proctor/raku/ch-1.raku b/challenge-075/simon-proctor/raku/ch-1.raku
new file mode 100644
index 0000000000..32c4e8d699
--- /dev/null
+++ b/challenge-075/simon-proctor/raku/ch-1.raku
@@ -0,0 +1,31 @@
+#!/usr/bin/env raku
+
+use v6;
+
+#| Given an amount and a list of valid coins show all the combinations of change
+sub MAIN (
+    UInt $amount where * > 0, #= Amount to make change of
+    *@coins where { .all ~~ Int && .all > 0 }, #= Valid coins
+) {
+    .join(", ").say for make-change( $amount, @coins );
+}
+
+my %change_cache;
+
+multi sub make-change( 0, @coins ) {
+    return [[],]
+}
+
+multi sub make-change( $amount, @coins ) {
+    with %change_cache{$amount} { return |%change_cache{$amount} }
+    my @result = [];
+    for @coins.grep( * <= $amount ) -> $coin {
+        my @list = make-change( $amount - $coin, @coins.grep( * <= $amount ) );
+        for @list -> @change {
+            @result.push( [$coin, |@change] );
+        }        
+    }
+    @result = @result.map( { $_.sort.Array } ).unique( with => &[~~] );
+    %change_cache{$amount} = @result;
+    return @result;
+}