From 25f0d1da2eb93ba4ba6df4b0f615fa0c8145b7c7 Mon Sep 17 00:00:00 2001 From: Simon Proctor Date: Tue, 25 Aug 2020 11:13:00 +0100 Subject: Probably overkill but it works and is pretty fast for big numbers with British coins --- challenge-075/simon-proctor/raku/ch-1.raku | 31 ++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+) create mode 100644 challenge-075/simon-proctor/raku/ch-1.raku (limited to 'challenge-075') 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; +} -- cgit