diff options
| author | drbaggy <js5@sanger.ac.uk> | 2021-06-19 11:12:41 +0100 |
|---|---|---|
| committer | drbaggy <js5@sanger.ac.uk> | 2021-06-19 11:12:41 +0100 |
| commit | 69846439dfbe8dd89e0ad0dcddda00b6db3ec060 (patch) | |
| tree | dd443a9acc2e26ff6f6d5317021b89edeb66d8f6 | |
| parent | eda544efa917e0b554c55cdcc155c19f836ebb4b (diff) | |
| download | perlweeklychallenge-club-69846439dfbe8dd89e0ad0dcddda00b6db3ec060.tar.gz perlweeklychallenge-club-69846439dfbe8dd89e0ad0dcddda00b6db3ec060.tar.bz2 perlweeklychallenge-club-69846439dfbe8dd89e0ad0dcddda00b6db3ec060.zip | |
fixed a typo
| -rw-r--r-- | challenge-117/james-smith/perl/ch-2.pl | 28 |
1 files changed, 15 insertions, 13 deletions
diff --git a/challenge-117/james-smith/perl/ch-2.pl b/challenge-117/james-smith/perl/ch-2.pl index 248d8d2dfe..f2ee1b08ad 100644 --- a/challenge-117/james-smith/perl/ch-2.pl +++ b/challenge-117/james-smith/perl/ch-2.pl @@ -4,6 +4,8 @@ use strict; use warnings; use feature qw(say); +use utf8; + use Test::More; use Benchmark qw(cmpthese); @@ -51,9 +53,9 @@ if( $N < 0 ) { ## Run recursive dumper! } unless( $N ) { ## Run the test scripts - is( schroder_cache_array( $_->[0] ), $_->[1] ) foreach @TESTS; - is( schroder_non_recursive( $_->[0] ), $_->[1] ) foreach @TESTS; - is( schroder_recurrence_rel( $_->[0] ), $_->[1] ) foreach @TESTS; + is( schröder_cache_array( $_->[0] ), $_->[1] ) foreach @TESTS; + is( schröder_non_recursive( $_->[0] ), $_->[1] ) foreach @TESTS; + is( schröder_recurrence_rel( $_->[0] ), $_->[1] ) foreach @TESTS; done_testing(); exit; } @@ -61,9 +63,9 @@ unless( $N ) { ## Run the test scripts ## Run the benchmarking.... cmpthese( 10000, { - 'recursive' => sub { @cache=(); schroder_cache_array( $N ); }, - 'non-recursive' => sub { schroder_non_recursive( $N ); }, - 'recrel' => sub { schroder_recurrence_rel( $N ); }, + 'recursive' => sub { @cache=(); schröder_cache_array( $N ); }, + 'non-recursive' => sub { schröder_non_recursive( $N ); }, + 'recrel' => sub { schröder_recurrence_rel( $N ); }, }); sub triangle { @@ -95,8 +97,8 @@ sub triangle { triangle( $size, $offset - 1, $route.'H' ) if $offset; } -sub schroder_cache_array { -## The count is the Schroder number +sub schröder_cache_array { +## The count is the Schröder number ## We can duplicate the "algorithm above" but counting to display ## the number of routes. We use a cache as we repeatedly hit the ## same tree [there are only $N*($N+1)/2 combinations of $size & $offset.] @@ -107,14 +109,14 @@ sub schroder_cache_array { my($size,$offset) = @_; $offset ||=0; return $size ? ( $cache[$size][$offset] ||= - schroder_cache_array( $size - 1, $offset + 1 ) #L - + schroder_cache_array( $size - 1, $offset ) #R - + ( $offset ? schroder_cache_array( $size, $offset - 1 ) : 0 ) + schröder_cache_array( $size - 1, $offset + 1 ) #L + + schröder_cache_array( $size - 1, $offset ) #R + + ( $offset ? schröder_cache_array( $size, $offset - 1 ) : 0 ) ) : 1; } -sub schroder_non_recursive { +sub schröder_non_recursive { ## We can rewrite this non-recursively by starting at the bottom row ## (all values 1) and working our way up the triangle {working right ## to left} @@ -129,7 +131,7 @@ sub schroder_non_recursive { return $x[0]; } -sub schroder_recurrence_rel { +sub schröder_recurrence_rel { ## As well as the total calculation above there is a recurrence ## relation which defines S_n in terms of S_1 -> S_n-1 ## As expected slightly faster than the previous solution |
