diff options
| -rw-r--r-- | challenge-337/kjetillll/perl/ch-1.pl | 67 | ||||
| -rw-r--r-- | challenge-337/kjetillll/perl/ch-2.pl | 34 |
2 files changed, 101 insertions, 0 deletions
diff --git a/challenge-337/kjetillll/perl/ch-1.pl b/challenge-337/kjetillll/perl/ch-1.pl new file mode 100644 index 0000000000..56dbd146a1 --- /dev/null +++ b/challenge-337/kjetillll/perl/ch-1.pl @@ -0,0 +1,67 @@ +use strict; use warnings; + +sub f_simple { + map -// + grep( $_ <= $', @_ ), @_ +} + +sub f_fast { + my %n; + @n{ sort { $a <=> $b } @_ } = 0 .. $#_; + @n{ @_ } +} + +my @tests = ( + [ [6, 5, 4, 8] => [2, 1, 0, 3] ], + [ [7, 7, 7, 7] => [3, 3, 3, 3] ], + [ [5, 4, 3, 2, 1] => [4, 3, 2, 1, 0] ], + [ [-1, 0, 3, -2, 1] => [1, 2, 4, 0, 3] ], + [ [0, 1, 1, 2, 0] => [1, 3, 3, 4, 1] ], + [ [81,5,47,70,45,11,58,51,52,88,15,69,43,76,40,43,22,75,79,9,68,21,36,65,19,62,81,-7,41,43,36,-7,3,79,3] + => [33,4,19,27,18,6,22,20,21,34,7,26,17,29,13,17,10,28,31,5,25,9,12,24,8,23,33,1,14,17,12,1,3,31,3] ], + + [ [68,55,61,-9,-7,43,79,-9,50,39,57,32,0,50,-1,67,97,97,42,32,45,15,99,65,0,62,85,11,83,53,27,90,78,5,23, + 95,40,24,62,-5,52,62,87,23,23,99,26,36,-5,58,57,4,91,-6,62,83,-6,21,23,29,82,7,50,-1,64,5,25,58,64,38, + -1,-6,46,82,-4,42,20,85,28,39,67,62,69,-3,16,19,98,71,-3,98,90,95,67,95,10,49,2,38,32,30,34,4,69,78,52, + 2,75,35,16,65,57,89,84,-8,22,98,33,52,34,36,32,33,69,39,35,5,66,42,44,68,6,71,90,85,56,20,52,6,8,88, + 99,38,32,-4,-8,21,57,82,46,1,53,28,18,13,79,10,30,22,71,4,76,52,78,47,-1,57,53,12,51,34,-2,45,75,39,7, + 77,87,23,39,10,23,78,84,41,85,30,-2,56,13,78,-7,62,9,58,38,-9,55,7,53,77,62,22,74,56,58,31,31,-1,80,71, + 71,36,63,74,72,45,88,30,40,-3,58,45,49,15,2,84,74,-1,72,73,80,68,88,88,65,7,5,66,81,70,91,33,87,90,18, + 33,59,71,7,42,62,80,45,13,75,81,-9,94,48,58,20,80,69,86,33,65,33,-5,86,21,31,33,-4,61,-4,66,19,64,32,-9, + -9,1,16,73,11,43,44,22,13,87,29,61,75,98,84,57,43,68,59,9,87,58,25,77,38,38,-6,16,2,12,37,4,72,93,-2, + 7,0,21,38,-1,88,51,24,72,19,7,58,64,6,82,73,11,0,93,0,-1,22,45,12,64,41,29,47,60,78,29,33,10,18,90, + 47,11,98,61,73,25,19,95,90,61,40,39,-5,83,70,-2,56,51,90,2,96,7,-8,11,96,93,95,57,-3,52,43,71,-5,94,-3, + 40,0,-1,98,11,39,0,20,9,43,-9,61,19,90,46,78,-5,17,63,66,45,72,59,21,14,42,85,18,23,29,85,32,-5,61,26, + -1,61,20,2,-7,4,47,37,63,58,53,28,31,1,59,86,58,54,93,39,7,3,67,95,23,11,52,23,81,23,55,59,46,92,76, + 78,61,4,2,-9,71,55,16,80,56,82,38,58,43,13,-9,19,-7,2,13,7,92,18,66,25,92,39,92,-2,98,63,87,98,64,37, + 79,89,23,97,-8,70,15,82,33,22] + => [367,294,332,8,16,251,414,8,274,234,306,197,58,274,51,363,488,488,245,197,260,121,499,354,58,340,441, + 108,431,289,174,465,411,80,165,483,238,167,340,27,284,340,450,165,165,499,173,214,27,317,306,76,467,20, + 340,431,20,148,165,182,428,93,274,51,350,80,171,317,350,225,51,20,264,428,31,245,143,441,177,234,363, + 340,371,36,126,138,496,382,36,496,465,483,363,483,101,271,69,225,197,186,209,76,371,411,284,69,398,211, + 126,354,306,457,435,12,154,496,206,284,209,214,197,206,371,234,211,80,359,245,253,367,83,382,465,441,299, + 143,284,83,94,455,499,225,197,31,12,148,306,428,264,61,289,177,132,117,414,101,186,154,382,76,400,284, + 411,268,51,306,289,111,277,209,41,260,398,234,93,403,450,165,234,101,165,411,435,240,441,186,41,299,117, + 411,16,340,97,317,225,8,294,93,289,403,340,154,394,299,317,190,190,51,419,382,382,214,344,394,387,260, + 455,186,238,36,317,260,271,121,69,435,394,51,387,391,419,367,455,455,354,93,80,359,422,374,467,206,450, + 465,132,206,322,382,93,245,340,419,260,117,398,422,8,477,269,317,143,419,371,444,206,354,206,27,444,148, + 190,206,31,332,31,359,138,350,197,8,8,61,126,391,108,251,253,154,117,450,182,332,398,496,435,306,251, + 367,322,97,450,317,171,403,225,225,20,126,69,111,217,76,387,475,41,93,58,148,225,51,455,277,167,387, + 138,93,317,350,83,428,391,108,58,475,58,51,154,260,111,350,240,182,268,323,411,182,206,101,132,465,268, + 108,496,332,391,171,138,483,465,332,238,234,27,431,374,41,299,277,465,69,485,93,12,108,485,475,483,306, + 36,284,251,382,27,477,36,238,58,51,496,108,234,58,143,97,251,8,332,138,465,264,411,27,127,344,359, + 260,387,322,148,118,245,441,132,165,182,441,197,27,332,173,51,332,143,69,16,76,268,217,344,317,289,177, + 190,61,322,444,317,290,475,234,93,70,363,483,165,108,284,165,422,165,294,322,264,471,400,411,332,76,69, + 8,382,294,126,419,299,428,225,317,251,117,8,138,16,69,117,93,471,132,359,171,471,234,471,41,496,344, + 450,496,350,217,414,457,165,488,12,374,121,428,206,154] ] + ); + +print "@{ $$_[1] }" eq "@{[ f_simple( @{$$_[0]} ) ]}" ? "ok " : "error " for @tests; +print "@{ $$_[1] }" eq "@{[ f_fast( @{$$_[0]} ) ]}" ? "ok " : "error " for @tests; + +print "\n\nbenchmarking runtimes per second, wait a few seconds...\n\n"; +my @inputs = map $$_[0], @tests; +use Benchmark; +Benchmark::cmpthese(400, { + f_simple => sub{ f_simple( @$_ ) for @inputs }, # n^2 + f_fast => sub{ f_fast( @$_ ) for @inputs }, # n log(n) +}); diff --git a/challenge-337/kjetillll/perl/ch-2.pl b/challenge-337/kjetillll/perl/ch-2.pl new file mode 100644 index 0000000000..a7b51d416d --- /dev/null +++ b/challenge-337/kjetillll/perl/ch-2.pl @@ -0,0 +1,34 @@ + +sub f_simple { + my($r, $c, @l) = @_; + my @matrix = map [ (0) x $c ], 0 .. $r-1; + for( @l ){ + my($ir, $ic) = @$_; + $matrix[ $ir ][ $_ ]++ for 0 .. $c-1; + $matrix[ $_ ][ $ic ]++ for 0 .. $r-1; + } + my $oddcount = 0; + for( @matrix ){ + for ( @$_ ){ + $oddcount += $_ % 2 + } + } + $oddcount +} + +sub f_faster_and_less_memory { + my($r, $c, @l) = @_; + my @oddr = (0) x $r; $oddr[ $$_[0] ] ^= 1 for @l; + my @oddc = (0) x $c; $oddc[ $$_[1] ] ^= 1 for @l; + 0 + map { //; grep $' ^ $_, @oddc } @oddr +} + +my @tests = map [ $$_{output}, @{ $$_{input} }{'row','col'}, @{$$_{input}{locations}} ], + { input => { row => 2, col => 3, locations => [ [0,1],[1,1] ] }, output => 6 }, + { input => { row => 2, col => 2, locations => [ [1,1],[0,0] ] }, output => 0 }, + { input => { row => 3, col => 3, locations => [ [0,0],[1,2],[2,1] ] }, output => 0 }, + { input => { row => 1, col => 5, locations => [ [0,2],[0,4] ] }, output => 2 }, + { input => { row => 4, col => 2, locations => [ [1,0],[3,1],[2,0],[0,1] ] }, output => 8 }; + +print f_simple( @$_[1..$#$_] ) == $$_[0] ? "ok\n" : "error\n" for @tests; +print f_faster_and_less_memory( @$_[1..$#$_] ) == $$_[0] ? "ok\n" : "error\n" for @tests; |