From df7b8cd1780e7e184f0196f5de80fae5f4438f3d Mon Sep 17 00:00:00 2001 From: Bob Lied Date: Tue, 27 Jun 2023 08:01:03 -0500 Subject: Count Primes with sieve --- challenge-223/bob-lied/perl/ch-1.pl | 65 +++++++++++++++++++++++++++++++++++++ 1 file changed, 65 insertions(+) create mode 100644 challenge-223/bob-lied/perl/ch-1.pl diff --git a/challenge-223/bob-lied/perl/ch-1.pl b/challenge-223/bob-lied/perl/ch-1.pl new file mode 100644 index 0000000000..de9a6d4625 --- /dev/null +++ b/challenge-223/bob-lied/perl/ch-1.pl @@ -0,0 +1,65 @@ +#!/usr/bin/env perl +# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu: +#============================================================================= +# ch-1.pl Perl Weekly Challenge 223 Task1 Count Primes +#============================================================================= +# Copyright (c) 2023, Bob Lied +#============================================================================= +# You are given a positive integer, $n. +# Write a script to find the total count of primes less than or equal to the +# given integer. +# Example 1 Input: $n = 10 Output: 4 +# Since there are 4 primes (2,3,5,7) less than or equal to 10. +# Example 2 Input: $n = 1 Output: 0 +# Example 3 Input: $n = 20 Output: 8 +# Since there are 4 primes (2,3,5,7,11,13,17,19) less than or equal to 20. +#============================================================================= + +use v5.36; + +use builtin qw(true false); no warnings "experimental::builtin"; + +use Getopt::Long; +my $Verbose = 0; +my $DoTest = 0; + +GetOptions("test" => \$DoTest, "verbose" => \$Verbose); +exit(!runTest()) if $DoTest; + +sub sieve($n) +{ + my @prime = (false, false, true, (true,false) x (($n-1)/2) ); + + for (my $p = 3; $p*$p <= $n; $p++ ) + { + if ( $prime[$p] ) + { + for (my $i = $p*$p ; $i <= $n ; $i += $p ) + { + $prime[$i] = false; + } + } + } + my $count = grep { $prime[$_] } 2 .. $n+1; +} + +sub countPrimes($n) +{ + return ( $n < 2 ? 0 : sieve($n) ); +} + +sub runTest +{ + use Test2::V0; + + is( countPrimes( 10), 4, "Example 1"); + is( countPrimes( 1), 0, "Example 2"); + is( countPrimes( 20), 8, "Example 3"); + is( countPrimes( 2), 1, "p 2"); + is( countPrimes( 3), 2, "p 3"); + is( countPrimes( 11), 5, "p 11"); + is( countPrimes( 100), 25, "p 100"); + is( countPrimes(1000), 168, "p 1000"); + + done_testing; +} -- cgit From 691757689ad317705f7a5593f31037d867ce4d15 Mon Sep 17 00:00:00 2001 From: Bob Lied Date: Thu, 6 Jul 2023 07:29:47 -0500 Subject: Week 223 solutions --- challenge-223/bob-lied/README | 6 +-- challenge-223/bob-lied/perl/ch-2.pl | 84 +++++++++++++++++++++++++++++++++++++ 2 files changed, 87 insertions(+), 3 deletions(-) create mode 100644 challenge-223/bob-lied/perl/ch-2.pl diff --git a/challenge-223/bob-lied/README b/challenge-223/bob-lied/README index 169a7cc554..250ec5af49 100644 --- a/challenge-223/bob-lied/README +++ b/challenge-223/bob-lied/README @@ -1,4 +1,4 @@ -Solutions to weekly challenge 222 by Bob Lied +Solutions to weekly challenge 223 by Bob Lied -https://perlweeklychallenge.222org/blog/perl-weekly-challenge-222/ -https://github.com/boblied/perlweeklychallenge-222club/tree/master/challenge-222/bob-lied +https://perlweeklychallenge.223org/blog/perl-weekly-challenge-223/ +https://github.com/boblied/perlweeklychallenge-223club/tree/master/challenge-223/bob-lied diff --git a/challenge-223/bob-lied/perl/ch-2.pl b/challenge-223/bob-lied/perl/ch-2.pl new file mode 100644 index 0000000000..216379cbd7 --- /dev/null +++ b/challenge-223/bob-lied/perl/ch-2.pl @@ -0,0 +1,84 @@ +#!/usr/bin/env perl +# vim:set ts=4 sw=4 sts=4 et ai wm=0 nu: +#============================================================================= +# ch-2.pl Perl Weekly Challenge 223 Task 2 Box Coins +#============================================================================= +# Copyright (c) 2023, Bob Lied +#============================================================================= +# You are given an array representing box coins, @box. +# Write a script to collect the maximum coins until you took out all boxes. +# If we pick box[i] then we collect the coins $box[i-1] * $box[i] * $box[i+1]. +# If $box[i+1] or $box[i-1] is out of bound then treat it as 1 coin. +# Example 1: Input: @box = (3, 1, 5, 8) +# Output: 167 +# Step 1: pick box [i=1] and collected coins 3 * 1 * 5 => 15. +# Boxes available (3, 5, 8). +# Step 2: pick box [i=1] and collected coins 3 * 5 * 8 => 120. +# Boxes available (3, 8). +# Step 3: pick box [i=0] and collected coins 1 * 3 * 8 => 24. +# Boxes available (8). +# Step 4: pick box [i=0] and collected coins 1 * 8 * 1 => 8. +# No more box available. +# Example 2: Input: @box = (1, 5) +# Output: 10 +# Step 1: pick box [i=0] and collected coins 1 * 1 * 5 => 5. +# Boxes available (5). +# Step 2: pick box [i=0] and collected coins 1 * 5 * 1 => 5 +# No more box available. +#============================================================================= + +use v5.36; + +use Getopt::Long; my $Verbose = 0; +my $DoTest = 0; + +GetOptions("test" => \$DoTest, "verbose" => \$Verbose); +exit(!runTest()) if $DoTest; + +my $Max = 0; +sub _boxCoin($box, $total, $indent) +{ + # Assumes there is a 1 on each end + return unless $box->$#* > 1; + my $last = $box->$#*; + + for my $coin ( 1 .. $last-1 ) + { + my $score = $box->[$coin-1] * $box->[$coin] * $box->[$coin+1]; + + my $newTotal = $total + $score; + $Max = $newTotal if $newTotal > $Max; + + say "${indent}[@$box] [$coin]=$box->[$coin], score=$score, total=", $newTotal if $Verbose; + + _boxCoin( [ $box->@[0..$coin-1], $box->@[$coin+1 .. $last] ], $total+$score, "$indent " ); + } +} + +sub boxCoins($box) +{ + $Max = 0; + # Put a 1 on each end to handle edges + _boxCoin( [ 1, $box->@*, 1 ], 0, "" ); + return $Max; +} + +sub runTest +{ + use Test2::V0; + + is( boxCoins( [3,1,5,8] ), 167, "Example 1"); + is( boxCoins( [1,5 ] ), 10, "Example 2"); + is( boxCoins( [ ] ), 0, "Empty list"); + is( boxCoins( [ 7 ] ), 7, "Singleton"); + is( boxCoins( [1,2 ] ), 4, "1,2"); + is( boxCoins( [2,1 ] ), 4, "2,1"); + is( boxCoins( [1,2,3 ] ), 12, "1,2,3"); + is( boxCoins( [3,2,1 ] ), 12, "3,2,1"); + is( boxCoins( [3,1,2 ] ), 15, "3,1,2"); + is( boxCoins( [1,2,3,4] ), 40, "1,2,3,4"); + is( boxCoins( [4,3,2,1] ), 40, "4,3,2,1"); + is( boxCoins( [2,4,3,1] ), 36, "2,4,3,1"); + + done_testing; +} -- cgit From 6b4ffbd7c7bc3b4f3948e2029411fbe2a6f7f4ae Mon Sep 17 00:00:00 2001 From: Bob Lied Date: Thu, 6 Jul 2023 07:30:12 -0500 Subject: Week 223 solutions --- challenge-223/bob-lied/perl/ch-1.pl | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/challenge-223/bob-lied/perl/ch-1.pl b/challenge-223/bob-lied/perl/ch-1.pl index de9a6d4625..cecd089ec2 100644 --- a/challenge-223/bob-lied/perl/ch-1.pl +++ b/challenge-223/bob-lied/perl/ch-1.pl @@ -26,6 +26,42 @@ my $DoTest = 0; GetOptions("test" => \$DoTest, "verbose" => \$Verbose); exit(!runTest()) if $DoTest; +package Sieve; + +sub new($class, $n) +{ + my $self = { + _max => 10, + _sieve => [ false, false, true, true, false, true, false, true, false, false, false ], + }; + bless $self, $class; +} + +sub upto($self, $n) +{ + return if $n <= $self->{_max}; + push @{$self->{_sieve}}, (true) x ( $n - $self->{_max} ); + for (my $p = $n; $p*$p <= $n; $p++ ) + { + if ( $self->{_sieve}->[$p] ) + { + for (my $i = $p*$p ; $i <= $n ; $i += $p ) + { + $self->{_sieve}->[$i] = false; + } + } + } +} + +sub count($self, $n) +{ +} + +1; + +package main; + + sub sieve($n) { my @prime = (false, false, true, (true,false) x (($n-1)/2) ); -- cgit