Solutions to challenge 257

3 files changed, 201 insertions, 0 deletions

diff --git a/challenge-257/jo-37/blog.txt b/challenge-257/jo-37/blog.txt
new file mode 100644
index 0000000000..8354d02fdc
--- /dev/null
+++ b/challenge-257/jo-37/blog.txt
@@ -0,0 +1 @@
+https://github.sommrey.de/the-bears-den/2024/02/23/ch-257.html
diff --git a/challenge-257/jo-37/perl/ch-1.pl b/challenge-257/jo-37/perl/ch-1.pl
new file mode 100755
index 0000000000..93bd7fb00c
--- /dev/null
+++ b/challenge-257/jo-37/perl/ch-1.pl
@@ -0,0 +1,81 @@
+#!/usr/bin/perl -s
+
+use v5.24;
+use Test2::V0 '!float';
+use PDL;
+use PDL::NiceSlice;
+use Benchmark 'cmpthese';
+
+our ($tests, $examples, $benchmark);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [--] [N...]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+N...
+    list of numbers
+
+EOS
+
+
+### Input and Output
+
+say sdc(@ARGV);
+
+
+### Implementation
+
+sub sdc {
+    my $l = long @_;
+    my $si = $l->qsorti;
+    cat($si, sequence($l) - $l->($si)->dummy(0)->enumvec)
+        ->xchg(0,1)->qsortvec->((1));
+}
+
+sub sdc_full {
+    my $l = long @_;
+    ($l < $l->dummy(0))->sumover;
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        is sdc(5, 2, 1, 6)->unpdl, [2, 1, 0, 3], 'example 1';
+        is sdc(1, 2, 0, 3)->unpdl, [1, 2, 0, 3], 'example 2';
+        is sdc(0, 1)->unpdl, [0, 1], 'example 3';
+        is sdc(9, 4, 9, 2)->unpdl, [2, 1, 2, 0], 'example 4';
+
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+    }
+
+    SKIP: {
+        skip "benchmark" unless $benchmark;
+
+        my $n = 10000;
+        my $l = ($n * random $n)->long;
+        ok all(sdc_full($l) == sdc($l)), 'cross-check';
+
+        cmpthese(0, {
+                full => sub {sdc_full($l)},
+                rank => sub {sdc($l)}
+            });
+
+    }
+
+    done_testing;
+    exit;
+}
diff --git a/challenge-257/jo-37/perl/ch-2.pl b/challenge-257/jo-37/perl/ch-2.pl
new file mode 100755
index 0000000000..89027b5768
--- /dev/null
+++ b/challenge-257/jo-37/perl/ch-2.pl
@@ -0,0 +1,119 @@
+#!/usr/bin/perl -s
+
+use v5.24;
+use Test2::V0 '!float';
+use PDL;
+use PDL::NiceSlice;
+
+our ($tests, $examples);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [M]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+M
+    a matrix in any form accepted by the PDL string constructor, e.g.
+    '[[0, 1,-2, 0, 1], [0, 0, 0, 1, 3], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]'
+
+EOS
+
+
+### Input and Output
+
+say 0 + !!is_reduced_echelon("@ARGV");
+
+
+### Implementation
+
+sub is_reduced_echelon {
+	my $m = pdl @_;
+
+    my $allones = whichND($m == 1);
+    my $firstidx = which($allones->(1)->enumvec == 0);
+    my $firstones = $allones->dice('X', $firstidx);
+    return unless $firstones->dim(1) < 2 ||
+        all $firstones((0),0:-2) < $firstones((0),1:-1);
+    for my $firstone ($firstones->dog) {
+        my ($col, $row) = $firstone->list;
+        return unless 1 == sum $m->dice('X', $row)->(0:$col) != 0;
+        return unless 1 == sum $m->dice($col, 'X')->(,0:$row) != 0;
+    }
+    my $zeros = which $m->orover == 0;
+    return unless !$firstones->ngood || !$zeros->ngood ||
+        $firstones->((1))->max < $zeros->min;
+    
+    return unless $zeros->dim(0) + $firstidx->dim(0) == $m->dim(1);
+    
+    1;
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        ok !is_reduced_echelon([
+                [1, 1, 0],
+                [0, 1, 0],
+                [0, 0, 0]
+            ]), 'example 1';
+
+        ok is_reduced_echelon([
+                [0, 1,-2, 0, 1],
+                [0, 0, 0, 1, 3],
+                [0, 0, 0, 0, 0],
+                [0, 0, 0, 0, 0]
+            ]), 'example 2';
+
+        ok is_reduced_echelon([
+                [1, 0, 0, 4],
+                [0, 1, 0, 7],
+                [0, 0, 1,-1]
+            ]), 'example 3';
+
+        ok !is_reduced_echelon([
+                  [0, 1,-2, 0, 1],
+                  [0, 0, 0, 0, 0],
+                  [0, 0, 0, 1, 3],
+                  [0, 0, 0, 0, 0]
+             ]), 'example 4';
+
+        ok !is_reduced_echelon([
+                [0, 1, 0],
+                [1, 0, 0],
+                [0, 0, 0]
+             ]), 'example 5';
+
+        ok !is_reduced_echelon([
+                [4, 0, 0, 0],
+                [0, 1, 0, 7],
+                [0, 0, 1,-1]
+             ]), 'example 6';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        ok is_reduced_echelon([
+                [0, 0, 0],
+                [0, 0, 0]
+            ]), 'zero matrix';
+
+        ok is_reduced_echelon([
+                [0, 0, 1],
+                [0, 0, 0]
+            ]), 'single row';
+	}
+
+    done_testing;
+    exit;
+}