From 33e4df55e2e63dd53955f70b1e1defbcf4517dbe Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Thu, 17 Mar 2022 09:05:28 +0800 Subject: TWC 156 Task 2 --- challenge-156/cheok-yin-fung/perl/ch-2.pl | 90 +++++++++++++++++++++++++++++++ 1 file changed, 90 insertions(+) create mode 100644 challenge-156/cheok-yin-fung/perl/ch-2.pl diff --git a/challenge-156/cheok-yin-fung/perl/ch-2.pl b/challenge-156/cheok-yin-fung/perl/ch-2.pl new file mode 100644 index 0000000000..b61f0dd8a2 --- /dev/null +++ b/challenge-156/cheok-yin-fung/perl/ch-2.pl @@ -0,0 +1,90 @@ +#!/usr/bin/perl +# The Weekly Challenge 156 +# Task 2 Weired Number +# references: +# https://www.geeksforgeeks.org/subset-sum-problem-dp-25/ + +use v5.22.0; +use warnings; +use List::Util qw/uniqint/; +use Math::Prime::Util qw/next_prime/; + +if (defined($ARGV[0])) { + my $N = $ARGV[0]; + say(weird($N) ? "$N is a weird number." : "$N is not weird."); +} + + + +sub weird { + my $num = $_[0]; + my @divisor = proper_factors($num); + return subset_sum($num, [@divisor]); +} + + + +sub factorization { + # trivial prime factorization + my $num = $_[0]; + my @prime_factors; + my $prime = 2; + while ($num != 1) { + if ($num % $prime == 0) { + $num /= $prime; + push @prime_factors, $prime; + } + else { + $prime = next_prime($prime); + } + } + return @prime_factors; +} + + + +sub proper_factors { + my @prime_factors = factorization($_[0]); + my @pf = (1); + while (scalar @prime_factors > 0) { + my $n = shift @prime_factors; + my @temp_pf = @pf; + push @pf, $n*$_ for @temp_pf; + } + @pf = sort {$a<=>$b} uniqint @pf; + pop @pf; # remove the largest factor -> the number itself + return @pf; +} + + + +sub subset_sum { + # dynamic programming + my $sum = $_[0]; + my @A = $_[1]->@*; + + my $DP; + $DP->[0][$_] = 1 for (0..scalar @A); + $DP->[$_][0] = undef for (1..$sum); + for my $s (1..$sum) { + for my $k (1..scalar @A) { + $DP->[$s][$k] = $DP->[$s][$k-1]; + if ($s >= $A[$k-1]) { + $DP->[$s][$k] = $DP->[$s][$k] + || + $DP->[$s-$A[$k-1]][$k-1]; + } + } + } + return !$DP->[$sum][scalar @A]; +} + + + +use Test::More tests => 6; +ok !weird(12), "n=12"; +ok weird(70), "n=70"; +ok !weird(100), "n=100"; +ok weird(4030), "n=4030 (term from wikipedia)"; +ok !weird(6000), "n=6000"; +ok weird(9272), "n=9272 (term from wikipedia)"; -- cgit From dda6cbc53bc7592cca40c5f45cf5c5fcff1a34b9 Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Thu, 17 Mar 2022 09:26:23 +0800 Subject: TWC 156 Task 2 (2nd commit) --- challenge-156/cheok-yin-fung/perl/ch-2.pl | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) diff --git a/challenge-156/cheok-yin-fung/perl/ch-2.pl b/challenge-156/cheok-yin-fung/perl/ch-2.pl index b61f0dd8a2..5feecf02dc 100644 --- a/challenge-156/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-156/cheok-yin-fung/perl/ch-2.pl @@ -6,7 +6,7 @@ use v5.22.0; use warnings; -use List::Util qw/uniqint/; +use List::Util qw/uniqint sum/; use Math::Prime::Util qw/next_prime/; if (defined($ARGV[0])) { @@ -18,8 +18,9 @@ if (defined($ARGV[0])) { sub weird { my $num = $_[0]; - my @divisor = proper_factors($num); - return subset_sum($num, [@divisor]); + my @proper_divisors = proper_divisors($num); + return 0 if (sum @proper_divisors) < $num; + return !subset_sum($num, [@proper_divisors]); } @@ -43,7 +44,7 @@ sub factorization { -sub proper_factors { +sub proper_divisors { my @prime_factors = factorization($_[0]); my @pf = (1); while (scalar @prime_factors > 0) { @@ -76,7 +77,7 @@ sub subset_sum { } } } - return !$DP->[$sum][scalar @A]; + return $DP->[$sum][scalar @A]; } -- cgit From e194c1e13f183c7f84882a8bb44d8b543c642bef Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Thu, 17 Mar 2022 11:16:09 +0800 Subject: typo --- challenge-156/cheok-yin-fung/perl/ch-2.pl | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/challenge-156/cheok-yin-fung/perl/ch-2.pl b/challenge-156/cheok-yin-fung/perl/ch-2.pl index 5feecf02dc..0410a55139 100644 --- a/challenge-156/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-156/cheok-yin-fung/perl/ch-2.pl @@ -1,8 +1,9 @@ #!/usr/bin/perl # The Weekly Challenge 156 -# Task 2 Weired Number +# Task 2 Weird Number # references: # https://www.geeksforgeeks.org/subset-sum-problem-dp-25/ +# Usage: $ ch-2.pl $N use v5.22.0; use warnings; @@ -83,8 +84,8 @@ sub subset_sum { use Test::More tests => 6; -ok !weird(12), "n=12"; -ok weird(70), "n=70"; +ok !weird(12), "n=12 (Example 1)"; +ok weird(70), "n=70 (Example 2)"; ok !weird(100), "n=100"; ok weird(4030), "n=4030 (term from wikipedia)"; ok !weird(6000), "n=6000"; -- cgit From 4f9000fbb6d750dec4d1ff5b9c9a42e7085a5e13 Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Thu, 17 Mar 2022 16:53:36 +0800 Subject: edge case n=1 --- challenge-156/cheok-yin-fung/perl/ch-2.pl | 1 + 1 file changed, 1 insertion(+) diff --git a/challenge-156/cheok-yin-fung/perl/ch-2.pl b/challenge-156/cheok-yin-fung/perl/ch-2.pl index 0410a55139..ef83ce1222 100644 --- a/challenge-156/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-156/cheok-yin-fung/perl/ch-2.pl @@ -19,6 +19,7 @@ if (defined($ARGV[0])) { sub weird { my $num = $_[0]; + return 0 if $num == 1; my @proper_divisors = proper_divisors($num); return 0 if (sum @proper_divisors) < $num; return !subset_sum($num, [@proper_divisors]); -- cgit From 5efb41abe8d0f779ffbfa6de992e61b2793d8d9a Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Thu, 17 Mar 2022 17:03:42 +0800 Subject: better array name for inside &proper_divisors --- challenge-156/cheok-yin-fung/perl/ch-2.pl | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/challenge-156/cheok-yin-fung/perl/ch-2.pl b/challenge-156/cheok-yin-fung/perl/ch-2.pl index ef83ce1222..7dccf5706e 100644 --- a/challenge-156/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-156/cheok-yin-fung/perl/ch-2.pl @@ -48,15 +48,15 @@ sub factorization { sub proper_divisors { my @prime_factors = factorization($_[0]); - my @pf = (1); + my @pd = (1); while (scalar @prime_factors > 0) { my $n = shift @prime_factors; - my @temp_pf = @pf; - push @pf, $n*$_ for @temp_pf; + my @temp_pd = @pd; + push @pd, $n*$_ for @temp_pd; } - @pf = sort {$a<=>$b} uniqint @pf; - pop @pf; # remove the largest factor -> the number itself - return @pf; + @pd = sort {$a<=>$b} uniqint @pd; + pop @pd; # remove the largest factor -> the number itself + return @pd; } -- cgit From 8b784c4f595a470f4b01639fe4bbd1cadfd3cb36 Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Fri, 18 Mar 2022 19:59:20 +0800 Subject: Task 1 --- challenge-156/cheok-yin-fung/perl/ch-1.pl | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) create mode 100644 challenge-156/cheok-yin-fung/perl/ch-1.pl diff --git a/challenge-156/cheok-yin-fung/perl/ch-1.pl b/challenge-156/cheok-yin-fung/perl/ch-1.pl new file mode 100644 index 0000000000..82b1555505 --- /dev/null +++ b/challenge-156/cheok-yin-fung/perl/ch-1.pl @@ -0,0 +1,27 @@ +#!/usr/bin/perl +use v5.22.0; +use warnings; +use Math::Prime::Util qw 'is_prime'; + +my $N = $ARGV[0] || 10; + +my $count = 0; + +for (1..3*$N) { + if (pernicious_simple($_)) { + say $_; + $count++; + } + last if $count == $N; +} + +die "bound too small\n" if $count < $N; + + + +sub pernicious_simple { + my $num = $_[0]; + my $count_one = scalar + grep { $_ == 1 } split "", sprintf("%b",$num); + return is_prime($count_one) ? 1 : 0; +} -- cgit From 6949f7b6c244ef95a0a3fa1f9d916ac8133831ef Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Sat, 19 Mar 2022 00:42:02 +0800 Subject: Task 1 --- challenge-156/cheok-yin-fung/blog.txt | 1 + challenge-156/cheok-yin-fung/perl/ch-1.pl | 37 +++++++++++++++++++------------ 2 files changed, 24 insertions(+), 14 deletions(-) create mode 100644 challenge-156/cheok-yin-fung/blog.txt diff --git a/challenge-156/cheok-yin-fung/blog.txt b/challenge-156/cheok-yin-fung/blog.txt new file mode 100644 index 0000000000..96fd21704b --- /dev/null +++ b/challenge-156/cheok-yin-fung/blog.txt @@ -0,0 +1 @@ +https://E7-87-83.github.io/coding/challenge_156.html diff --git a/challenge-156/cheok-yin-fung/perl/ch-1.pl b/challenge-156/cheok-yin-fung/perl/ch-1.pl index 82b1555505..bbf0bbfbf8 100644 --- a/challenge-156/cheok-yin-fung/perl/ch-1.pl +++ b/challenge-156/cheok-yin-fung/perl/ch-1.pl @@ -1,27 +1,36 @@ #!/usr/bin/perl use v5.22.0; use warnings; -use Math::Prime::Util qw 'is_prime'; +use Math::Prime::Util qw /next_prime/; +use Algorithm::Combinatorics qw/combinations/; my $N = $ARGV[0] || 10; -my $count = 0; +my $list_size = $N; +my $ub = 3*$N; -for (1..3*$N) { - if (pernicious_simple($_)) { - say $_; - $count++; +my @pern_num = (); + +for my $k (2..$ub) { + my $prime = 2; + while ($prime <= $k) { + my @weight_k_pern_num = (); + my $iter = combinations([1..$k-1], $prime-1); + while (my $c = $iter->next) { + my @ch = ((1), (0) x ($k-1)); + $ch[$_] = 1 for @{$c}; + my $new_pern_num = oct("0b".(join "", @ch)); + push @weight_k_pern_num, $new_pern_num; + } + push @pern_num, @weight_k_pern_num; + $prime = next_prime($prime); } - last if $count == $N; + last if scalar @pern_num >= $N; } -die "bound too small\n" if $count < $N; + +@pern_num = sort {$a<=>$b} @pern_num; +say join ", ", @pern_num[0..$N-1]; -sub pernicious_simple { - my $num = $_[0]; - my $count_one = scalar - grep { $_ == 1 } split "", sprintf("%b",$num); - return is_prime($count_one) ? 1 : 0; -} -- cgit From 511f82b397acb52cc795b8be8be4c317bcc700fe Mon Sep 17 00:00:00 2001 From: E7-87-83 Date: Sun, 20 Mar 2022 14:40:21 +0800 Subject: fix everywhere --- challenge-156/cheok-yin-fung/perl/ch-1.pl | 10 +++++++--- challenge-156/cheok-yin-fung/perl/ch-2.pl | 2 +- 2 files changed, 8 insertions(+), 4 deletions(-) diff --git a/challenge-156/cheok-yin-fung/perl/ch-1.pl b/challenge-156/cheok-yin-fung/perl/ch-1.pl index bbf0bbfbf8..24941c76d7 100644 --- a/challenge-156/cheok-yin-fung/perl/ch-1.pl +++ b/challenge-156/cheok-yin-fung/perl/ch-1.pl @@ -1,4 +1,8 @@ #!/usr/bin/perl +# The Weekly Challenge 156 +# Task 1 Pernicious Number +# Usage: +# ch-1.pl [$N, for an output with the first $N pernicious number] use v5.22.0; use warnings; use Math::Prime::Util qw /next_prime/; @@ -14,15 +18,15 @@ my @pern_num = (); for my $k (2..$ub) { my $prime = 2; while ($prime <= $k) { - my @weight_k_pern_num = (); + my @length_k_weight_p_num = (); my $iter = combinations([1..$k-1], $prime-1); while (my $c = $iter->next) { my @ch = ((1), (0) x ($k-1)); $ch[$_] = 1 for @{$c}; my $new_pern_num = oct("0b".(join "", @ch)); - push @weight_k_pern_num, $new_pern_num; + push @length_k_weight_p_num, $new_pern_num; } - push @pern_num, @weight_k_pern_num; + push @pern_num, @length_k_weight_p_num; $prime = next_prime($prime); } last if scalar @pern_num >= $N; diff --git a/challenge-156/cheok-yin-fung/perl/ch-2.pl b/challenge-156/cheok-yin-fung/perl/ch-2.pl index 7dccf5706e..364e15a9c9 100644 --- a/challenge-156/cheok-yin-fung/perl/ch-2.pl +++ b/challenge-156/cheok-yin-fung/perl/ch-2.pl @@ -1,7 +1,7 @@ #!/usr/bin/perl # The Weekly Challenge 156 # Task 2 Weird Number -# references: +# references on subset sum: # https://www.geeksforgeeks.org/subset-sum-problem-dp-25/ # Usage: $ ch-2.pl $N -- cgit