add solutions to challenge-75

3 files changed, 151 insertions, 0 deletions

diff --git a/challenge-075/alexander-pankoff/README b/challenge-075/alexander-pankoff/README
new file mode 100644
index 0000000000..41f67807ac
--- /dev/null
+++ b/challenge-075/alexander-pankoff/README
@@ -0,0 +1 @@
+Solution by Alexander Pankoff
diff --git a/challenge-075/alexander-pankoff/perl/ch-1.pl b/challenge-075/alexander-pankoff/perl/ch-1.pl
new file mode 100755
index 0000000000..ad37e76630
--- /dev/null
+++ b/challenge-075/alexander-pankoff/perl/ch-1.pl
@@ -0,0 +1,86 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use feature qw(signatures say);
+no warnings qw(experimental::signatures experimental::smartmatch);
+
+use List::Util qw(any sum0);
+use Scalar::Util qw(looks_like_number);
+
+# You are given an array of positive numbers @A.
+#
+# Write a script to find the larget rectangle histogram created by the given array.
+# BONUS: Try to print the histogram as shown in the example, if possible.
+
+my ( $S, @C ) = @ARGV;
+
+$S //= 6;
+
+@C = ( 1, 2, 4 ) unless @C;
+
+if (   ( any { !looks_like_number( $_ ) } ( $S, @C ) )
+    || ( any { $_ < 1 } @C ) )
+{
+    usage();
+    exit 1;
+}
+
+my @possible_combinations = possible_combinations( \@C, $S );
+
+say scalar @possible_combinations;
+
+exit 0 unless $ENV{DEBUG};
+
+for my $combination ( @possible_combinations ) {
+    say "(" . join( ', ', @$combination ) . ")";
+}
+
+exit 0;
+
+sub possible_combinations ( $coins, $sum, $cur = [] ) {
+    my $current_sum = sum0 @{$cur};
+
+    return $cur   if $current_sum == $sum;
+    die "invalid" if $current_sum > $sum;
+
+    my @solutions;
+    for my $coin ( @$coins ) {
+        eval {
+            my @sub_solutions = possible_combinations( $coins, $sum, [ @$cur, $coin ] );
+            push @solutions, map {
+                [ sort { $a <=> $b } @$_ ]
+            } @sub_solutions;
+        };
+
+        die $@ if $@ and $@ !~ /invalid/;
+    }
+
+    return unique_combinations( @solutions );
+}
+
+sub unique_combinations(@list) {
+    my @out;
+
+    for my $item ( @list ) {
+        my $found = 0;
+        for my $check ( @out ) {
+            if ( @$check ~~ @$item ) {
+                $found = 1;
+                last;
+            }
+        }
+        push @out, $item unless $found;
+    }
+
+    return @out;
+}
+
+sub usage() {
+    say <<END;
+$0 <SUM> [COINS]
+
+  <SUM>   the sum that should be created
+  [COINS] the set of coins available
+END
+}
diff --git a/challenge-075/alexander-pankoff/perl/ch-2.pl b/challenge-075/alexander-pankoff/perl/ch-2.pl
new file mode 100755
index 0000000000..3bd029a638
--- /dev/null
+++ b/challenge-075/alexander-pankoff/perl/ch-2.pl
@@ -0,0 +1,64 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use feature qw(signatures say);
+no warnings qw(experimental::signatures);
+
+use Scalar::Util qw(looks_like_number);
+use List::Util qw(any min max);
+
+# You are given an array of positive numbers @A.
+#
+# Write a script to find the larget rectangle histogram created by the given array.
+# BONUS: Try to print the histogram as shown in the example, if possible.
+
+my ( @A ) = @ARGV;
+
+@A = ( 2, 1, 4, 5, 3, 7 ) unless @A;
+
+if ( any { !looks_like_number( $_ ) || $_ < 0 } ( @A ) ) {
+    usage();
+    exit 1;
+}
+
+print_histogram( @A );
+
+say largest_rectangle( @A );
+
+exit 0;
+
+sub largest_rectangle(@cols) {
+    return 0 unless @cols;
+
+    max(
+        rectangle_size( @cols ),
+        largest_rectangle( @cols[ 1 .. $#cols ] ),
+        largest_rectangle( @cols[ 0 .. ( $#cols - 1 ) ] )
+    );
+}
+
+sub rectangle_size(@cols) {
+    return scalar @cols * min @cols;
+}
+
+sub print_histogram(@cols) {
+    my $height = max @cols;
+
+    while ( $height ) {
+        say join( ' ', $height, map { $_ >= $height ? '#' : ' ' } @cols );
+        $height--;
+    }
+
+    say join( ' ', map { '_' } ( 0 .. @cols ) );
+    say join( ' ', ' ', @cols );
+}
+
+sub usage() {
+    say <<END
+$0 [A]
+
+  [A] An array of positive integers
+END
+}
+