first - pass - day job again? - even more so for my brother - did you know BR used to have 66 minutes in the hour so they could solve the 2nd problem...

2 files changed, 123 insertions, 0 deletions

diff --git a/challenge-128/james-smith/perl/ch-1.pl b/challenge-128/james-smith/perl/ch-1.pl
new file mode 100644
index 0000000000..ab507a7726
--- /dev/null
+++ b/challenge-128/james-smith/perl/ch-1.pl
@@ -0,0 +1,66 @@
+#!/usr/local/bin/perl
+
+use strict;
+
+use warnings;
+use feature qw(say);
+use Test::More;
+use Benchmark qw(cmpthese timethis);
+use Data::Dumper qw(Dumper);
+
+my @arr1 = (
+  [qw( 1 0 0 0 1 0 )],
+  [qw( 1 1 0 0 0 1 )],
+  [qw( 1 0 0 0 0 0 )],
+);
+my @arr2 = (
+  [qw( 0 0 1 1 )],
+  [qw( 0 0 0 1 )],
+  [qw( 0 0 1 0 )],
+);
+my @TESTS = ( [ \@arr1, '6 2 3' ], [ \@arr2, '6 2 3' ],);
+
+is( "@{ find_empty( $_->[0]) }", $_->[1] ) foreach @TESTS;
+
+done_testing();
+
+sub find_empty {
+  my @rows = @{$_[0]};
+  my $h = @rows-1;
+  my $w = @{$rows[0]}-1;
+  my @runs = map { [1 - $_->[-1]] } @rows;
+
+  ## First pass through the array - we calculate how many
+  ## 0s are in the cell and to the right... So for example 1 we get
+  ##   0 3 2 1 0 1
+  ##   0 0 3 2 1 0
+  ##   0 5 4 3 2 1
+  ## This is O(n^2)
+  foreach my $i (reverse 0..$w-1) {
+    foreach my $j (0..$h) {
+      unshift @{$runs[$j]}, $rows[$j][$i] ? 0 : $runs[$j][0]+1;
+    }
+  }
+  ## Now we have to loop over all squares and check rectangles starting
+  ## at the square and going down and to the right...
+  ## This is now an O(n^3) operation reduced from the O(n^4) operation
+  ## by working with run lengths...
+  ## Effectively the O(n^2) operation above removes the inner loop of
+  ## scanning right for 0s...
+
+  my $max_area = [0,0,0];
+  foreach my $x ( 0..$w ) {
+    foreach my $y ( 0..$h ) {
+      next unless $runs[$y][$x];  ## Short cut answer will be 0
+      my $max_w = 1e9;
+      foreach my $j ( $y..$h ) {
+        $max_w = $runs[$j][$x] if $runs[$j][$x] < $max_w;
+        last unless $max_w;   ## Short cut all subsequent answers will zero
+        my $area = $max_w * ($j-$y+1);
+        $max_area = [$area,$max_w,$j-$y+1] if $area>$max_area->[0];
+      }
+    }
+  }
+  return $max_area;
+}
+
diff --git a/challenge-128/james-smith/perl/ch-2.pl b/challenge-128/james-smith/perl/ch-2.pl
new file mode 100644
index 0000000000..05b63d47ea
--- /dev/null
+++ b/challenge-128/james-smith/perl/ch-2.pl
@@ -0,0 +1,57 @@
+#!/usr/local/bin/perl
+
+use strict;
+
+use warnings;
+use feature qw(say);
+use Test::More;
+use Benchmark qw(cmpthese timethis);
+use Data::Dumper qw(Dumper);
+
+my @TESTS = (
+  [ [qw(11:20 14:30)],
+    [qw(11:50 15:00)],
+    1 ],
+  [ [qw(10:20 11:00 11:10 12:20 16:20 19:00)],
+    [qw(10:30 13:20 12:40 12:50 20:20 21:20)],
+    3 ]
+);
+
+is( bump_platform( $_->[0], $_->[1] ), $_->[2] ) foreach @TESTS;
+is( bump_platform_keep_trains( $_->[0], $_->[1] ), $_->[2] ) foreach @TESTS;
+
+done_testing();
+
+sub bump_platform {
+  my @arr = @{shift @_};
+  my @dep = @{shift @_};
+  #shift @{$arr};
+  my @plat = ();#(shift @{$dep});
+  OUTER: foreach my $st (@arr) {
+    foreach(0..$#plat) {
+      next unless $st gt $plat[$_];
+      $plat[$_] = shift @dep;
+      next OUTER;
+    }
+    push @plat,shift @dep;
+  }
+  return scalar @plat;
+}
+
+sub bump_platform_keep_trains {
+  my @arr = @{shift @_};
+  my @dep = @{shift @_};
+  my $t = 0;
+  my @plat; # = ( [ [shift @{$arr}, shift @{$dep}, my $t=1] ] );
+  OUTER: foreach my $st (@arr) {
+    foreach(@plat) {
+      next unless $st gt $_->[-1][1];
+      push @{$_}, [ $st, (shift @dep), ++$t ];
+      next OUTER;
+    }
+    push @plat, [ [ $st, (shift @dep), ++$t ] ];
+  }
+  print Dumper( \@plat );
+  return scalar @plat;
+}
+