From c6efbedee9e59a37f6a5ce83e8adf8d9a2ecc225 Mon Sep 17 00:00:00 2001
From: Simon Green <mail@simon.green>
Date: Sun, 31 Oct 2021 22:07:28 +1100
Subject: sgreen solutions to challenge 136

---
 challenge-136/sgreen/README.md    |  4 +--
 challenge-136/sgreen/blog.txt     |  1 +
 challenge-136/sgreen/perl/ch-1.pl | 52 +++++++++++++++++++++++++++++++++++++++
 challenge-136/sgreen/perl/ch-2.pl | 44 +++++++++++++++++++++++++++++++++
 4 files changed, 99 insertions(+), 2 deletions(-)
 create mode 100644 challenge-136/sgreen/blog.txt
 create mode 100755 challenge-136/sgreen/perl/ch-1.pl
 create mode 100755 challenge-136/sgreen/perl/ch-2.pl

diff --git a/challenge-136/sgreen/README.md b/challenge-136/sgreen/README.md
index 12939a8bf5..a369799dbf 100644
--- a/challenge-136/sgreen/README.md
+++ b/challenge-136/sgreen/README.md
@@ -1,3 +1,3 @@
-# The Weekly Challenge 135
+# The Weekly Challenge 136
 
-Solution by Simon Green. [Blog](https://dev.to/simongreennet/weekly-challenge-135-g0o)
+Solution by Simon Green. [Blog](https://dev.to/simongreennet/weekly-challenge-136-12m7)
diff --git a/challenge-136/sgreen/blog.txt b/challenge-136/sgreen/blog.txt
new file mode 100644
index 0000000000..98a33767ae
--- /dev/null
+++ b/challenge-136/sgreen/blog.txt
@@ -0,0 +1 @@
+https://dev.to/simongreennet/weekly-challenge-136-12m7
diff --git a/challenge-136/sgreen/perl/ch-1.pl b/challenge-136/sgreen/perl/ch-1.pl
new file mode 100755
index 0000000000..ef834c6ddb
--- /dev/null
+++ b/challenge-136/sgreen/perl/ch-1.pl
@@ -0,0 +1,52 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use feature 'say';
+use List::Util 'min';
+
+sub _gcd {
+    # Calculate the greatest common divisor. Start at the lowest of
+    #   the two supplied numbers
+    my ( $n1, $n2 ) = @_;
+
+    # And work backwards until we find the gcd
+    for ( my $i = min( $n1, $n2 ) ; $i >= 1 ; $i-- ) {
+        return $i if $n1 % $i == 0 and $n2 % $i == 0;
+    }
+
+    # We should never get here, since when $i is one, the equation should
+    #  always be true
+    return 1;
+}
+
+sub _is_pot {
+    # Returns whether the number is a power of two.
+    my $n = shift;
+
+    # Count upwards from 1 until we find a solution or go bust
+    my $i = 0;
+
+    while ( ++$i ) {
+        my $p = 2**$i;
+        return 1 if $p == $n;
+        return 0 if $p > $n;
+    }
+}
+
+sub main {
+    my ( $m, $n ) = @_;
+
+    # Sanity check
+    die "You must specify two numbers\n"               unless defined $m and defined $n;
+    die "The first value is not a positive integer\n"  unless $m =~ /^[1-9][0-9]*$/;
+    die "The second value is not a positive integer\n" unless $n =~ /^[1-9][0-9]*$/;
+
+    # Calculate the gcd
+    my $gcd = _gcd( $m, $n );
+
+    # .. and display whether it is a power of two
+    say _is_pot($gcd);
+}
+
+main(@ARGV);
diff --git a/challenge-136/sgreen/perl/ch-2.pl b/challenge-136/sgreen/perl/ch-2.pl
new file mode 100755
index 0000000000..be9baa5ab9
--- /dev/null
+++ b/challenge-136/sgreen/perl/ch-2.pl
@@ -0,0 +1,44 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use feature 'say';
+
+use List::Util qw(sum0);
+
+sub _find_sums {
+    my $solutions = 0;
+    my ( $remaining, $pool ) = @_;
+
+    while ( my $number = pop @$pool ) {
+        my $sum = sum0(@$pool);
+        if ( $number == $remaining or $number + $sum == $remaining ) {
+            ++$solutions;
+        }
+        elsif ( $number < $remaining ) {
+            if ( $sum >= $remaining - $number ) {
+                #$solutions += _find_sums( $remaining - $number, \@new_pool );
+                $solutions += _find_sums( $remaining - $number, [@$pool] );
+            }
+        }
+    }
+    return $solutions;
+}
+
+sub main {
+    my $n = shift;
+
+    # Sanity check
+    die "You must specify an integer\n"         unless defined $n;
+    die "The value is not a positive integer\n" unless $n =~ /^[1-9][0-9]*$/;
+
+    # Generate list of Fibonacci numbers <= $n
+    my @numbers = ( 1, 2 );
+    while ( $numbers[-2] + $numbers[-1] <= $n ) {
+        push @numbers, $numbers[-2] + $numbers[-1];
+    }
+
+    say _find_sums( $n, \@numbers );
+}
+
+main(@ARGV);
-- 
cgit