Merge pull request #8096 from choroba/ech217

Add solutions to 217: Sorted Matrix & Max Number by E. Choroba

2 files changed, 111 insertions, 0 deletions

diff --git a/challenge-217/e-choroba/perl/ch-1.pl b/challenge-217/e-choroba/perl/ch-1.pl
new file mode 100755
index 0000000000..d37076b152
--- /dev/null
+++ b/challenge-217/e-choroba/perl/ch-1.pl
@@ -0,0 +1,55 @@
+#! /usr/bin/perl
+use warnings;
+use strict;
+use experimental qw( signatures );
+
+sub sorted_matrix($m) {
+    (sort { $a <=> $b } map @$_, @$m)[2]
+}
+
+sub sorted_matrix_sliding_window($m) {
+    my $iter = iter($m);
+    my @window = sort { $a <=> $b } map $iter->(), 1 .. 3;
+    while (defined( my $e = $iter->() )) {
+        if (my $count = grep $e < $_, @window) {
+            splice @window, -$count, 0, $e;
+            pop @window;
+        }
+    }
+    return $window[2]
+}
+
+sub iter($m) {
+    my ($x, $y) = (0, 0);
+    return sub() {
+        return if $x > $#$m;
+        my $e = $m->[$x][$y];
+        $y = 0, ++$x if ++$y > $#$m;
+        return $e
+    }
+}
+
+
+use Test::More tests => 3 + 1;
+
+is sorted_matrix([[3, 1, 2], [5, 2, 4], [0, 1, 3]]), 1, 'Example 1';
+is sorted_matrix([[2, 1], [4, 5]]), 4, 'Example 2';
+is sorted_matrix([[1, 0, 3], [0, 0, 0], [1, 2, 1]]), 0, 'Example 3';
+
+use Benchmark qw{ cmpthese };
+my $size = 1000;
+my @m = map [map int rand 1_000_000, 1 .. $size], 1 .. $size;
+
+is sorted_matrix(\@m), sorted_matrix_sliding_window(\@m), 'same';
+
+cmpthese(-10, {
+    window => sub { sorted_matrix_sliding_window(\@m) },
+    sorted => sub { sorted_matrix(\@m) },
+});
+
+__END__
+Interestingly, sorting the whole array is faster than using the sliding window.
+
+         Rate window sorted
+window 3.04/s     --   -31%
+sorted 4.44/s    46%     --
diff --git a/challenge-217/e-choroba/perl/ch-2.pl b/challenge-217/e-choroba/perl/ch-2.pl
new file mode 100755
index 0000000000..209c7ad60d
--- /dev/null
+++ b/challenge-217/e-choroba/perl/ch-2.pl
@@ -0,0 +1,56 @@
+#! /usr/bin/perl
+use warnings;
+use strict;
+use experimental qw( signatures );
+
+sub max_number(@list) {
+    return join "",
+        sort { (0 == index $a, $b) ? -compare($a, $b)
+             : (0 == index $b, $a) ? compare($b, $a)
+                                   : $b cmp $a
+        } @list
+}
+
+sub compare($x, $y) {
+    return $x <=> $y if length($x) == length($y);
+
+    my $first = substr $x, 0, 1;
+    my $diff  = substr $x, length($y), 1;
+    my $cmp = $diff <=> $first;
+    return $cmp if $cmp || 1 == length $y;
+
+    return compare(substr($x, 1), substr($y, 1))
+}
+
+use Test::More tests => 5 + 3 * 6 + 3;
+
+is max_number(1, 23), 231, 'Example 1';
+is max_number(10, 3, 2), 3210, 'Example 2';
+is max_number(31, 2, 4, 10), 431210, 'Example 3';
+is max_number(5, 11, 4, 1, 2), 542111, 'Example 4';
+is max_number(1, 10), 110, 'Example 5';
+
+is max_number(53, 531, 2), 535312, 't 53 531';
+is max_number(531, 53, 2), 535312, 't 531 53';
+is max_number(53, 535, 2), 535532, 't 53 535';
+is max_number(535, 53, 2), 535532, 't 535 53';
+is max_number(53, 536, 2), 536532, 't 53 536';
+is max_number(536, 53, 2), 536532, 't 536 53';
+
+is max_number(4567, 45673), 456745673, 't 4567+3';
+is max_number(4567, 45674), 456745674, 't 4567+4';
+is max_number(4567, 45675), 456754567, 't 4567+5';
+is max_number(45673, 4567), 456745673, 't 4567+3 rev';
+is max_number(45674, 4567), 456745674, 't 4567+4 rev';
+is max_number(45675, 4567), 456754567, 't 4567+5 rev';
+
+is max_number(445671, 44567), 44567445671, 'recursion <';
+is max_number(445674, 44567), 44567445674, 'recursion =';
+is max_number(445675, 44567), 44567544567, 'recursion >';
+is max_number(44567, 445671), 44567445671, 'recursion < rev';
+is max_number(44567, 445674), 44567445674, 'recursion = rev';
+is max_number(44567, 445675), 44567544567, 'recursion > rev';
+
+is max_number(23, 23, 231), 2323231, 'repeated <';
+is max_number(23, 23, 232), 2323232, 'repeated =';
+is max_number(23, 23, 233), 2332323, 'repeated >';