Solutions for challenges 001-005

5 files changed, 169 insertions, 0 deletions

diff --git a/challenge-003/ryan-thompson/README b/challenge-003/ryan-thompson/README
new file mode 100644
index 0000000000..53b1e7cfa0
--- /dev/null
+++ b/challenge-003/ryan-thompson/README
@@ -0,0 +1 @@
+Solutions by Ryan Thompson.
diff --git a/challenge-003/ryan-thompson/perl5/ch-1.pl b/challenge-003/ryan-thompson/perl5/ch-1.pl
new file mode 100755
index 0000000000..be8543a812
--- /dev/null
+++ b/challenge-003/ryan-thompson/perl5/ch-1.pl
@@ -0,0 +1,85 @@
+#!/usr/bin/env perl
+#
+# ch-1.pl - Generate 5-smooth numbers (all prime divisors < 5)
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+no warnings 'uninitialized';
+use List::Util qw< min max sum >;
+
+my $limit = $ARGV[0] // die "Usage: $0 <limit>";
+
+say join ', ', hamming($limit);
+
+# Return hamming numbers up to the specified limit.
+
+# We do this by putting all # Hamming numbers < $limit into an array (@n).
+# The list is then sorted. This gives us O(n log n) complexity. See POD.
+sub hamming {
+    my $limit = shift;
+
+    # Pre-generate all powers of prime factors 2, 3, and 5
+    my @d2 = map { 2**$_ } 0..( log($limit) / log(2) );
+    my @d3 = map { 3**$_ } 0..( log($limit) / log(3) );
+    my @d5 = map { 5**$_ } 0..( log($limit) / log(5) );
+
+    my @n;
+    for my $d2 (@d2) {
+        for my $d3 (@d3) {
+            last if $d2 * $d3 > $limit;
+            push @n, grep { $_ <= $limit } map { $d2 * $d3 * $_ } @d5;
+        }
+    }
+
+    sort { $a <=> $b } @n;
+}
+
+__END__
+
+=head1 COMPLEXITY ANALYSIS
+
+Perl's mergesort C<sort()> guarantees O(N log N) worst case behaviour. The
+final line of our function is:
+
+    sort { $a <=> $b } @n;
+
+So we are certainly bound by O(N log N) complexity on the size of the
+resulting list. However, is it possible for another term to dominate?
+
+We do have a 3-level nested loop over C<@d2>, C<@d3> and C<@d5>.
+Fortunately, the bounds for each loop are known to be:
+
+    log($limit) / log($prime)   # Where $prime is 2, 3, or 5
+
+Additionally, we exit the loops early when the partial product is already
+greater than C<$limit>. Even if we ignore this, the complexity we get
+from these loops is:
+
+    (log($limit) / log(2)) * (log($limit) / log(3)) * (log($limit) / log(5))
+
+    LOG_235 = log^3($limit) / (log(2) * log(3) * log(5))
+
+To analytically compare the above (abbreviated to LOG_235) versus N log N, we
+need a way to calculate N (i.e., the size of the result list) given the
+initial C<$limit>. This is non-trivial. So an easier way to find our answer is
+to compare the growth empirically. This works because it is easy to see both
+formulae are strictly increasing.
+
+    $limit  List Size (N)  LOG_235    O(N log N)
+    --------------------------------------------
+      1e1               9       24            19
+      1e2              34      105           119
+      1e3              86      350           383
+      1e4             175      756           903
+      1e5             313     1496          1798
+      1e6             507     2340          3157
+      1e7             768     3960          5102
+      1e8            1105     5508          7743
+      1e9            1530     7410         11219
+      1e10           2053    10710         15658
+
+Thus, except for insignificantly small values of C<$limit>, O(N log N)
+dominates, though LOG_235 is never far behind.
diff --git a/challenge-003/ryan-thompson/perl5/ch-2.pl b/challenge-003/ryan-thompson/perl5/ch-2.pl
new file mode 100755
index 0000000000..40365b3c26
--- /dev/null
+++ b/challenge-003/ryan-thompson/perl5/ch-2.pl
@@ -0,0 +1,26 @@
+#!/usr/bin/env perl
+#
+# ch-2.pl - Pascal's Triangle
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+no warnings 'uninitialized';
+
+my $height = shift // die "Usage: $0 <height>";
+
+say "@{$_}" for pascal_triangle($height);
+
+# Generate Pascal's Triangle to the specified height.
+# Note we do not pretty-print it like I did in the p6 solution, as I wanted to
+# demonstrate a more generic solution.
+sub pascal_triangle {
+    my $h = shift;
+
+    my @tri = [1];
+    push @tri, [ 1, map { $tri[-1][$_-1] + $tri[-1][$_] } 1..$_ ] for 1..$h-1;
+
+    @tri;
+}
diff --git a/challenge-003/ryan-thompson/perl6/ch-1.p6 b/challenge-003/ryan-thompson/perl6/ch-1.p6
new file mode 100755
index 0000000000..2876b7c035
--- /dev/null
+++ b/challenge-003/ryan-thompson/perl6/ch-1.p6
@@ -0,0 +1,31 @@
+#!/usr/bin/env perl6
+
+# ch-1.p6 - Generate 5-smooth (Hamming) numbers
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use v6;
+
+my Int $lim = 10000;
+
+sub MAIN( Int $limit ) {
+    hamming($limit).join(', ').say;
+}
+
+#| Return Hamming numbers up to the specified $limit
+sub hamming( Int $limit ) {
+    my @n;
+    for 1, 2, 4, 8 … ∞ -> $d2 {
+        last if $d2 > $limit;
+        for 1, 3, 9, 27 … ∞ -> $d3 {
+            last if $d2 * $d3 > $limit;
+            for 1, 5, 25, 125 … ∞ -> $d5 {
+                my $n = $d2 * $d3 * $d5;
+                last if $n > $limit;
+                @n.push($n);
+            }
+        }
+    }
+
+    @n.sort;
+}
diff --git a/challenge-003/ryan-thompson/perl6/ch-2.p6 b/challenge-003/ryan-thompson/perl6/ch-2.p6
new file mode 100755
index 0000000000..ff34c1846d
--- /dev/null
+++ b/challenge-003/ryan-thompson/perl6/ch-2.p6
@@ -0,0 +1,26 @@
+#!/usr/bin/env perl6
+
+# ch-2.p6 - Generate Pascal's Triangle
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use v6;
+
+#| Instructive binomial coefficient implementation from Perl 6 Examples page
+sub infix:<choose> { [*] ($^n … 0) Z/ 1 .. $^p }
+
+sub MAIN( Int $height = 12 ) {
+    pascal-triangle($height);
+}
+
+#| Print Pascal's Triangle, up to the specified height
+sub pascal-triangle( Int $h ) {
+    my $width = ($h choose ($h / 2).Int).chars; # Widest element
+
+    for ^$h -> $n {
+        my @row = (0..$n).map: { $n choose $_ };
+        my $str = @row.fmt("%{$width}d").join;
+        say ' ' x ($h * ($width + 1) / 2 - $str.chars / 2).Int ~ $str;
+    }
+}
+