diff options
| -rw-r--r-- | challenge-076/walt-mankowski/blog.txt | 1 | ||||
| -rw-r--r-- | challenge-076/walt-mankowski/perl/ch-1.pl | 68 | ||||
| -rw-r--r-- | challenge-076/walt-mankowski/perl/ch-2.pl | 116 | ||||
| -rw-r--r-- | challenge-076/walt-mankowski/perl/search_grid.txt | 19 |
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 |