From 8cf30ac3764b883497c91bb47806a787ea3ee22a Mon Sep 17 00:00:00 2001 From: James Smith Date: Thu, 17 Jun 2021 23:57:57 +0100 Subject: Update README.md --- challenge-117/james-smith/README.md | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-) diff --git a/challenge-117/james-smith/README.md b/challenge-117/james-smith/README.md index aa4a62c493..84b19d8bef 100644 --- a/challenge-117/james-smith/README.md +++ b/challenge-117/james-smith/README.md @@ -72,8 +72,14 @@ sub schroder_cache_array { } ``` -But as we've said before recursion is a curse - so to remove the function -overhead of recursion we can re-write this like this: +But as we've said before recursion is a curse - but we notice that +``` + T0,m = 1 + Tn,0 = Tn-1,0 + Tn-1,1 + Tn,m = Tn-1,m + Tn-1,m+1 + Tn,m-1 +``` +We can use that to define each row of a triangle with `Sn` as the last +value. ```perl sub schroder_non_recursive { @@ -88,6 +94,12 @@ sub schroder_non_recursive { } ``` +We again use the row "flip" as we only need one row and the previous +one to get values... + +There is a faster solution - in that the Scrhoder numbers can be +written as a recurrence relation: + ```perl sub schroder_recurrence_rel { my( $size, @S ) = ( shift, 1, 2 ); -- cgit From 78ecad78a2b52f3ba82b07f9d787e573deca5923 Mon Sep 17 00:00:00 2001 From: James Smith Date: Thu, 17 Jun 2021 23:58:42 +0100 Subject: Create blog.txt --- challenge-117/james-smith/blog.txt | 1 + 1 file changed, 1 insertion(+) create mode 100644 challenge-117/james-smith/blog.txt diff --git a/challenge-117/james-smith/blog.txt b/challenge-117/james-smith/blog.txt new file mode 100644 index 0000000000..8d12b20b58 --- /dev/null +++ b/challenge-117/james-smith/blog.txt @@ -0,0 +1 @@ +https://github.com/drbaggy/perlweeklychallenge-club/blob/master/challenge-117/james-smith/ -- cgit From 4b681fc5f809dec0d649a740ce24b2b9f03087eb Mon Sep 17 00:00:00 2001 From: James Smith Date: Fri, 18 Jun 2021 00:02:20 +0100 Subject: Update README.md --- challenge-117/james-smith/README.md | 2 ++ 1 file changed, 2 insertions(+) diff --git a/challenge-117/james-smith/README.md b/challenge-117/james-smith/README.md index 84b19d8bef..07571f0918 100644 --- a/challenge-117/james-smith/README.md +++ b/challenge-117/james-smith/README.md @@ -55,6 +55,8 @@ sub triangle { ### Now the counts... Schroder numbers +*It's amazing what you find out about when you google the answers you get!* + Due to the "memory" storage issues we can change the problem to one of counting rather than listing... The first approach is to just convert the `triangle` method above to count - we introduce a cache as well to improve performance. -- cgit From 419787187210ea2f71d7fb4aad6deea50da34a99 Mon Sep 17 00:00:00 2001 From: James Smith Date: Fri, 18 Jun 2021 07:03:01 +0100 Subject: Update README.md --- challenge-117/james-smith/README.md | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) diff --git a/challenge-117/james-smith/README.md b/challenge-117/james-smith/README.md index 07571f0918..e17e38bcbc 100644 --- a/challenge-117/james-smith/README.md +++ b/challenge-117/james-smith/README.md @@ -53,7 +53,10 @@ sub triangle { } ``` -### Now the counts... Schroder numbers +Note we don't "collect" routes in a datastructure and then print them all at the end, but instead render directly from within the +function. For `$N` larger than `10` the memory requirements for storing this information increases significantly, so this code is limited purely by disk rather than memory. + +### Now the counts... Schröder numbers *It's amazing what you find out about when you google the answers you get!* @@ -99,8 +102,9 @@ sub schroder_non_recursive { We again use the row "flip" as we only need one row and the previous one to get values... -There is a faster solution - in that the Scrhoder numbers can be -written as a recurrence relation: +Googling for `2, 6, 22, 90, 394` came up with https://en.wikipedia.org/wiki/Schröder_number, a page +about Schröder numbers - which gives up the following faster (about twice as fast as above) solution - +as Scrhoder numbers can be written as a recurrence relation: ```perl sub schroder_recurrence_rel { -- cgit From 6939f51f9085bb0af3f721e1d47fac3b5a705ec1 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Fri, 18 Jun 2021 07:04:11 +0100 Subject: solutions at foot! --- challenge-117/james-smith/perl/ch-2.pl | 7 +++++++ 1 file changed, 7 insertions(+) diff --git a/challenge-117/james-smith/perl/ch-2.pl b/challenge-117/james-smith/perl/ch-2.pl index 854c9244b2..248d8d2dfe 100644 --- a/challenge-117/james-smith/perl/ch-2.pl +++ b/challenge-117/james-smith/perl/ch-2.pl @@ -142,3 +142,10 @@ sub schroder_recurrence_rel { } return $S[ $size ]; } + +## +# 1, 2, 6, 22, 90, 394, +# 1806, 8558, 41586, 206098, 1037718, +# 5293446, 27297738, 142078746, 745387038, 3937603038, +# 20927156706, 111818026018, 600318853926, 3236724317174, 17518619320890, +# 95149655201962, 518431875418926, 2832923350929742, 15521467648875090 -- cgit