From a26d8716271b568c97c62ff33dafcc123fb1e33f Mon Sep 17 00:00:00 2001 From: Ryan Thompson Date: Tue, 17 Dec 2019 16:45:28 -0600 Subject: Solutions for challenges 001-005 --- challenge-001/ryan-thompson/README | 1 + challenge-001/ryan-thompson/perl5/ch-1.pl | 14 +++++ challenge-001/ryan-thompson/perl5/ch-2.pl | 12 +++++ challenge-001/ryan-thompson/perl6/ch-1.p6 | 11 ++++ challenge-001/ryan-thompson/perl6/ch-2.p6 | 14 +++++ challenge-002/ryan-thompson/README | 1 + challenge-002/ryan-thompson/perl5/ch-1.pl | 19 +++++++ challenge-002/ryan-thompson/perl5/ch-2.pl | 46 +++++++++++++++++ challenge-002/ryan-thompson/perl6/ch-1.p6 | 9 ++++ challenge-002/ryan-thompson/perl6/ch-2.p6 | 10 ++++ challenge-003/ryan-thompson/README | 1 + challenge-003/ryan-thompson/perl5/ch-1.pl | 85 +++++++++++++++++++++++++++++++ challenge-003/ryan-thompson/perl5/ch-2.pl | 26 ++++++++++ challenge-003/ryan-thompson/perl6/ch-1.p6 | 31 +++++++++++ challenge-003/ryan-thompson/perl6/ch-2.p6 | 26 ++++++++++ challenge-004/ryan-thompson/README | 1 + challenge-004/ryan-thompson/perl5/ch-1.pl | 13 +++++ challenge-004/ryan-thompson/perl5/ch-2.pl | 30 +++++++++++ challenge-004/ryan-thompson/perl6/ch-1.p6 | 2 + challenge-004/ryan-thompson/perl6/ch-2.p6 | 12 +++++ challenge-005/ryan-thompson/README | 1 + challenge-005/ryan-thompson/perl5/ch-1.pl | 26 ++++++++++ challenge-005/ryan-thompson/perl5/ch-2.pl | 33 ++++++++++++ challenge-005/ryan-thompson/perl6/ch-1.p6 | 23 +++++++++ challenge-005/ryan-thompson/perl6/ch-2.p6 | 14 +++++ 25 files changed, 461 insertions(+) create mode 100644 challenge-001/ryan-thompson/README create mode 100755 challenge-001/ryan-thompson/perl5/ch-1.pl create mode 100755 challenge-001/ryan-thompson/perl5/ch-2.pl create mode 100755 challenge-001/ryan-thompson/perl6/ch-1.p6 create mode 100755 challenge-001/ryan-thompson/perl6/ch-2.p6 create mode 100644 challenge-002/ryan-thompson/README create mode 100755 challenge-002/ryan-thompson/perl5/ch-1.pl create mode 100755 challenge-002/ryan-thompson/perl5/ch-2.pl create mode 100755 challenge-002/ryan-thompson/perl6/ch-1.p6 create mode 100755 challenge-002/ryan-thompson/perl6/ch-2.p6 create mode 100644 challenge-003/ryan-thompson/README create mode 100755 challenge-003/ryan-thompson/perl5/ch-1.pl create mode 100755 challenge-003/ryan-thompson/perl5/ch-2.pl create mode 100755 challenge-003/ryan-thompson/perl6/ch-1.p6 create mode 100755 challenge-003/ryan-thompson/perl6/ch-2.p6 create mode 100644 challenge-004/ryan-thompson/README create mode 100755 challenge-004/ryan-thompson/perl5/ch-1.pl create mode 100755 challenge-004/ryan-thompson/perl5/ch-2.pl create mode 100755 challenge-004/ryan-thompson/perl6/ch-1.p6 create mode 100644 challenge-004/ryan-thompson/perl6/ch-2.p6 create mode 100644 challenge-005/ryan-thompson/README create mode 100755 challenge-005/ryan-thompson/perl5/ch-1.pl create mode 100755 challenge-005/ryan-thompson/perl5/ch-2.pl create mode 100644 challenge-005/ryan-thompson/perl6/ch-1.p6 create mode 100644 challenge-005/ryan-thompson/perl6/ch-2.p6 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 + +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 + +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 + +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 + +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 + +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 + +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 + +use v6; + +S/^0+ //.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 + +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 + +use 5.010; +use warnings; +use strict; +no warnings 'uninitialized'; +use List::Util qw< min max sum >; + +my $limit = $ARGV[0] // die "Usage: $0 "; + +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 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 + +use 5.010; +use warnings; +use strict; +no warnings 'uninitialized'; + +my $height = shift // die "Usage: $0 "; + +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 + +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 + +use v6; + +#| Instructive binomial coefficient implementation from Perl 6 Examples page +sub infix: { [*] ($^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 + +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 + +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, ; + +# 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 + +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 + +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 () { + chomp; + my $key = join '', sort split '', fc; + $dict{$key} //= [ ]; + push @{$dict{$key}}, fc($_); +}; + +my $word = shift // die "Usage: $0 "; +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 + +# 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 () { + 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 + +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 + +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 } -- cgit