diff options
| author | drbaggy <js5@sanger.ac.uk> | 2021-08-16 13:20:00 +0100 |
|---|---|---|
| committer | drbaggy <js5@sanger.ac.uk> | 2021-08-16 13:20:00 +0100 |
| commit | 29508f0d381cd703ef8f160b1a1bae0ae9025d0e (patch) | |
| tree | b9e8d0a69601fc18f78badafc56e47c2e41d16c2 /challenge-126 | |
| parent | 649e141869d5874a852f1e9947246932ece9a44c (diff) | |
| download | perlweeklychallenge-club-29508f0d381cd703ef8f160b1a1bae0ae9025d0e.tar.gz perlweeklychallenge-club-29508f0d381cd703ef8f160b1a1bae0ae9025d0e.tar.bz2 perlweeklychallenge-club-29508f0d381cd703ef8f160b1a1bae0ae9025d0e.zip | |
notes added
Diffstat (limited to 'challenge-126')
| -rw-r--r-- | challenge-126/james-smith/perl/ch-1.pl | 42 |
1 files changed, 33 insertions, 9 deletions
diff --git a/challenge-126/james-smith/perl/ch-1.pl b/challenge-126/james-smith/perl/ch-1.pl index e680e413c2..94b9ee2ff9 100644 --- a/challenge-126/james-smith/perl/ch-1.pl +++ b/challenge-126/james-smith/perl/ch-1.pl @@ -38,6 +38,19 @@ is( get_no_one_count_x($_->[0]), $_->[1] ) foreach @TESTS; is( get_no_one_count($_->[0]), $_->[1] ) foreach @TESTS; done_testing(); +cmpthese(-5,{ 'scan 98' => sub { get_no_one_count( 98 ) }, + 'opt 98' => sub { get_no_one_count_x( 98 ) }, }); +cmpthese(-5,{ 'scan 987' => sub { get_no_one_count( 987 ) }, + 'opt 987' => sub { get_no_one_count_x( 987 ) }, }); +cmpthese(-5,{ 'scan 9876' => sub { get_no_one_count( 9876 ) }, + 'opt 9876' => sub { get_no_one_count_x( 9876 ) }, }); +cmpthese(-5,{ 'scan 98765' => sub { get_no_one_count( 98765 ) }, + 'opt 98765' => sub { get_no_one_count_x( 98765 ) }, }); +cmpthese(-5,{ 'scan 987654' => sub { get_no_one_count( 987654 ) }, + 'opt 987654' => sub { get_no_one_count_x( 987654 ) }, }); +cmpthese(-5,{ 'scan 9876543' => sub { get_no_one_count( 9876543 ) }, + 'opt 9876543' => sub { get_no_one_count_x( 9876543 ) }, }); + sub get_no_one_count { my $n = shift; return scalar grep { ! m{1} } 2..$n; @@ -45,16 +58,27 @@ sub get_no_one_count { ## Optimized version.... seems to work ... and far better than scan... sub get_no_one_count_x { - my $n = shift; - my $c = 0; - my $m = 1; + my ( $n, $count, $pow_9 ) = ( shift, 0, 1 ); while($n) { - my $t=$n%10; - $c = 0 if $t==1; - $c += $t ? ( $t < 2 ? ($m-1) : ($t-1)*$m ) : 0; - $m *= 9; - $n= int($n/10); + my $t = $n % 10; ## get last digit + $count = 0 if $t==1; ## Throw everything away we've found a 1 + $count += $t ? ( $t == 1 ? ($pow_9-1) : ($t-1)*$pow_9 ) : 0; + ## 0 it contributes nothing + ## 1 contributes 9^X-1 + ## 2-9 contributes (n-1)9^X + $pow_9 *= 9; ## update power of nine + $n = ( $n - $t )/10; ## drop last digit } - return $c; + return $count; } +## Comparison + +# | N | scan | opt | Speed-up | +# | --------: | --------: | --------: | ---------: | +# | 98 | 16,027 | 1,173,850 | 72 | +# | 987 | 2,623 | 867,796 | 330 | +# | 9,876 | 253 | 685,956 | 2,715 | +# | 98,765 | 24.4 | 565,427 | 23,155 | +# | 987,654 | 1.23 | 482,800 | 392,998 | +# | 9,876,543 | 0.23 | 418,410 | 1,853,771 | |