Merge pull request #4004 from choroba/ech111

Add solutions to 111: Search Matrix & Ordered Letters by E. Choroba

2 files changed, 103 insertions, 0 deletions

diff --git a/challenge-111/e-choroba/perl/ch-1.pl b/challenge-111/e-choroba/perl/ch-1.pl
new file mode 100755
index 0000000000..f46953570a
--- /dev/null
+++ b/challenge-111/e-choroba/perl/ch-1.pl
@@ -0,0 +1,72 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+
+sub search_matrix_hash {
+    my ($matrix, $value) = @_;
+    my %values;
+    @values{ map @$_, @$matrix } = ();
+    return exists $values{$value} ? 1 : 0
+}
+
+sub search_matrix_bin {
+    my ($matrix, $value) = @_;
+    my ($y0, $y1) = (0, $#$matrix);
+
+    while ($y0 < $y1) {
+        my $y = int(($y0 + $y1) / 2);
+        if ($matrix->[$y][0] > $value) {
+            $y1 = $y - 1;
+        } elsif ($matrix->[$y][-1] < $value) {
+            $y0 = $y + 1;
+        } else {
+            $y1 = $y;
+        }
+    }
+    return 0 if $y1 < $y0;
+
+    my ($x0, $x1) = (0, $#{ $matrix->[$y0] });
+    while ($x0 < $x1) {
+        my $x = int(($x0 + $x1) / 2);
+        if ($matrix->[$y0][$x] > $value) {
+            $x1 = $x - 1;
+
+        } elsif ($matrix->[$y0][$x] < $value) {
+            $x0 = $x + 1;
+
+        } else {
+            $x1 = $x;
+        }
+    }
+    return 0 if $x1 < $x0;
+
+    return $matrix->[$y0][$x0] == $value ? 1 : 0;
+}
+
+my $matrix = [[  1,  2,  3,  5,  7 ],
+              [  9, 11, 15, 19, 20 ],
+              [ 23, 24, 25, 29, 31 ],
+              [ 32, 33, 39, 40, 42 ],
+              [ 45, 47, 48, 49, 50 ]];
+
+use Test::More tests => 2 + 52;
+
+is search_matrix_hash($matrix, 35), 0, 'Missing';
+is search_matrix_hash($matrix, 39), 1, 'Found';
+
+for my $i (0 .. 51) {
+    is  search_matrix_bin($matrix, $i),
+        search_matrix_hash($matrix, $i), "same $i";
+}
+
+use Benchmark qw{ cmpthese };
+cmpthese(-3, {
+    hash => sub { search_matrix_hash($matrix, int rand 52) },
+    bin  => sub { search_matrix_bin($matrix, int rand 52) },
+});
+
+__END__
+
+         Rate hash  bin
+hash 222009/s   -- -76%
+bin  914600/s 312%   --
diff --git a/challenge-111/e-choroba/perl/ch-2.pl b/challenge-111/e-choroba/perl/ch-2.pl
new file mode 100755
index 0000000000..eee781f1c7
--- /dev/null
+++ b/challenge-111/e-choroba/perl/ch-2.pl
@@ -0,0 +1,31 @@
+#!/usr/bin/perl
+use warnings;
+use strict;
+use feature qw{ say };
+
+use Syntax::Construct qw{ // };
+
+my $file = shift // '/usr/share/dict/british';
+my %max = (0 => [""]);
+open my $in, '<', $file or die $!;
+WORD:
+while (my $word = <$in>) {
+    chomp $word;
+    my $l = lc $word;
+    for my $i (2 .. length $word) {
+        next WORD if substr($l, $i - 2, 1) gt substr($l, $i - 1, 1);
+    }
+    if (length($word) > (keys %max)[0]) {
+        %max = (length $word => [$word]);
+    } elsif (length($word) == (keys %max)[0]) {
+        push @{ $max{ length $word } }, $word;
+    }
+}
+say for map @$_, values %max;
+
+__END__
+beefily
+billowy
+chikors
+dikkops
+Elmmott