diff options
| -rw-r--r-- | challenge-205/bruce-gray/blog.txt | 1 | ||||
| -rw-r--r-- | challenge-205/bruce-gray/perl/ch-1.pl | 16 | ||||
| -rw-r--r-- | challenge-205/bruce-gray/perl/ch-2.pl | 24 | ||||
| -rw-r--r-- | challenge-205/bruce-gray/raku/ch-1.raku | 13 | ||||
| -rw-r--r-- | challenge-205/bruce-gray/raku/ch-2.raku | 36 |
5 files changed, 90 insertions, 0 deletions
diff --git a/challenge-205/bruce-gray/blog.txt b/challenge-205/bruce-gray/blog.txt new file mode 100644 index 0000000000..b9b0d6392a --- /dev/null +++ b/challenge-205/bruce-gray/blog.txt @@ -0,0 +1 @@ +https://blogs.perl.org/users/bruce_gray/2023/02/twc-205-exclusive-third-or-first.html diff --git a/challenge-205/bruce-gray/perl/ch-1.pl b/challenge-205/bruce-gray/perl/ch-1.pl new file mode 100644 index 0000000000..a6d723c0f1 --- /dev/null +++ b/challenge-205/bruce-gray/perl/ch-1.pl @@ -0,0 +1,16 @@ +use v5.36; +use List::Util qw<uniq>; +sub task1 ( $ns ) { + my ( $x1, $x2, $x3 ) = sort { $b <=> $a } uniq @{$ns}; + return $x3 // $x1; +} + + +my @tests = ( + [ [ 5, 3, 4 ], 3 ], # 5 4 3 + [ [ 5, 6 ], 6 ], # 6 5 * Third highest is missing, so maximum is returned. + [ [ 5, 4, 4, 3 ], 3 ], # 5 4 3 (Aha! ties!) +); +use Test::More; +plan tests => 0+@tests; +is task1($_->[0]), $_->[1] for @tests; diff --git a/challenge-205/bruce-gray/perl/ch-2.pl b/challenge-205/bruce-gray/perl/ch-2.pl new file mode 100644 index 0000000000..9e2861bf96 --- /dev/null +++ b/challenge-205/bruce-gray/perl/ch-2.pl @@ -0,0 +1,24 @@ +use v5.36; +use ntheory qw<forcomb>; +use List::Util qq<max>; + +# See my Raku solution for a faster algorithm. +sub task2 ( @ns ) { + my $r = 0; + + forcomb { + $r = max( $r, $ns[$_[0]] ^ $ns[$_[1]] ); + } @ns, 2; + + return $r; +} + + +my @tests = ( + [ [ 1, 2, 3, 4, 5, 6, 7 ], 7 ], # 1 xor 6 = 7 + [ [ 2, 4, 1, 3 ], 7 ], # 4 xor 3 = 7 + [ [ 10, 5, 7, 12, 8 ], 15 ], # 10 xor 5 = 15 +); +use Test::More; +plan tests => 0+@tests; +is task2(@{$_->[0]}), $_->[1] for @tests; diff --git a/challenge-205/bruce-gray/raku/ch-1.raku b/challenge-205/bruce-gray/raku/ch-1.raku new file mode 100644 index 0000000000..8af9db5649 --- /dev/null +++ b/challenge-205/bruce-gray/raku/ch-1.raku @@ -0,0 +1,13 @@ +sub task1 ( @ns ) { + return (.elems == 3 ?? .head !! .tail) given @ns.sort.squish.tail(3); +} + + +my @tests = + ( ( 5, 3, 4 ), 3 ), # 5 4 3 + ( ( 5, 6 ), 6 ), # 6 5 * Third highest is missing, so maximum is returned. + ( ( 5, 4, 4, 3 ), 3 ), # 5 4 3 (Aha! ties!) +; +use Test; +plan +@tests; +is task1(.[0]), .[1] for @tests; diff --git a/challenge-205/bruce-gray/raku/ch-2.raku b/challenge-205/bruce-gray/raku/ch-2.raku new file mode 100644 index 0000000000..2b98b2d10c --- /dev/null +++ b/challenge-205/bruce-gray/raku/ch-2.raku @@ -0,0 +1,36 @@ +# In Raku, we can solve the task in one line: +sub task2_short { @_.unique.combinations(2).map({ [+^] .list }).max } + +# But with a bit of analysis, we can go *much* faster! +# See blog post for explanation of the algorithm. +sub task2_fast ( @ns ) { + sub hi-bit ( UInt $n ) { $n.log2.floor } + + my %grouped = @ns.unique.classify(&hi-bit); + + my ($top_group, @lesser_groups) = %grouped.sort(-*.key).map(*.value); + + if !@lesser_groups { + my $removes_hi-bit = 1 +< hi-bit($top_group[0]); + return task2_fast( $top_group.list »-» $removes_hi-bit ); + } + else { + return [max] @lesser_groups.map: { + ($top_group.list X+^ .list).max; + } + } +} + + +# my &task2 = &task2_short; +my &task2 = &task2_fast; +my @tests = + ( ( 1, 2, 3, 4, 5, 6, 7 ), 7 ), # 1 xor 6 = 7 + ( ( 2, 4, 1, 3 ), 7 ), # 4 xor 3 = 7 + ( ( 10, 5, 7, 12, 8 ), 15 ), # 10 xor 5 = 15 + + ( [ flat(1 .. 4095) ], 4095 ), # short=113sec, fast=5sec !!! +; +use Test; +plan +@tests; +is task2(.[0]), .[1] for @tests; |
