Merge pull request #2261 from holli-holzer/master

#1 initial

1 files changed, 49 insertions, 0 deletions

diff --git a/challenge-077/markus-holzer/raku/ch-1.raku b/challenge-077/markus-holzer/raku/ch-1.raku
new file mode 100644
index 0000000000..7337c6ca01
--- /dev/null
+++ b/challenge-077/markus-holzer/raku/ch-1.raku
@@ -0,0 +1,49 @@
+#
+# D:\Projekte\Perl6\perlweeklychallenge-club\challenge-077\markus-holzer\raku>raku ch-1.raku 123456789
+# Number of combinations: 3230
+# Calculated in 8.736 seconds
+#
+# Let me know if yours is faster
+# See https://encyclopediaofmath.org/wiki/Zeckendorf_representation
+#
+
+use experimental :cached;
+
+unit sub MAIN( Int $N where * > 0, Bool :$v = False );
+
+my $start = now;
+
+with my @combinations = gather combine zeckendorf $N
+{
+    say @combinations.map( *.join( "," ) ).join( "\n" ) if $v;
+    say "Number of combinations: {+@combinations}";
+    say "Calculated in { sprintf "%.3f", now - $start } seconds"
+}
+
+sub combine( @Z ) is cached
+{
+    my &valid  = -> $result {
+        $result.elems == $result.unique.elems && $result !~~ @Z }
+
+    my &insert = -> $where, $what {
+        my @x = @Z.clone; @x.splice( $where, 1, |$what ); @x }
+
+    take @Z and sink @Z
+        .map( &zeckendorf )
+        .kv.map( &insert )
+        .grep( &valid )
+        .map( &combine )
+}
+
+sub zeckendorf( $n is copy ) is cached
+{
+    state @fib = [1, 1, * + * ... * > $N];
+
+    my &do-zeckendorf = {
+        eager gather for @fib.grep( * < $n ).reverse {
+            if $_ <= $n {
+                take $_;
+                $n -= $_ }}}
+
+    $n == 1 ?? 1.List !! do-zeckendorf
+}
\ No newline at end of file