Merge pull request #1169 from rjt-pl/rjt_044

rjt's Week 044 solutions and blogs

6 files changed, 120 insertions, 0 deletions

diff --git a/challenge-044/ryan-thompson/blog.txt b/challenge-044/ryan-thompson/blog.txt
new file mode 100644
index 0000000000..0d4cc8b833
--- /dev/null
+++ b/challenge-044/ryan-thompson/blog.txt
@@ -0,0 +1 @@
+http://www.ry.ca/2020/01/only-100-please/
diff --git a/challenge-044/ryan-thompson/blog1.txt b/challenge-044/ryan-thompson/blog1.txt
new file mode 100644
index 0000000000..17c8d9cbe3
--- /dev/null
+++ b/challenge-044/ryan-thompson/blog1.txt
@@ -0,0 +1 @@
+http://www.ry.ca/2020/01/make-it-200/
diff --git a/challenge-044/ryan-thompson/perl/ch-1.pl b/challenge-044/ryan-thompson/perl/ch-1.pl
new file mode 100755
index 0000000000..f37de54602
--- /dev/null
+++ b/challenge-044/ryan-thompson/perl/ch-1.pl
@@ -0,0 +1,37 @@
+#!/usr/bin/env perl
+#
+# ch-1.pl - Add + and - to 123456789 so it sums to 100
+#
+# 2020 Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+no warnings 'uninitialized';
+
+# @ops can contain any Perl binary numeric operator
+# Adding more ops grows search space exponentially.
+#my       @ops = qw( + - * / % >> << & | );
+my        @ops = qw( + - );
+my @prefix_ops = qw( + - ); # Ops which are also prefix ops
+
+sum_split(sum => 100, num => 123456789);
+
+# Output all possible ways to insert + and - into num, such that the
+# resulting expression == sum. Named arguments:
+sub sum_split {
+    my %o = @_;
+
+    if (0 == length $o{num}) {
+        my $sum = eval $o{exp} // return;
+        say "$sum == $o{exp}" if $sum == $o{sum};
+        return
+    }
+
+    # Partition $num and recurse
+    for (1..length $o{num}) {
+        my ($l, $r) = unpack "A$_ A*", $o{num};
+        my @cur_ops = length($o{exp}) > 0 ? @ops : @prefix_ops;
+        sum_split(%o, num => $r, exp => "$o{exp}$_$l") for @cur_ops;
+    }
+}
diff --git a/challenge-044/ryan-thompson/perl/ch-2.pl b/challenge-044/ryan-thompson/perl/ch-2.pl
new file mode 100755
index 0000000000..c348ec6e18
--- /dev/null
+++ b/challenge-044/ryan-thompson/perl/ch-2.pl
@@ -0,0 +1,40 @@
+#!/usr/bin/env perl
+#
+# ch-2.pl - Double or +1
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use warnings;
+use strict;
+use feature qw< signatures current_sub say >;
+no warnings 'experimental::signatures';
+
+say "@{[ double_or_plus(1, 200) ]}";
+say "@{[ exhaustive(1, 200, 9) ]}";
+
+# Just work backwards
+sub double_or_plus( $start, $end ) {
+    my @path = $end;
+    while ($end != $start) {
+        $end = $end % 2 ? $end - 1 : $end / 2;
+        unshift @path, $end;
+    }
+    @path;
+}
+
+# This is only necessary if you don't trust double_or_plus
+sub exhaustive( $start, $end, $max_path ) {
+    my @shortest = (0) x ($max_path + 1);
+
+    sub ( $start, $end, @path ) {
+        push @path, $start;
+
+        return if @path > @shortest or $start >  $end;
+        @shortest = @path and return if $start == $end;
+
+        __SUB__->($start + 1, $end, @path);
+        __SUB__->($start * 2, $end, @path); 
+    }->($start, $end);
+
+    @shortest;
+}
diff --git a/challenge-044/ryan-thompson/raku/ch-1.raku b/challenge-044/ryan-thompson/raku/ch-1.raku
new file mode 100644
index 0000000000..8c11ca3117
--- /dev/null
+++ b/challenge-044/ryan-thompson/raku/ch-1.raku
@@ -0,0 +1,23 @@
+#!/usr/bin/env perl6
+
+# ch-1.raku - Insert +/- into 123456789 to make 100
+#
+# Ryan Thompson <rjt@cpan.org>
+
+
+my $num = 123456789;
+
+expr-split(100, 123456789);
+
+#| Insert +/- into $num such that the expression = $sum; output all
+sub expr-split( Int $sum, Int $num, Str $exp = '', Int $psum = 0 ) {
+    say $exp if $num == 0 and $psum == $sum;
+    return   if $num == 0;
+
+    for 1..$num.chars {
+        my ($l, $r) = ($num.substr(0, $_), $num.substr($_))».Int;
+        expr-split($sum, $r, "$exp+$l", $psum + $l);
+        expr-split($sum, $r, "$exp-$l", $psum - $l);
+    }
+}
+
diff --git a/challenge-044/ryan-thompson/raku/ch-2.raku b/challenge-044/ryan-thompson/raku/ch-2.raku
new file mode 100644
index 0000000000..e4800c1bca
--- /dev/null
+++ b/challenge-044/ryan-thompson/raku/ch-2.raku
@@ -0,0 +1,18 @@
+#!/usr/bin/env perl6
+
+# ch-2.raku - +1 or *2 to 200
+#
+# Ryan Thompson <rjt@cpan.org>
+
+say double-or-plus(1, 200);
+
+# Shortest path verified past 1..43000, maybe I'll come up with a proof
+sub double-or-plus( Int $start, Int $end is copy ) {
+    my @path = $end;
+    while ($end != $start) {
+        $end = $end %% 2 ?? ($end / 2).Int !! $end -1;
+        @path.unshift($end);
+    }
+
+    @path;
+}