diff options
| -rw-r--r-- | challenge-076/cheok-yin-fung/perl/BLOG.txt | 1 | ||||
| -rw-r--r-- | challenge-076/cheok-yin-fung/perl/ch-1.pl | 82 | ||||
| -rw-r--r-- | challenge-076/cheok-yin-fung/perl/ch-2.pl | 189 |
3 files changed, 272 insertions, 0 deletions
diff --git a/challenge-076/cheok-yin-fung/perl/BLOG.txt b/challenge-076/cheok-yin-fung/perl/BLOG.txt new file mode 100644 index 0000000000..5ffd910c6c --- /dev/null +++ b/challenge-076/cheok-yin-fung/perl/BLOG.txt @@ -0,0 +1 @@ +http://blogs.perl.org/users/c_y_fung/2020/09/cys-take-on-pwc076.html diff --git a/challenge-076/cheok-yin-fung/perl/ch-1.pl b/challenge-076/cheok-yin-fung/perl/ch-1.pl new file mode 100644 index 0000000000..b5c2260f6e --- /dev/null +++ b/challenge-076/cheok-yin-fung/perl/ch-1.pl @@ -0,0 +1,82 @@ +# Perl Weekly Challenge #076 Task 1 Prime Sum +# task statement: +# You are given a number $N. Write a script +# to find the minimum number of prime numbers +# required, whose summation gives you $N. +# Usage: ch-1.pl $N + +# Given the Goldbach's conjecture is verified +# for n < 4 000 000 000 000 000 000 +# ( source: mathworld.wolfram.com ) + +use strict; +use warnings; + +sub is_prime { + my $ans = 1; + for my $i (2..int sqrt($_[0])) { + if ($_[0] % $i == 0) {$ans = 0; return 0;} + } + return $ans; +} + +my %oddprime; +my $V; +if ($ARGV[0]) {$V = $ARGV[0];} else {$V = 1024;} + +# small special cases + +if ($V == 1) { + print "0\nas 1 is smaller than the smallest prime.\n"; + exit; +} + +if ($V == 2) { + print "1\nas 2 is the smallest prime.\n"; + exit; +} + +if ($V == 4) { + print "2\nas 2 + 2 = 4 and 4 is not a prime.\n"; + exit; +} + +# normal cases +sub setoddprime { + for my $p (3..$V) {$oddprime{$p} = 1 if is_prime($p);} +} + + +if ($V % 2 == 0) { + print "2\n"; + setoddprime; + for (keys %oddprime) { + if ($oddprime{$V-$_}) { + print "as $_", " + ", $V-$_," = $V.\n" ; + last; + } + } +} +else { + setoddprime; + if ($oddprime{$V}) { + print "1\nas $V is a prime.\n"; + } + elsif ($oddprime{$V-2}) { + print "2\nas 2 + " ,$V-2, " = $V\nand $V is not a prime.\n" , + } + else { + print "3\n"; + for (keys %oddprime) { + if ($oddprime{$V-3-$_}) { + print "3 + $_", " + ", $V-$_-3," = $V .\n"; + print "The answer can't be 1 or 2 because", + " neither ", $V-2 ," nor $V is a prime; and\n", + " there are no even primes except 2\n", + " (two odd primes sum to an even number).\n"; + last; + } + } + } +} + diff --git a/challenge-076/cheok-yin-fung/perl/ch-2.pl b/challenge-076/cheok-yin-fung/perl/ch-2.pl new file mode 100644 index 0000000000..1642231842 --- /dev/null +++ b/challenge-076/cheok-yin-fung/perl/ch-2.pl @@ -0,0 +1,189 @@ +# Perl Weekly Challenge #076 Task 2 Word Search +# task statements: +# 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. +# Usage: ch-2.pl gridfile dictfile + +use strict; +use warnings; +use Data::Dumper; + +my @matrix; +my @dictwords; +my $gridfile; +my $dictfile; + +if ($ARGV[1]) { + $gridfile = $ARGV[0]; + $dictfile = $ARGV[1]; +} +else { + $gridfile = "pwc076grid"; + $dictfile = "1000engwords.txt"; +} + +open GRID, $gridfile or die "no such text file for the grid: $gridfile"; +open DICT, $dictfile or die "no such text file for the dictionary: $dictfile"; + +#read words from dictionary file +foreach (<DICT>) { + my @temp; + if ($_ =~ /^[a-z]+$/) { + s/\s/\r/g; + s/\s//g; + push @temp, $_ ; + } + for my $line (@temp) { + push @dictwords, $line; + } +} + +@dictwords = sort {$a cmp $b} @dictwords; + +# read the grid from grid file +my $k = 0; +for (<GRID>) { + chomp; + if ($_ ne "") { + @{$matrix[$k]} = split " ", $_; + $k++; + } +} + +my $xlen = scalar @{$matrix[0]}; +my $ylen = scalar @matrix; + +# some subroutines for manipulating the lines on the grid +# ============== + +sub joinline { + return lc(join "", @_); +} + +sub reversestring { + return join "", reverse (split //, $_[0]); +} + + +# horizontal and vertical lines +# ============= + +my @rowline, my @colline, my @urighttolleft; +my @diagonal; + +for my $i (0..$ylen-1) { + $rowline[$i*2] = joinline @{$matrix[$i]}; + $rowline[$i*2+1] = joinline reverse @{$matrix[$i]}; +} + +for my $j (0..$xlen-1) { + $colline[$j*2] = joinline( map {${$matrix[$_]}[$j]} (0..$ylen-1) ); + $colline[$j*2+1] = reversestring $colline[$j*2]; +} +# =========================== + + +# diagonal +# ============================== +sub find_diagonal { + my @mat = @{$_[0]}; + my @ulefttolright = (); + my @extra_dia = (); + my $t_xlen = scalar @{$mat[0]}; + my $t_ylen = scalar @mat; + my $t_limit = ($t_xlen > $t_ylen) ? $t_ylen : $t_xlen; + my $t_diff = ($t_xlen > $t_ylen) ? $t_xlen - $t_ylen : $t_ylen - $t_xlen; + + if ($t_xlen >= $t_ylen) { + for my $c (0..$t_diff) { + $ulefttolright[$c*2] = joinline + map {${$mat[$_]}[$c+$_]} (0..$t_ylen-1) ; + $ulefttolright[$c*2+1] = reversestring $ulefttolright[$c*2]; + } + + for my $d (0..$t_limit-2) { + $extra_dia[$d*4] = joinline + map {${$mat[$_]}[$t_diff+$d+1+$_]} (0..$t_limit-$d-2) ; + $extra_dia[$d*4+1] = reversestring $extra_dia[$d*4]; + $extra_dia[$d*4+2] = joinline + map {${$mat[$d+1+$_]}[$_]} (0..$t_limit-$d-2) ; + $extra_dia[$d*4+3] = reversestring $extra_dia[$d*4+2]; + } + } + else { + for my $c (0..$t_diff) { + $ulefttolright[$c*2] = joinline + map {${$mat[$_+$c]}[$_]} (0..$t_xlen-1) ; + $ulefttolright[$c*2+1] = reversestring $ulefttolright[$c*2]; + } + for my $d (0..$t_limit-2) { + $extra_dia[$d*4] = joinline + map {${$mat[$t_diff+$d+1+$_]}[$_]} (0..$t_limit-$d-2) ; + $extra_dia[$d*4+1] = reversestring $extra_dia[$d*4]; + $extra_dia[$d*4+2] = joinline + map {${$mat[$_]}[$d+1+$_]} (0..$t_limit-$d-2) ; + $extra_dia[$d*4+3] = reversestring $extra_dia[$d*4+2]; + } + + + } + return (@ulefttolright, @extra_dia); +} +# ============================= + + +# antidiagonal +# ============================== + +sub vertical_reflection { + my @mat = @{$_[0]}; + my @newmat; + my $t_xlen = scalar @{$mat[0]}; + my $t_ylen = scalar @mat; + for my $i (0..$t_ylen-1) { + @{$newmat[$i]} = (); + for my $j (0..$t_xlen-1) { + ${$newmat[$i]}[$j] = ${$mat[$i]}[-1-$j]; + } + } + return @newmat; +} + + +@diagonal = find_diagonal(\@matrix); +my @newmatrix = vertical_reflection(\@matrix) ; +my @antidiagonal = find_diagonal( \@newmatrix); +# =========================== + + +# main dish: + +my %unique; + +for my $word (@dictwords) { + for (@rowline,@colline,@diagonal,@antidiagonal) { + if (defined $_) { + if ($_ =~ /$word/ && not($unique{$word}) ) { + print $word, " "; + $unique{$word} = 1; + } + } + } +} + +print "\n"; + +# grid: as given in task statement +# word list: +# https://www.oxfordlearnersdictionaries.com/wordlists/oxford3000-5000 +# words with length more than or equal to 5 in the grid: +# align broad constitution depart enter midst social virus +# +# Running time +# real 0m0.254s +# user 0m0.249s +# sys 0m0.004s + |