Solutions for challenges 001-005

25 files changed, 461 insertions, 0 deletions

diff --git a/challenge-001/ryan-thompson/README b/challenge-001/ryan-thompson/README
new file mode 100644
index 0000000000..53b1e7cfa0
--- /dev/null
+++ b/challenge-001/ryan-thompson/README
@@ -0,0 +1 @@
+Solutions by Ryan Thompson.
diff --git a/challenge-001/ryan-thompson/perl5/ch-1.pl b/challenge-001/ryan-thompson/perl5/ch-1.pl
new file mode 100755
index 0000000000..43570e88a1
--- /dev/null
+++ b/challenge-001/ryan-thompson/perl5/ch-1.pl
@@ -0,0 +1,14 @@
+#!/usr/bin/env perl
+#
+# ch-1.pl - s/e/E/g
+#
+# 2019 Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+
+my $str = 'Perl Weekly Challenge';
+my $count = $str =~ tr/e/E/;
+
+say "$str -> e x $count";
diff --git a/challenge-001/ryan-thompson/perl5/ch-2.pl b/challenge-001/ryan-thompson/perl5/ch-2.pl
new file mode 100755
index 0000000000..c066e37ead
--- /dev/null
+++ b/challenge-001/ryan-thompson/perl5/ch-2.pl
@@ -0,0 +1,12 @@
+#!/usr/bin/env perl
+#
+# ch-2.pl - FizzBuzz "one-liner"
+#
+# 2019 Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+
+say !($_ % 15) ? 'fizzbuzz'
+  : !($_ %  3) ? 'fizz'
+  : !($_ %  5) ? 'buzz'
+  :              $_ for 1..20;
diff --git a/challenge-001/ryan-thompson/perl6/ch-1.p6 b/challenge-001/ryan-thompson/perl6/ch-1.p6
new file mode 100755
index 0000000000..08c7107545
--- /dev/null
+++ b/challenge-001/ryan-thompson/perl6/ch-1.p6
@@ -0,0 +1,11 @@
+#!/usr/bin/env perl6
+
+# ch-1.p6 - s/e/E/g
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use v6;
+
+my Str $str = 'Perl Weekly Challenge';
+my $distance = $str ~~ tr/e/E/;
+say "$str -> e x " ~ $distance.Int;
diff --git a/challenge-001/ryan-thompson/perl6/ch-2.p6 b/challenge-001/ryan-thompson/perl6/ch-2.p6
new file mode 100755
index 0000000000..5b3ff142e5
--- /dev/null
+++ b/challenge-001/ryan-thompson/perl6/ch-2.p6
@@ -0,0 +1,14 @@
+#!/usr/bin/env perl6
+
+# ch-2.p6 - FizzBuzz "one-liner"
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use v6;
+
+(1..20).map({
+    !($_ % 15) ?? 'fizzbuzz'
+ !! !($_ %  3) ?? 'fizz'
+ !! !($_ %  5) ?? 'buzz'
+ !!               $_
+})».say;
diff --git a/challenge-002/ryan-thompson/README b/challenge-002/ryan-thompson/README
new file mode 100644
index 0000000000..53b1e7cfa0
--- /dev/null
+++ b/challenge-002/ryan-thompson/README
@@ -0,0 +1 @@
+Solutions by Ryan Thompson.
diff --git a/challenge-002/ryan-thompson/perl5/ch-1.pl b/challenge-002/ryan-thompson/perl5/ch-1.pl
new file mode 100755
index 0000000000..6b39a9c09e
--- /dev/null
+++ b/challenge-002/ryan-thompson/perl5/ch-1.pl
@@ -0,0 +1,19 @@
+#!/usr/bin/env perl
+#
+# ch-1.pl - Remove leading zeroes from positive numbers
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+no warnings 'uninitialized';
+
+# Accept filenames or standard input
+
+# The spec was a bit vague, so I'm choosing to only modify numbers that start
+# at the beginning of a line. Change the ^ to a \b to work on any number
+print s/^0+(?=[1-9])//r while (<<>>);
+
+# Another cheeky way about it, if you are certain you only have +ve ints:
+# say 0+$_ while (<<>>);
diff --git a/challenge-002/ryan-thompson/perl5/ch-2.pl b/challenge-002/ryan-thompson/perl5/ch-2.pl
new file mode 100755
index 0000000000..6f67afd439
--- /dev/null
+++ b/challenge-002/ryan-thompson/perl5/ch-2.pl
@@ -0,0 +1,46 @@
+#!/usr/bin/env perl
+#
+# ch-2.pl - Convert integers to and from base35
+#
+# 2019 Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+no warnings 'uninitialized';
+
+my @base35 = (0..9, 'a'..'y'); # Display representation
+my %val; @val{@base35} = 0..34;
+
+# Verification: Covert 20 random numbers to and from base35
+printf "%8d => %8s => %8d\n", 
+    $_, int_to_base35($_), base35_to_int(int_to_base35($_)) 
+        for map { int rand(1e8) } 1..20;
+
+sub int_to_base35 {
+    my $int = shift;
+    die "Expecting integer" unless $int =~ /^\d+$/;
+
+    my $base35;
+    while ($int) {
+        $base35 = $base35[ $int % 35 ] . $base35;
+        my $digit = $int % 35;
+        $int = int($int / 35);
+    }
+
+    $base35 // 0;
+}
+
+sub base35_to_int {
+    my $base35 = lc( shift );
+    die "Expecting [0-9a-y]" unless $base35 =~ /^[0-9a-y]+$/;
+
+    my $mul = 1; # Digits multiplier
+    my $int = 0; # Result
+    for (reverse split '', $base35) {
+        $int += $mul * $val{$_};
+        $mul *= 35;
+    }
+
+    $int;
+}
diff --git a/challenge-002/ryan-thompson/perl6/ch-1.p6 b/challenge-002/ryan-thompson/perl6/ch-1.p6
new file mode 100755
index 0000000000..626b52cc1f
--- /dev/null
+++ b/challenge-002/ryan-thompson/perl6/ch-1.p6
@@ -0,0 +1,9 @@
+#!/usr/bin/env perl6
+
+# ch-1.p6 - Remove leading zeroes from positive numbers
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use v6;
+
+S/^0+ <?[ 1..9 ]>//.say for $*ARGFILES.lines;
diff --git a/challenge-002/ryan-thompson/perl6/ch-2.p6 b/challenge-002/ryan-thompson/perl6/ch-2.p6
new file mode 100755
index 0000000000..10c65b3af8
--- /dev/null
+++ b/challenge-002/ryan-thompson/perl6/ch-2.p6
@@ -0,0 +1,10 @@
+#!/usr/bin/env perl6
+
+# ch-2.p6 - Convert numbers to/from base35
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use v6;
+
+.say for <0 34 35 69 70 1170605>».base(35);
+.say for <0  Y 10 1Y 20    Raku>».parse-base(35);
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;
+    }
+}
+
diff --git a/challenge-004/ryan-thompson/README b/challenge-004/ryan-thompson/README
new file mode 100644
index 0000000000..53b1e7cfa0
--- /dev/null
+++ b/challenge-004/ryan-thompson/README
@@ -0,0 +1 @@
+Solutions by Ryan Thompson.
diff --git a/challenge-004/ryan-thompson/perl5/ch-1.pl b/challenge-004/ryan-thompson/perl5/ch-1.pl
new file mode 100755
index 0000000000..865c249e5a
--- /dev/null
+++ b/challenge-004/ryan-thompson/perl5/ch-1.pl
@@ -0,0 +1,13 @@
+#!/usr/bin/env perl
+#
+# ch-1.pl - Display as many digits of pi as there are characters in this file
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+
+use bignum qw< bpi >;
+
+say bpi((-s $0) - 2);
diff --git a/challenge-004/ryan-thompson/perl5/ch-2.pl b/challenge-004/ryan-thompson/perl5/ch-2.pl
new file mode 100755
index 0000000000..af4fed57c4
--- /dev/null
+++ b/challenge-004/ryan-thompson/perl5/ch-2.pl
@@ -0,0 +1,30 @@
+#!/usr/bin/env perl
+#
+# ch-2.pl - Filter words that are made up of a given list of letters
+#
+# Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+no warnings     'uninitialized';
+use feature     'fc'; # >= 5.16
+use List::Util  'all';
+
+sub legal_word(_);
+
+my $letters = $ARGV[0] // die "Usage: $0 letters < words.txt";
+my %letters = letter_hash($letters);
+print for grep legal_word, <STDIN>;
+
+# Return true if $word can be formed using %letters
+sub legal_word(_) {
+    my ($word) = @_;
+    chomp $word;
+    my %word = letter_hash($word);
+
+    all { $word{$_} <= $letters{$_} } keys %word;
+}
+
+# Turn abcc into ( a => 1, b => 1, c => 2 )
+sub letter_hash { my %r; $r{ fc($_) }++ for split '', $_[0]; %r }
diff --git a/challenge-004/ryan-thompson/perl6/ch-1.p6 b/challenge-004/ryan-thompson/perl6/ch-1.p6
new file mode 100755
index 0000000000..dad130282d
--- /dev/null
+++ b/challenge-004/ryan-thompson/perl6/ch-1.p6
@@ -0,0 +1,2 @@
+use v6.d;
+π.say;
diff --git a/challenge-004/ryan-thompson/perl6/ch-2.p6 b/challenge-004/ryan-thompson/perl6/ch-2.p6
new file mode 100644
index 0000000000..74d466153a
--- /dev/null
+++ b/challenge-004/ryan-thompson/perl6/ch-2.p6
@@ -0,0 +1,12 @@
+#!/usr/bin/env perl6
+
+# ch-2.p6 - Print words that only contain letters in argument
+#
+# Ryan Thompson <rjt@cpan.org>
+
+sub MAIN( Str $letter-string ) {
+    my $letters = $letter-string.fc.comb.Bag;
+
+    .say for $*ARGFILES.lines.grep: { .fc.comb.Bag ⊆ $letters }
+
+}
diff --git a/challenge-005/ryan-thompson/README b/challenge-005/ryan-thompson/README
new file mode 100644
index 0000000000..53b1e7cfa0
--- /dev/null
+++ b/challenge-005/ryan-thompson/README
@@ -0,0 +1 @@
+Solutions by Ryan Thompson.
diff --git a/challenge-005/ryan-thompson/perl5/ch-1.pl b/challenge-005/ryan-thompson/perl5/ch-1.pl
new file mode 100755
index 0000000000..c5f4d781f2
--- /dev/null
+++ b/challenge-005/ryan-thompson/perl5/ch-1.pl
@@ -0,0 +1,26 @@
+#!/usr/bin/env perl
+#
+# ch-1.pl - Print all anagrams of a given word
+#
+# 2019 Ryan Thompson <rjt@cpan.org>
+
+use 5.010;
+use warnings;
+use strict;
+no warnings 'uninitialized';
+use feature 'fc';
+
+# Dictionary creation is O(n) on number of words. Anagram lookup is O(1).
+
+my %dict;
+for (<STDIN>) {
+    chomp;
+    my $key = join '', sort split '', fc;
+    $dict{$key} //= [ ];
+    push @{$dict{$key}}, fc($_);
+};
+
+my $word = shift // die "Usage: $0 <word>";
+my $word_key = join '', sort split '', fc($word);
+
+say for sort @{ $dict{$word_key} // die "$word is not in dictionary" };
diff --git a/challenge-005/ryan-thompson/perl5/ch-2.pl b/challenge-005/ryan-thompson/perl5/ch-2.pl
new file mode 100755
index 0000000000..c95cd95644
--- /dev/null
+++ b/challenge-005/ryan-thompson/perl5/ch-2.pl
@@ -0,0 +1,33 @@
+#!/usr/bin/env perl
+#
+# ch-2.pl - Print "string of characters" with the most anagrams
+#
+# 2019 Ryan Thompson <rjt@cpan.org>
+
+# There's some ambiguity in the challenge description. I do not know what
+# "a sequence of characters" means in the context of this challenge, so I'm
+# going to write some general functions and then turn that into a specific
+# example. The general functions could, however, be used to analyze just
+# about any sequence of characters.
+
+use 5.010;
+use warnings;
+use strict;
+no warnings 'uninitialized';
+use feature 'fc';
+use List::Util qw< max >;
+
+# All the smarts are in the dictionary. We key on the sorted list of chars,
+# and append the original word to an array ref in the value. Thus all anagrams
+# of each other will have the same hash key.
+my %dict;
+for (<STDIN>) {
+    chomp;
+    my $key = join '', sort split '', fc;
+    $dict{$key} //= [ ];
+    push @{$dict{$key}}, fc($_);
+};
+
+# This gives all results in the event of a tie (the case with my dict)
+my $max = max map { scalar @$_ } values %dict;
+say for map { "<@$_>" } grep { @$_ == $max } values %dict;
diff --git a/challenge-005/ryan-thompson/perl6/ch-1.p6 b/challenge-005/ryan-thompson/perl6/ch-1.p6
new file mode 100644
index 0000000000..41608eabcc
--- /dev/null
+++ b/challenge-005/ryan-thompson/perl6/ch-1.p6
@@ -0,0 +1,23 @@
+#!/usr/bin/env perl6
+
+# ch-1.p6 - Print all anagrams of a word
+#
+# Ryan Thompson <rjt@cpan.org>
+
+sub MAIN( Str $word ) {
+    # 25 seconds. I'm hoping this will get faster as Raku matures...
+    my %dict = % .classify-list: { word-key($_) }, $*ARGFILES.lines».fc;
+
+    .say for %dict{ word-key($word) };
+}
+
+sub word-key( Str $word ) { $word.fc.comb.sort.join }
+
+# Here's a cute-but-very-slow version. Instructive, but .permutations
+# really takes a long time on long words like ｢irresistible｣
+# (12! = 479,001,600 permutations)
+sub MAIN_cute_but_slow( Str $word ) {
+    my $perm = set $word.fc.comb.permutations».join.unique;
+    my $dict = set $*ARGFILES.lines».fc;
+    .say for ($dict ∩ $perm).keys.sort;
+}
diff --git a/challenge-005/ryan-thompson/perl6/ch-2.p6 b/challenge-005/ryan-thompson/perl6/ch-2.p6
new file mode 100644
index 0000000000..5aff9bec0e
--- /dev/null
+++ b/challenge-005/ryan-thompson/perl6/ch-2.p6
@@ -0,0 +1,14 @@
+#!/usr/bin/env perl6
+
+# ch-2.p6 - Print word with highest anagram count
+#
+# Ryan Thompson <rjt@cpan.org>
+
+sub MAIN( ) {
+    my %dict = % .classify-list: { word-key($_) }, $*ARGFILES.lines».fc;
+
+    my $max = %dict.values».elems.max;
+    .say for %dict.values.grep: { .elems == $max };
+}
+
+sub word-key( Str $word ) { $word.fc.comb.sort.join }