Merge pull request #2205 from waltman/branch-for-challenge-076

Branch for challenge 076

4 files changed, 204 insertions, 0 deletions

diff --git a/challenge-076/walt-mankowski/blog.txt b/challenge-076/walt-mankowski/blog.txt
new file mode 100644
index 0000000000..859d3d5201
--- /dev/null
+++ b/challenge-076/walt-mankowski/blog.txt
@@ -0,0 +1 @@
+http://www.mawode.com/blog/blog/2020/09/04/perl-weekly-challenge-76/
diff --git a/challenge-076/walt-mankowski/perl/ch-1.pl b/challenge-076/walt-mankowski/perl/ch-1.pl
new file mode 100644
index 0000000000..99ae70ce29
--- /dev/null
+++ b/challenge-076/walt-mankowski/perl/ch-1.pl
@@ -0,0 +1,68 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use feature qw(:5.32);
+use experimental qw(signatures);
+use List::Util qw(sum);
+use Algorithm::Combinatorics qw(combinations_with_repetition);
+
+# TASK #1 › Prime Sum
+# Submitted by: Mohammad S Anwar
+# Reviewed by: Ryan Thompson
+#
+# You are given a number $N. Write a script to find the minimum number
+# of prime numbers required, whose summation gives you $N.
+#
+# For the sake of this task, please assume 1 is not a prime number.
+# Example:
+#
+# Input:
+#     $N = 9
+#
+# Ouput:
+#     2 as sum of 2 prime numbers i.e. 2 and 7 is same as the input number.
+#     2 + 7 = 9.
+
+# compute primes up to $n using the Sieve of Eratosthenes
+sub primes_upto($n) {
+    my @is_prime = map {1} (0..$n);
+    $is_prime[0] = $is_prime[1] = 0;
+
+    for my $i (2..$n) {
+        if ($is_prime[$i]) {
+            for (my $j = $i * 2; $j <= $n; $j += $i) {
+                $is_prime[$j] = 0;
+            }
+        }
+    }
+    return grep {$is_prime[$_]} 2..$n;
+}
+
+# find n possibly repeating primes, where n <= k, where the primes add
+# up to s
+sub sums_goldbach($s, $k, @primes) {
+    my @solutions;
+    my $best = 1e300;
+
+    my $iter = combinations_with_repetition([0, @primes], $k);
+    while (my $p = $iter->next) {
+        my @digits = grep(!/^0$/, $p->@*); # remove 0s
+        next unless @digits; # ignore (0,0,0)
+        next unless sum(@digits) == $s;
+        if (@digits < $best) {
+            @solutions = (join " + ", @digits);
+            $best = @digits;
+        } elsif (@digits == $best) {
+            push @solutions, join " + ", @digits;
+        }
+    }
+    return @solutions;
+}
+
+my $n = shift @ARGV;
+my @primes = primes_upto($n);
+say "primes: @primes";
+
+my $k = $n % 2 == 0 ? 2 : 3;
+my @solutions = sums_goldbach($n, $k, @primes);
+say join "\n", @solutions;
diff --git a/challenge-076/walt-mankowski/perl/ch-2.pl b/challenge-076/walt-mankowski/perl/ch-2.pl
new file mode 100644
index 0000000000..7a707deac9
--- /dev/null
+++ b/challenge-076/walt-mankowski/perl/ch-2.pl
@@ -0,0 +1,116 @@
+#!/usr/bin/env perl
+use strict;
+use warnings;
+use feature qw(:5.32);
+use experimental qw(signatures);
+use autodie;
+
+# TASK #2 › Word Search
+# Submitted by: Neil Bowers
+# Reviewed by: Ryan Thompson
+#
+# Write a script that takes two file names. The first file would
+# contain word search grid as shown below. The second file contains
+# list of words, one word per line. You could even use local
+# dictionary file.
+#
+# Print out a list of all words seen on the grid, looking both
+# orthogonally and diagonally, backwards as well as forwards.
+#
+# Output
+# Found 54 words of length 5 or more when checked against the local
+# dictionary. You may or may not get the same result but that is fine.
+
+my $MIN_LEN = 5;
+my ($grid_name, $dict_name) = @ARGV;
+my $grid = read_grid($grid_name);
+my $rows = $grid->@*;
+my $cols = $grid->[0]->@*;
+
+my ($words, $prefixes) = parse_dict($dict_name, $MIN_LEN);
+
+my @dirs = ([ 0,  1], # e
+            [-1,  1], # ne
+            [-1,  0], # n
+            [-1, -1], # nw
+            [ 0, -1], # w
+            [ 1, -1], # sw
+            [ 1,  0], # s
+            [ 1,  1], # se
+           );
+
+my @found;
+for my $row (0..$rows-1) {
+    for my $col (0..$cols-1) {
+        for my $dir (@dirs) {
+            push @found, search_grid($grid, $row, $col, $dir, $words, $prefixes);
+        }
+    }
+}
+
+for my $word (sort @found) {
+    say $word;
+}
+
+sub read_grid($grid_name) {
+    my @grid;
+    open my $fh, '<', $grid_name;
+    my $width = 0;
+    my $row = 0;
+    while (my $line = <$fh>) {
+        chomp $line;
+        $line =~ s/ //g;
+        if ($width == 0) {
+            # make top line
+            $width = 2 + length($line);
+            for my $col (0..$width-1) {
+                $grid[$row][$col] = ' ';
+            }
+            $row = 1;
+        }
+        my @c = split //, $line;
+        $grid[$row][0] = ' ';
+        for my $i (0..$#c) {
+            $grid[$row][$i+1] = lc $c[$i];
+        }
+        $grid[$row][$width-1] = ' ';
+        $row++;
+    }
+    # make bottom line
+    for my $col (0..$width-1) {
+        $grid[$row][$col] = ' ';
+    }
+
+    return \@grid;
+}
+
+sub parse_dict($dict_name, $min_len) {
+    my %words;
+    my %prefixes;
+
+    open my $fh, '<', $dict_name;
+    while (my $word = <$fh>) {
+        chomp $word;
+        next unless length($word) >= $min_len;
+        next unless $word =~ /^[a-z]+$/;
+
+        $words{$word} = 1;
+        for my $len (1..length($word)) {
+            $prefixes{substr($word, 0, $len)} = 1;
+        }
+    }
+    return (\%words, \%prefixes);
+}
+
+sub search_grid($grid, $row, $col, $dir, $words, $prefixes) {
+    my @found;
+    my $s = $grid->[$row][$col];
+    while (defined $prefixes->{$s}) {
+        $row += $dir->[0];
+        $col += $dir->[1];
+        $s .= $grid->[$row][$col];
+        push @found, $s if defined $words->{$s};
+    }
+
+    return @found;
+}
diff --git a/challenge-076/walt-mankowski/perl/search_grid.txt b/challenge-076/walt-mankowski/perl/search_grid.txt
new file mode 100644
index 0000000000..31cf2e0fd8
--- /dev/null
+++ b/challenge-076/walt-mankowski/perl/search_grid.txt
@@ -0,0 +1,19 @@
+B I D E M I A T S U C C O R S T
+L D E G G I W Q H O D E E H D P
+U S E I R U B U T E A S L A G U
+N G N I Z I L A I C O S C N U D
+T G M I D S T S A R A R E I F G
+S R E N M D C H A S I V E E L I
+S C S H A E U E B R O A D M T E
+H W O V L P E D D L A I U L S S
+R Y O N L A S F C S T A O G O T
+I G U S S R R U G O V A R Y O C
+N R G P A T N A N G I L A M O O
+E I H A C E I V I R U S E S E D
+S E T S U D T T G A R L I C N H
+H V R M X L W I U M S N S O T B
+A E A O F I L C H T O D C A E U
+Z S C D F E C A A I I R L N R F
+A R I I A N Y U T O O O U T P F
+R S E C I S N A B O S C N E R A
+D R S M P C U U N E L T E S I L