From b2c716c80f57393600713ffd1d2555e56a4221b6 Mon Sep 17 00:00:00 2001 From: drbaggy Date: Tue, 22 Sep 2020 12:35:51 +0100 Subject: Challenge 79 solutions --- challenge-079/james-smith/README.md | 73 +++++++++++----------------- challenge-079/james-smith/perl/ch-1.pl | 89 ++++++++++++++++++++++++++++++++++ challenge-079/james-smith/perl/ch-2.pl | 70 ++++++++++++++++++++++++++ 3 files changed, 188 insertions(+), 44 deletions(-) create mode 100755 challenge-079/james-smith/perl/ch-1.pl create mode 100644 challenge-079/james-smith/perl/ch-2.pl diff --git a/challenge-079/james-smith/README.md b/challenge-079/james-smith/README.md index 74219c000c..96284e7deb 100644 --- a/challenge-079/james-smith/README.md +++ b/challenge-079/james-smith/README.md @@ -1,60 +1,45 @@ Solutions by James Smith. -# Challenge 1 - leader +# Challenge 1 - Count Set Bits -There are two solutions to this - the naive one works left to right, but the optimal one runs right to left. +This is a really interesting challenge - there is a really quick naive solution which is to do the +counting - but that is an O(n log(n)) problem so as n gets large (to values where the modulus +calculation is required) then this gets very slow. -```perl -sub leader { ## Most efficient way is to work backwards on this rather - ## than forwards... +There is an O(log(n)) solution which means breaking the sums into chunks which are easy to sum. - return 0 unless @_; ## If nothing passed return 0 as requested. +For the numbers 1 .. (2^n-1) you can see that the sum of the bits is n(2^n)/2 - my @R = my $max = pop @_; ## Last one will always be a "leader"... - foreach ( reverse @_ ) { ## Work forward and unshift the value if it is now a leader - unshift @R, $max = $_ if $max < $_; ## greater than max value (and update max at the same time) - } +[ There are 2^n numbers (including 0) and you can represent number in n bits, and exactly half of the bits are 1 ] - return @R; ## Return array of leaders... -} -``` - -Notes: - - * This is an O(n) solution where the forward solution is O(n^2); - -# Challenge 2 - left rotate +We can then use this to work out the sums of the bit counts.. -This is a simpler challenge as this is something Perl is even better at - rotating an array is just -an array slice of the array with the indicies itself rotated... +First we get a bit representation of "$i+1" -The index rotation is easy: "offset" .. "size of list", 0 .. ("offset" - 1); +so e.g. for i = 22 - the array is 1 0 1 1 1 -So the code reduces to: +Loop through the bits and use the count method above to count the lower bits +of each group (ignore any where the value in the bit array is 0) +The higher bits are counted by multiplying the size of the group by the bits +in the "higher bit" e.g. 16, 20, 22 below... What we note though is that this +number increases by 1 each time that we loop through the array -```perl -sub rotate { - my $a = shift; - ## First parameter is an arrayref containing the values to be rotated - ## Remaining parameters are the offsets for each rotation +So in the example above the chunks become: - ## This is a great use of array slicing to achieve what we need - ## Indexes go from offset -> size-1 & 0 -> offset-1 - ## Perl nicely handles the case where the value to the left of - ## the double dot is higher than the value to the right - - print " [@{[ @{$a}[ $_..(@{$a}-1), 0..($_-1) ] ]}]\n" foreach @_; - - ## Let us use the @{[ ]} trick to embed content into the print - ## statement - this is a very useful and often under used feature - ## of perl which makes for simpler code when rendering output... - ## this is nice because print "@A" an print @A are subtly different - ## with the "@A" putting spaces (default value of $") -} +``` + 1..15 - split this into 16 x "0" & 0..15 - total is 2^4 * 0 + 4(2^4)/2 = 32 +16..19 - split this into 4 x "16" & 0..3 - total is 2^2 * 1 + 2(2^2)/2 = 8 +20..21 - split this into 2 x "20" & 0..1 - total is 2^1 * 2 + 1(2^1)/2 = 5 +22 - split this into 1 x "22" & 0 - total is 2^0 * 3 + 0(2^0)/2 = 3 + 48 ``` -Notes: +# Challenge 2 - trapped rain water - * We use Arrayref slice notation @{ $arrayref }[ @index_list ] to do the rotation +Much simpler challenge this time - we just need to work out how much water is trapped. +So for any column we need to work out the maximum height of rocks to the left and right +of the column, if neither of these are higher than the height of the current column no +water is trapped. Otherwise the amount of water is trapped is the minimum of these two +values minus the height of the column. - * We use "@{[ ... ]}" string interpolation to insert these values into the output... +To enhance the image - I've also added "~~"s to indicate where the water is trapped diff --git a/challenge-079/james-smith/perl/ch-1.pl b/challenge-079/james-smith/perl/ch-1.pl new file mode 100755 index 0000000000..b7b458744f --- /dev/null +++ b/challenge-079/james-smith/perl/ch-1.pl @@ -0,0 +1,89 @@ +#!/usr/bin/perl + +use strict; +use warnings; + +use Time::HiRes qw(time); + +foreach (@ARGV) { + my $t = time; + my $q = count_set_bits($_); + my $d = time-$t; + $t = time; + my $q2 = naive_count_set_bits($_); + my $d2 = time-$t; + printf "%15d\t%15d\t%15d\t%12.6f\t%12.6f\t%12.3f\n", $_, $q, $q2, $d, $d2, $d2/$d; +} + +## Counting isn't the best way - we can work this out only looking at the current +## number. +## +## The count for the integers 1 .. (2^n-1) is n(2^n)/2 +## +## We can use this information to get the total... +## Get array of bits for "i+1" +## Foreach bit in this representation which is 1 - we count the number of bits +## in that chunk of the number so e.g. +## i = 22 +## Then the bit array is 1,0,1,1,1 +## +## Loop through the bits and use the count method above to count the lower bits +## of each group (ignore any where the value in the bit array is 0) +## The higher bits are counted by multiplying the size of the group by the bits +## in the "higher bit" e.g. 16, 20, 22 below... What we note though is that this +## number increases by 1 each time that we loop through the array +## +## So in the example above the chunks become: +## 1..15 - split this into 16 x "0" & 0..15 - total is 2^4 * 0 + 4(2^4)/2 = 32 +## 16..19 - split this into 4 x "16" & 0..3 - total is 2^2 * 1 + 2(2^2)/2 = 8 +## 20..21 - split this into 2 x "20" & 0..1 - total is 2^1 * 2 + 1(2^1)/2 = 5 +## 22 - split this into 1 x "22" & 0 - total is 2^0 * 3 + 0(2^0)/2 = 3 +## 48 +## I have included the naive method for comparison.... +## the naive method is O(n ln(n)) and the optimal method is O(ln(n)) +## Numbers below to show this... + +## we see the following performance +## "i" "count" "fast" "naive" "speed up" +## 1 1 0.000017 0.000008 0.458 +## 10 17 0.000014 0.000007 0.492 +## 100 319 0.000012 0.000022 1.840 +## 1,000 4,938 0.000010 0.000187 18.690 +## 10,000 64,613 0.000019 0.001943 101.875 +## 100,000 815,030 0.000035 0.076236 2,175.218 +## 1,000,000 9,884,999 0.000034 0.835451 24,677.007 +## 10,000,000 114,434,632 0.000034 8.543442 250,585.965 +## 100,000,000 314,447,109 0.000041 95.227608 2,322,171.727 + + +sub count_set_bits { + my $i = shift; + my @q = split m{}, sprintf '%b', $i+1; + my $t = my $s = 0; + while (@q) { + next unless shift @q; + $t += ($s + @q/2)*(1<<@q); + $t %= 1000000007; + $s++; + } + return $t; +} + +sub naive_count_set_bits { + my $c = 0; + $c += (sprintf "%b", $_) =~ tr/1/1/ for 1..shift; + return $c % 1000000007; +} + +# "i" "count" "fast" "naive" "speed up" +# 1 1 0.000017 0.000008 0.458 +# 10 17 0.000014 0.000007 0.492 +# 100 319 0.000012 0.000022 1.840 +# 1,000 4,938 0.000010 0.000187 18.690 +# 10,000 64,613 0.000019 0.001943 101.875 +# 100,000 815,030 0.000035 0.076236 2,175.218 +# 1,000,000 9,884,999 0.000034 0.835451 24,677.007 +# 10,000,000 114,434,632 0.000034 8.543442 250,585.965 +# 100,000,000 314,447,109 0.000041 95.227608 2,322,171.727 + +# diff --git a/challenge-079/james-smith/perl/ch-2.pl b/challenge-079/james-smith/perl/ch-2.pl new file mode 100644 index 0000000000..c2616068fe --- /dev/null +++ b/challenge-079/james-smith/perl/ch-2.pl @@ -0,0 +1,70 @@ +#!/usr/bin/perl + +use strict; +use feature qw(say); +use warnings; + +say trapped_rain_water( qw(2 1 4 1 2 5) ); + +say trapped_rain_water( qw(3 1 3 1 1 5) ); + +## Function draws chart - and returns amount of water trapped... +## Output below for two runs + +# +# heights: 2 1 4 1 2 5 heights: 3 1 3 1 1 5 +# +# 5 | ## 5 | ## +# 4 | ## ~~ ~~ ## 4 | ## +# 3 | ## ~~ ~~ ## 3 | ## ~~ ## ~~ ~~ ## +# 2 | ## ~~ ## ~~ ## ## 2 | ## ~~ ## ~~ ~~ ## +# 1 | ## ## ## ## ## ## 1 | ## ## ## ## ## ## +# -- + -- -- -- -- -- -- -- + -- -- -- -- -- -- +# | 2 1 4 1 2 5 | 3 1 3 1 1 5 +# +# 6 6 +# + +sub trapped_rain_water { ## Returns amount of water trapped + my @heights = @_; ## Heights of each "column" + my @water_heights = [$heights[0],$heights[0]]; + my $t = 0; + my $h = 0; + ## Keep height of "histogram" for purposes of display only.. + foreach( @heights ) { + $h = $_ if $h < $_; + } + foreach my $x (1 .. @heights-2 ) { + my $lh = my $rh = 0; + ## Find highest value left and right of the current column... + foreach (0 .. $x-1) { + $lh = $heights[$_] if $lh < $heights[$_]; + } + foreach ($x+1 .. @heights-1) { + $rh = $heights[$_] if $rh < $heights[$_]; + } + ## If these are both above the height of the current column then + ## water will collect in the column - it will be the smaller of + ## these two totals minus the height of the current ground... + my $th = ($lh < $rh ? $lh : $rh); + ## We will keep water heights so we can draw the water levels on + ## the picture + push @water_heights, [ $heights[$x], $th ]; + $t += $th-$heights[$x] if $heights[$x] < $th; + } + + push @water_heights, [$heights[-1],$heights[-1]]; + + print "\n"; + ## Draw the levels -> "##" for rock, "~~" for water... + foreach my $y ( reverse 1 .. $h ) { + printf " %2d |%s\n", $y, join q(), map { $_->[0] < $y ? ( $_->[1] < $y ? q( ) : q( ~~) ) : q( ##) } @water_heights; + } + ## Draw the horizontal axis + printf " -- +%s\n", join q(), map { q( --) } @heights; + printf " |%s\n", join q(), map { sprintf ' %2d', $_ } @heights; + print "\n"; + + return $t; +} + -- cgit