From 6fd8db0664e939622da59a3aa7aff38d3da39519 Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Fri, 4 Sep 2020 09:28:22 +0800 Subject: for challenge #076 --- challenge-076/cheok-yin-fung/perl/ch-1.pl | 77 ++++++++++++ challenge-076/cheok-yin-fung/perl/ch-2.pl | 188 ++++++++++++++++++++++++++++++ 2 files changed, 265 insertions(+) create mode 100644 challenge-076/cheok-yin-fung/perl/ch-1.pl create mode 100644 challenge-076/cheok-yin-fung/perl/ch-2.pl 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..51275f8742 --- /dev/null +++ b/challenge-076/cheok-yin-fung/perl/ch-1.pl @@ -0,0 +1,77 @@ +# 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 conjecture is verified +# for n < 4 000 000 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.\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" ; + } + } +} +else { + setoddprime; + if ($oddprime{$V}) { + print "1\nas $V is a prime.\n"; + } + elsif ($oddprime{$V-2} == 1) { + print "2\nas 2 + " ,$V-2, " = $V.\n" , + } + else { + print "3\n"; + for (keys %oddprime) { + if ($oddprime{$V-3-$_}) { + print "as 3 + $_", " + ", $V-$_-3," = $V.\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..28c1dc62d9 --- /dev/null +++ b/challenge-076/cheok-yin-fung/perl/ch-2.pl @@ -0,0 +1,188 @@ +# Perl Weekly Challenge #076 Task 2 +# Word Search +# task statement: +# 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 () { + 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 () { + 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 { + my @temp = @_; + @temp = grep {defined($_)} @temp; + # without the `grep {defined($_)}`, the program crashes + # while the input grid is a vertically longer rectangle. + # I haven't figured out why. Aug 3rd 2020 + return lc(join "", @temp); +} + +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 $xlen_t = scalar @{$mat[0]}; + my $ylen_t = scalar @mat; + $ulefttolright[0] = joinline map {${$mat[$_]}[$_]} (0..$ylen_t-1); + $ulefttolright[1] = reversestring $ulefttolright[0]; + + if ($xlen_t >= $ylen_t) { + for my $c (0..$xlen_t-$ylen_t) { + $ulefttolright[$c*2] = joinline + map {${$mat[$_]}[$c+$_]} (0..$ylen_t-1) ; + $ulefttolright[$c*2+1] = reversestring $ulefttolright[$c*2]; + } + + for my $c (0..$ylen_t-2) { + $extra_dia[$c*4] = joinline + map {${$mat[$_]}[$xlen_t-$ylen_t+$c+$_]} (0..$ylen_t-$c-1) ; + $extra_dia[$c*4+1] = reversestring $extra_dia[$c*4]; + $extra_dia[$c*4+2] = joinline + map {${$mat[$c+$_]}[$_]} (0..$ylen_t-$c-1) ; + $extra_dia[$c*4+3] = reversestring $extra_dia[$c*4+2]; + } + } + else { + for my $c (0..$ylen_t-$xlen_t) { + $ulefttolright[$c*2] = joinline + map {${$mat[$_+$c]}[$_]} (0..$xlen_t-1) ; + $ulefttolright[$c*2+1] = reversestring $ulefttolright[$c*2]; + } + for my $c (0..$xlen_t-2) { + $extra_dia[$c*4] = joinline + map {${$mat[$ylen_t-$xlen_t+$c+$_]}[$_]} (0..$xlen_t-$c-1) ; + $extra_dia[$c*4+1] = reversestring $extra_dia[$c*4]; + $extra_dia[$c*4+2] = joinline + map {${$mat[$_]}[$c+$_]} (0..$xlen_t-$c-1) ; + $extra_dia[$c*4+3] = reversestring $extra_dia[$c*4+2]; + } + } + return (@ulefttolright, @extra_dia); +} +# ============================= + + +# antidiagonal +# ============================== + +sub vertical_reflection { + my @mat = @{$_[0]}; + my @newmat; + my $xlen_t = scalar @{$mat[0]}; + my $ylen_t = scalar @mat; + for my $i (0..$xlen_t-1) { + @{$newmat[$i]} = (); + for my $j (0..$ylen_t-1) { + ${$newmat[$i]}[$j] = ${$mat[$i]}[$ylen_t-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 (not($unique{$word}) && defined($_) && $_ =~ /$word/ ) { + print $word, " "; + $unique{$word} = 1; + } + } +} +print "\n"; + + +# grid: as given in task statement +# words 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.314s +# user 0m0.302s +# sys 0m0.012s -- cgit From b3e1048f409a0e31e6f8b9ca15de21c12c42a33e Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Sat, 5 Sep 2020 13:02:32 +0800 Subject: improvement --- challenge-076/cheok-yin-fung/perl/ch-1.pl | 15 +++-- challenge-076/cheok-yin-fung/perl/ch-2.pl | 105 +++++++++++++++--------------- 2 files changed, 63 insertions(+), 57 deletions(-) diff --git a/challenge-076/cheok-yin-fung/perl/ch-1.pl b/challenge-076/cheok-yin-fung/perl/ch-1.pl index 51275f8742..c790d2c0e5 100644 --- a/challenge-076/cheok-yin-fung/perl/ch-1.pl +++ b/challenge-076/cheok-yin-fung/perl/ch-1.pl @@ -6,7 +6,7 @@ # Usage: ch-1.pl $N # Given the Goldbach's conjecture conjecture is verified -# for n < 4 000 000 000 000 000 000 000 000 +# for n < 4 000 000 000 000 000 000 # ( source: mathworld.wolfram.com ) use strict; @@ -37,7 +37,7 @@ if ($V == 2) { } if ($V == 4) { - print "2\nas 2 + 2 = 4.\n"; + print "2\nas 2 + 2 = 4 and 4 is not a prime.\n"; exit; } @@ -53,6 +53,7 @@ if ($V % 2 == 0) { for (keys %oddprime) { if ($oddprime{$V-$_}) { print "as $_", " + ", $V-$_," = $V.\n" ; + last; } } } @@ -61,14 +62,18 @@ else { if ($oddprime{$V}) { print "1\nas $V is a prime.\n"; } - elsif ($oddprime{$V-2} == 1) { - print "2\nas 2 + " ,$V-2, " = $V.\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 "as 3 + $_", " + ", $V-$_-3," = $V.\n"; + 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 index 28c1dc62d9..1642231842 100644 --- a/challenge-076/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-076/cheok-yin-fung/perl/ch-2.pl @@ -1,8 +1,10 @@ -# Perl Weekly Challenge #076 Task 2 -# Word Search -# task statement: -# 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. -# +# 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; @@ -58,12 +60,7 @@ my $ylen = scalar @matrix; # ============== sub joinline { - my @temp = @_; - @temp = grep {defined($_)} @temp; - # without the `grep {defined($_)}`, the program crashes - # while the input grid is a vertically longer rectangle. - # I haven't figured out why. Aug 3rd 2020 - return lc(join "", @temp); + return lc(join "", @_); } sub reversestring { @@ -93,43 +90,45 @@ for my $j (0..$xlen-1) { # ============================== sub find_diagonal { my @mat = @{$_[0]}; - my @ulefttolright; - my @extra_dia; - my $xlen_t = scalar @{$mat[0]}; - my $ylen_t = scalar @mat; - $ulefttolright[0] = joinline map {${$mat[$_]}[$_]} (0..$ylen_t-1); - $ulefttolright[1] = reversestring $ulefttolright[0]; - - if ($xlen_t >= $ylen_t) { - for my $c (0..$xlen_t-$ylen_t) { - $ulefttolright[$c*2] = joinline - map {${$mat[$_]}[$c+$_]} (0..$ylen_t-1) ; - $ulefttolright[$c*2+1] = reversestring $ulefttolright[$c*2]; + 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 $c (0..$ylen_t-2) { - $extra_dia[$c*4] = joinline - map {${$mat[$_]}[$xlen_t-$ylen_t+$c+$_]} (0..$ylen_t-$c-1) ; - $extra_dia[$c*4+1] = reversestring $extra_dia[$c*4]; - $extra_dia[$c*4+2] = joinline - map {${$mat[$c+$_]}[$_]} (0..$ylen_t-$c-1) ; - $extra_dia[$c*4+3] = reversestring $extra_dia[$c*4+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..$ylen_t-$xlen_t) { + for my $c (0..$t_diff) { $ulefttolright[$c*2] = joinline - map {${$mat[$_+$c]}[$_]} (0..$xlen_t-1) ; + map {${$mat[$_+$c]}[$_]} (0..$t_xlen-1) ; $ulefttolright[$c*2+1] = reversestring $ulefttolright[$c*2]; } - for my $c (0..$xlen_t-2) { - $extra_dia[$c*4] = joinline - map {${$mat[$ylen_t-$xlen_t+$c+$_]}[$_]} (0..$xlen_t-$c-1) ; - $extra_dia[$c*4+1] = reversestring $extra_dia[$c*4]; - $extra_dia[$c*4+2] = joinline - map {${$mat[$_]}[$c+$_]} (0..$xlen_t-$c-1) ; - $extra_dia[$c*4+3] = reversestring $extra_dia[$c*4+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); } @@ -142,12 +141,12 @@ sub find_diagonal { sub vertical_reflection { my @mat = @{$_[0]}; my @newmat; - my $xlen_t = scalar @{$mat[0]}; - my $ylen_t = scalar @mat; - for my $i (0..$xlen_t-1) { + my $t_xlen = scalar @{$mat[0]}; + my $t_ylen = scalar @mat; + for my $i (0..$t_ylen-1) { @{$newmat[$i]} = (); - for my $j (0..$ylen_t-1) { - ${$newmat[$i]}[$j] = ${$mat[$i]}[$ylen_t-1-$j]; + for my $j (0..$t_xlen-1) { + ${$newmat[$i]}[$j] = ${$mat[$i]}[-1-$j]; } } return @newmat; @@ -160,29 +159,31 @@ my @antidiagonal = find_diagonal( \@newmatrix); # =========================== - # main dish: my %unique; for my $word (@dictwords) { - for (@rowline,@colline,@diagonal,@antidiagonal) { - if (not($unique{$word}) && defined($_) && $_ =~ /$word/ ) { + for (@rowline,@colline,@diagonal,@antidiagonal) { + if (defined $_) { + if ($_ =~ /$word/ && not($unique{$word}) ) { print $word, " "; $unique{$word} = 1; } + } } } -print "\n"; +print "\n"; # grid: as given in task statement -# words list: +# 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.314s -# user 0m0.302s -# sys 0m0.012s +# real 0m0.254s +# user 0m0.249s +# sys 0m0.004s + -- cgit From 3c2763d12f6d643dd71d9d48f80907f59d31de37 Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Sun, 6 Sep 2020 00:26:14 +0800 Subject: add blogpost --- challenge-076/cheok-yin-fung/perl/BLOG.txt | 1 + challenge-076/cheok-yin-fung/perl/ch-1.pl | 2 +- 2 files changed, 2 insertions(+), 1 deletion(-) create mode 100644 challenge-076/cheok-yin-fung/perl/BLOG.txt 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 index c790d2c0e5..b5c2260f6e 100644 --- a/challenge-076/cheok-yin-fung/perl/ch-1.pl +++ b/challenge-076/cheok-yin-fung/perl/ch-1.pl @@ -5,7 +5,7 @@ # required, whose summation gives you $N. # Usage: ch-1.pl $N -# Given the Goldbach's conjecture conjecture is verified +# Given the Goldbach's conjecture is verified # for n < 4 000 000 000 000 000 000 # ( source: mathworld.wolfram.com ) -- cgit