Merge pull request #9649 from packy/master

Challenge 257 solutions by Packy Anderson

8 files changed, 498 insertions, 1 deletions

diff --git a/challenge-257/packy-anderson/README.md b/challenge-257/packy-anderson/README.md
index c576612b58..0a87407d66 100644
--- a/challenge-257/packy-anderson/README.md
+++ b/challenge-257/packy-anderson/README.md
@@ -16,4 +16,4 @@
 
 ## Blog Post
 
-[Merge the Maximum String Pairs](https://packy.dardan.com/b/Hg)
+[Reduced is Smaller!](https://packy.dardan.com/b/Ht)
diff --git a/challenge-257/packy-anderson/blog.txt b/challenge-257/packy-anderson/blog.txt
new file mode 100644
index 0000000000..fef7769217
--- /dev/null
+++ b/challenge-257/packy-anderson/blog.txt
@@ -0,0 +1 @@
+https://packy.dardan.com/b/Ht
\ No newline at end of file
diff --git a/challenge-257/packy-anderson/perl/ch-1.pl b/challenge-257/packy-anderson/perl/ch-1.pl
new file mode 100755
index 0000000000..43a3f8a66c
--- /dev/null
+++ b/challenge-257/packy-anderson/perl/ch-1.pl
@@ -0,0 +1,32 @@
+#!/usr/bin/env perl
+use v5.38;
+
+sub smallerThan(@ints) {
+  my @counts;
+  foreach my $i (0 .. $#ints) {
+    @counts[$i] = 0;
+    foreach my $j (0 .. $#ints) {
+      next if $i == $j;
+      $counts[$i]++ if $ints[$j] < $ints[$i];
+    }
+  }
+  return @counts;
+}
+
+sub solution(@ints) {
+  say 'Input: @ints = (' . join(', ', @ints) . ')';
+  my @counts = smallerThan(@ints);
+  say 'Output: (' . join(', ', @counts) . ')';
+}
+
+say "Example 1:";
+solution(5, 2, 1, 6);
+
+say "\nExample 2:";
+solution(1, 2, 0, 3);
+
+say "\nExample 3:";
+solution(0, 1);
+
+say "\nExample 4:";
+solution(9, 4, 9, 2);
\ No newline at end of file
diff --git a/challenge-257/packy-anderson/perl/ch-2.pl b/challenge-257/packy-anderson/perl/ch-2.pl
new file mode 100755
index 0000000000..eec5339e89
--- /dev/null
+++ b/challenge-257/packy-anderson/perl/ch-2.pl
@@ -0,0 +1,140 @@
+#!/usr/bin/env perl
+use v5.38;
+
+sub rowIsEntirelyZeros(@row) {
+  foreach my $n (@row) {
+    next if $n == 0;
+    return 0;
+  }
+  return 1;
+}
+
+sub rowHasLeadingOne(@row) {
+  foreach my $n (@row) {
+    next if $n == 0;
+    return $n == 1;
+  }
+}
+
+sub leadingOnePosition(@row) {
+  foreach my $i (0 .. $#row) {
+    next if $row[$i] == 0;
+    return $i;
+  }
+}
+
+sub columnHasZerosBesidesLeadingOne($matrix, $col) {
+  my $count = 0;
+  foreach my $row (@$matrix) {
+    next if $row->[$col] == 0; # skip zeroes
+    return 0 if $row->[$col] != 1; # fail if not one
+    $count++; # count ones
+  }
+  return $count == 1;
+}
+
+sub isReducedRowEchelon(@matrix) {
+  my $foundAllZeroRow = 0;
+  my $lastLeadingOnePos = -1; # avoid comparison with undef
+  foreach my $row (@matrix) {
+    if (! rowIsEntirelyZeros(@$row)) {
+      # 1. If a row does not consist entirely of zeros, then
+      #    the first nonzero number in the row is a 1. We call
+      #    this the leading 1.
+      return 0 unless rowHasLeadingOne(@$row);
+
+      # 2. If there are any rows that consist entirely of zeros,
+      #    then they are grouped together at the bottom of the
+      #    matrix.
+      return 0 if $foundAllZeroRow;
+
+      # 3. In any two successive rows that do not consist
+      #    entirely of zeros, the leading 1 in the lower row
+      #    occurs farther to the right than the leading 1 in
+      #    the higher row.
+      my $thisLeadingOnePos = leadingOnePosition(@$row);
+      return 0 if $lastLeadingOnePos > $thisLeadingOnePos;
+      $lastLeadingOnePos = $thisLeadingOnePos;
+
+      # 4. Each column that contains a leading 1 has zeros
+      #    everywhere else in that column.
+      return 0 unless columnHasZerosBesidesLeadingOne(
+        \@matrix, $thisLeadingOnePos
+      );
+    }
+    else {
+      $foundAllZeroRow = 1;
+    }
+  }
+  return 1;
+}
+
+sub formatMatrix($matrix, $indent=12) {
+  my @output;
+  foreach my $row (@$matrix) {
+    my $output_row = q{ } x $indent . "  [ ";
+    $output_row .= join(', ', map { sprintf "%2d", $_ } @$row) . ']';
+    push @output, $output_row;
+  }
+  return "[\n"
+       . join(",\n", @output)
+       . "\n"
+       . q{ } x $indent . "]";
+}
+
+sub solution(@matrix) {
+  say 'Input: $M = ' . formatMatrix(\@matrix);
+  my $output = isReducedRowEchelon(@matrix);
+  say 'Output: ' . $output;
+}
+
+say "Example 1:";
+solution(
+  [1, 1, 0],
+  [0, 1, 0],
+  [0, 0, 0]
+);
+
+say "\nExample 2:";
+solution(
+  [0, 1,-2, 0, 1],
+  [0, 0, 0, 1, 3],
+  [0, 0, 0, 0, 0],
+  [0, 0, 0, 0, 0]
+);
+
+say "\nExample 3:";
+solution(
+  [1, 0, 0, 4],
+  [0, 1, 0, 7],
+  [0, 0, 1,-1]
+);
+
+say "\nExample 4:";
+solution(
+  [0, 1,-2, 0, 1],
+  [0, 0, 0, 0, 0],
+  [0, 0, 0, 1, 3],
+  [0, 0, 0, 0, 0]
+);
+
+say "\nExample 5:";
+solution(
+  [0, 1, 0],
+  [1, 0, 0],
+  [0, 0, 0]
+);
+
+say "\nExample 6:";
+solution(
+  [4, 0, 0, 0],
+  [0, 1, 0, 7],
+  [0, 0, 1,-1]
+);
+
+say "\nExample 7:";
+solution(
+  [1, 0, -1],
+  [0, 1, 1],
+  [0, 0, 1]
+);
diff --git a/challenge-257/packy-anderson/python/ch-1.py b/challenge-257/packy-anderson/python/ch-1.py
new file mode 100755
index 0000000000..85c2dd0c36
--- /dev/null
+++ b/challenge-257/packy-anderson/python/ch-1.py
@@ -0,0 +1,29 @@
+#!/usr/bin/env python
+
+def smallerThan(ints):
+  counts = []
+  for i in range(len(ints)):
+    counts.append(0)
+    for j in range(len(ints)):
+      if i != j and ints[j] < ints[i]: counts[i] += 1
+  return counts
+
+def comma_join(arr):
+    return ', '.join(map(lambda i: str(i), arr))
+
+def solution(ints):
+    print(f'Input: @ints = ({comma_join(ints)})')
+    counts = smallerThan(ints)
+    print(f'Output: ({comma_join(counts)})')
+
+print('Example 1:')
+solution([5, 2, 1, 6])
+
+print('\nExample 2:')
+solution([1, 2, 0, 3])
+
+print('\nExample 3:')
+solution([0, 1])
+
+print('\nExample 4:')
+solution([9, 4, 9, 2])
\ No newline at end of file
diff --git a/challenge-257/packy-anderson/python/ch-2.py b/challenge-257/packy-anderson/python/ch-2.py
new file mode 100755
index 0000000000..ecb171cf4c
--- /dev/null
+++ b/challenge-257/packy-anderson/python/ch-2.py
@@ -0,0 +1,122 @@
+#!/usr/bin/env python
+
+def rowIsEntirelyZeros(row):
+    for n in row:
+        if not n == 0: return 0
+    return 1
+
+def rowHasLeadingOne(row):
+    for n in row:
+        if not n == 0: return n == 1
+
+def leadingOnePosition(row):
+    for i in range(len(row)):
+        if not row[i] == 0: return i
+
+def columnHasZerosBesidesLeadingOne(matrix, col):
+    count = 0
+    for row in matrix:
+        if not row[col] == 0: # skip zeroes
+            if row[col] != 1: return 0 # fail if not one
+            count += 1 # count ones
+    return count == 1
+
+def isReducedRowEchelon(matrix):
+    foundAllZeroRow = 0
+    lastLeadingOnePos = -1 # avoid comparison with undef
+    for row in matrix:
+        if not rowIsEntirelyZeros(row):
+            # 1. If a row does not consist entirely of zeros,
+            #    then the first nonzero number in the row is
+            #    a 1. We call this the leading 1.
+            if not rowHasLeadingOne(row): return 0 
+
+            # 2. If there are any rows that consist entirely
+            #    of zeros, then they are grouped together at
+            #    the bottom of the matrix.
+            if foundAllZeroRow: return 0
+
+            # 3. In any two successive rows that do not consist
+            #    entirely of zeros, the leading 1 in the lower row
+            #    occurs farther to the right than the leading 1 in
+            #    the higher row.
+            thisLeadingOnePos = leadingOnePosition(row)
+            if lastLeadingOnePos > thisLeadingOnePos: return 0
+            lastLeadingOnePos = thisLeadingOnePos
+
+            # 4. Each column that contains a leading 1 has zeros
+            #    everywhere else in that column.
+            if not columnHasZerosBesidesLeadingOne(
+                matrix, thisLeadingOnePos
+            ): return 0
+        else:
+            foundAllZeroRow = 1
+    return 1
+
+def formatMatrix(matrix, indent=12):
+    output = []
+    for row in matrix:
+        output_row = ' ' * indent + '  ['
+        output_row += ', '.join(map(lambda i: str(i), row))
+        output_row += ']'
+        output.append(output_row)
+
+    return(
+        "[\n" + ",\n".join(output) + "\n" +
+        ' ' * indent + ']'
+    )
+
+def solution(matrix):
+    print(f'Input: $M = {formatMatrix(matrix)}')
+    print(f'Output: {isReducedRowEchelon(matrix)}')
+
+print('Example 1:')
+solution([
+  [1, 1, 0],
+  [0, 1, 0],
+  [0, 0, 0]
+])
+
+print('\nExample 2:')
+solution([
+  [0, 1,-2, 0, 1],
+  [0, 0, 0, 1, 3],
+  [0, 0, 0, 0, 0],
+  [0, 0, 0, 0, 0]
+])
+
+print('\nExample 3:')
+solution([
+  [1, 0, 0, 4],
+  [0, 1, 0, 7],
+  [0, 0, 1,-1]
+])
+
+print('\nExample 4:')
+solution([
+  [0, 1,-2, 0, 1],
+  [0, 0, 0, 0, 0],
+  [0, 0, 0, 1, 3],
+  [0, 0, 0, 0, 0]
+])
+
+print('\nExample 5:')
+solution([
+  [0, 1, 0],
+  [1, 0, 0],
+  [0, 0, 0]
+])
+
+print('\nExample 6:')
+solution([
+  [4, 0, 0, 0],
+  [0, 1, 0, 7],
+  [0, 0, 1,-1]
+])
+
+print('\nExample 7:')
+solution([
+  [1, 0, -1],
+  [0, 1, 1],
+  [0, 0, 1]
+])
\ No newline at end of file
diff --git a/challenge-257/packy-anderson/raku/ch-1.raku b/challenge-257/packy-anderson/raku/ch-1.raku
new file mode 100755
index 0000000000..399e111cf5
--- /dev/null
+++ b/challenge-257/packy-anderson/raku/ch-1.raku
@@ -0,0 +1,32 @@
+#!/usr/bin/env raku
+use v6;
+
+sub smallerThan(@ints) {
+  my @counts;
+  for 0 .. @ints.end -> $i {
+    @counts[$i] = 0;
+    for 0 .. @ints.end -> $j {
+      next if $i == $j;
+      @counts[$i]++ if @ints[$j] < @ints[$i];
+    }
+  }
+  return @counts;
+}
+
+sub solution(@ints) {
+  say 'Input: @ints = (' ~ @ints.join(', ') ~ ')';
+  my @counts = smallerThan(@ints);
+  say 'Output: (' ~ @counts.join(', ') ~ ')';
+}
+
+say "Example 1:";
+solution([5, 2, 1, 6]);
+
+say "\nExample 2:";
+solution([1, 2, 0, 3]);
+
+say "\nExample 3:";
+solution([0, 1]);
+
+say "\nExample 4:";
+solution([9, 4, 9, 2]);
\ No newline at end of file
diff --git a/challenge-257/packy-anderson/raku/ch-2.raku b/challenge-257/packy-anderson/raku/ch-2.raku
new file mode 100755
index 0000000000..b174afb43b
--- /dev/null
+++ b/challenge-257/packy-anderson/raku/ch-2.raku
@@ -0,0 +1,141 @@
+#!/usr/bin/env raku
+use v6;
+
+sub rowIsEntirelyZeros(@row) {
+  for @row -> $n {
+    next if $n == 0;
+    return 0;
+  }
+  return 1;
+}
+
+sub rowHasLeadingOne(@row) {
+  for @row -> $n {
+    next if $n == 0;
+    return $n == 1;
+  }
+}
+
+sub leadingOnePosition(@row) {
+  for 0 .. @row.end -> $i {
+    next if @row[$i] == 0;
+    return $i;
+  }
+}
+
+sub columnHasZerosBesidesLeadingOne(@matrix, $col) {
+  my $count = 0;
+  for @matrix -> @row {
+    next if @row[$col] == 0; # skip zeroes
+    return 0 if @row[$col] != 1; # fail if not one
+    $count++; # count ones
+  }
+  return $count == 1;
+}
+
+sub isReducedRowEchelon(@matrix) {
+  my $foundAllZeroRow = 0;
+  my $lastLeadingOnePos = -1; # avoid comparison with undef
+  for @matrix -> @row {
+    if (! rowIsEntirelyZeros(@row)) {
+      # 1. If a row does not consist entirely of zeros, then
+      #    the first nonzero number in the row is a 1. We call
+      #    this the leading 1.
+      return 0 unless rowHasLeadingOne(@row);
+
+      # 2. If there are any rows that consist entirely of zeros,
+      #    then they are grouped together at the bottom of the
+      #    matrix.
+      return 0 if $foundAllZeroRow;
+
+      # 3. In any two successive rows that do not consist
+      #    entirely of zeros, the leading 1 in the lower row
+      #    occurs farther to the right than the leading 1 in
+      #    the higher row.
+      my $thisLeadingOnePos = leadingOnePosition(@row);
+      return 0 if $lastLeadingOnePos > $thisLeadingOnePos;
+      $lastLeadingOnePos = $thisLeadingOnePos;
+
+      # 4. Each column that contains a leading 1 has zeros
+      #    everywhere else in that column.
+      return 0 unless columnHasZerosBesidesLeadingOne(
+        @matrix, $thisLeadingOnePos
+      );
+    }
+    else {
+      $foundAllZeroRow = 1;
+    }
+  }
+  return 1;
+}
+
+sub formatMatrix(@matrix, $indent=12) {
+  my @output;
+  for @matrix -> @row {
+    my $output_row = q{ } x $indent ~ "  [ ";
+    $output_row ~= @row.map({ sprintf "%2d", $_ })
+                       .join(', ') ~ "]";
+    @output.push($output_row);
+  }
+  return "[\n"
+       ~ @output.join(",\n")
+       ~ "\n"
+       ~ q{ } x $indent ~ "]";
+}
+
+sub solution(@matrix) {
+  say 'Input: $M = ' ~ formatMatrix(@matrix);
+  my $output = isReducedRowEchelon(@matrix);
+  say 'Output: ' ~ $output;
+}
+
+say "Example 1:";
+solution([
+  [1, 1, 0],
+  [0, 1, 0],
+  [0, 0, 0]
+]);
+
+say "\nExample 2:";
+solution([
+  [0, 1,-2, 0, 1],
+  [0, 0, 0, 1, 3],
+  [0, 0, 0, 0, 0],
+  [0, 0, 0, 0, 0]
+]);
+
+say "\nExample 3:";
+solution([
+  [1, 0, 0, 4],
+  [0, 1, 0, 7],
+  [0, 0, 1,-1]
+]);
+
+say "\nExample 4:";
+solution([
+  [0, 1,-2, 0, 1],
+  [0, 0, 0, 0, 0],
+  [0, 0, 0, 1, 3],
+  [0, 0, 0, 0, 0]
+]);
+
+say "\nExample 5:";
+solution([
+  [0, 1, 0],
+  [1, 0, 0],
+  [0, 0, 0]
+]);
+
+say "\nExample 6:";
+solution([
+  [4, 0, 0, 0],
+  [0, 1, 0, 7],
+  [0, 0, 1,-1]
+]);
+
+say "\nExample 7:";
+solution([
+  [1, 0, -1],
+  [0, 1, 1],
+  [0, 0, 1]
+]);