From 69d2d13fcf0bd1b6547dee9c3c621d36395ea129 Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Tue, 15 Sep 2020 17:22:48 +0200
Subject: Perl solution for Week 77.

---
 challenge-077/abigail/Part1/solution.pl | 63 +++++++++++++++++++++++++++++++++
 1 file changed, 63 insertions(+)
 create mode 100644 challenge-077/abigail/Part1/solution.pl

(limited to 'challenge-077/abigail/Part1/solution.pl')

diff --git a/challenge-077/abigail/Part1/solution.pl b/challenge-077/abigail/Part1/solution.pl
new file mode 100644
index 0000000000..5e6856b6d8
--- /dev/null
+++ b/challenge-077/abigail/Part1/solution.pl
@@ -0,0 +1,63 @@
+#!/opt/perl/bin/perl
+
+#
+# Exercise:
+#     You are given a positive integer $N.
+#     Write a script to find out all possible combination of Fibonacci
+#     Numbers required to get $N on addition.
+#
+#     You are NOT allowed to repeat a number. Print 0 if none found.
+#
+
+#
+# Note:
+#    The "Print 0 if none found." is irrelevant. There is always at
+#    least one way to write any positive integer as a sum of distinct
+#    Fibonacci Numbers. (Zeckendorf's theorem states: "very positive
+#    integer can be represented uniquely as the sum of one or more
+#    distinct Fibonacci numbers in such a way that the sum does not
+#    include any two consecutive Fibonacci numbers")
+#
+
+use 5.032;
+
+use strict;
+use warnings;
+no  warnings 'syntax';
+
+use experimental 'signatures';
+use experimental 'lexical_subs';
+
+chomp (my $N = <>);
+
+#
+# Create a list of Fibonacci Numbers up to $N. We will start with (1, 2),
+# skipping the first two numbers 0 and 1. 0 doesn't add anything, and
+# we cannot duplicate numbers, so we just need one 1.
+#
+my @FIB = (1, 2);
+while ($FIB [-1] + $FIB [-2] < $N) {
+    push @FIB => $FIB [-1] + $FIB [-2];
+}
+
+sub solutions;
+
+#
+# Create all solutions for number $target, with all Fibonnaci numbers
+# having index $index or above.
+#
+sub solutions ($target, $index = 0) {
+    map {
+        my $fib = $FIB [$_];
+        $target  < $fib ? ()
+      : $target == $fib ? [$target]
+      : map {[$fib, @$_]} solutions ($target - $fib, $_ + 1)
+    } $index .. @FIB - 1;
+}
+
+my @all = solutions $N;
+
+local $" = " + ";
+say "@$_ = $N" for @all;
+
+__END__
-- 
cgit 


From d36cbe639e0dffeb2fd168576ea19570c9fb687d Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Tue, 15 Sep 2020 19:50:36 +0200
Subject: Fix off-by-one error.

We need all the Fibonacci numbers up to and including $N, else we will
miss out on a solution if $N is a Fibonacci number.
---
 challenge-077/abigail/Part1/solution.pl | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'challenge-077/abigail/Part1/solution.pl')

diff --git a/challenge-077/abigail/Part1/solution.pl b/challenge-077/abigail/Part1/solution.pl
index 5e6856b6d8..b39028c5b9 100644
--- a/challenge-077/abigail/Part1/solution.pl
+++ b/challenge-077/abigail/Part1/solution.pl
@@ -36,7 +36,7 @@ chomp (my $N = <>);
 # we cannot duplicate numbers, so we just need one 1.
 #
 my @FIB = (1, 2);
-while ($FIB [-1] + $FIB [-2] < $N) {
+while ($FIB [-1] + $FIB [-2] <= $N) {
     push @FIB => $FIB [-1] + $FIB [-2];
 }
 
-- 
cgit