From 975d2c0891841898a98ad788281ab0de5c969af1 Mon Sep 17 00:00:00 2001
From: Jörg Sommrey <28217714+jo-37@users.noreply.github.com>
Date: Sun, 3 Dec 2023 17:40:16 +0100
Subject: Solution to task 2 in O(N)

---
 challenge-245/jo-37/blog/Blog.md | 14 ++++++++++++--
 challenge-245/jo-37/perl/ch-2.pl | 10 +++++++++-
 2 files changed, 21 insertions(+), 3 deletions(-)

diff --git a/challenge-245/jo-37/blog/Blog.md b/challenge-245/jo-37/blog/Blog.md
index 584d250c3d..7fc77126a7 100644
--- a/challenge-245/jo-37/blog/Blog.md
+++ b/challenge-245/jo-37/blog/Blog.md
@@ -75,10 +75,14 @@ Suppose we have `p = sum(d[i]) mod 3`.
 If the remaining set of digits is not empty, the largest number is formed from the digits in descending order.
 Otherwise there is no solution.
 
+It turns out, that sorting the digits using a standard algorithm would
+be the most expensive operation in this approach.  Thus using a specific
+O(N) sort for a collection of decimal digits.
+
 This results in the following implementation:
 ```
 sub largest_of_three {
-	my (@digits, @ind, $mod) = sort @_;
+    my (@digits, @ind, $mod) = dsort(@_);
     for (0 .. $#digits) {
         # The digit modulo 3
         my $digit = $digits[$_] % 3;
@@ -99,4 +103,10 @@ sub largest_of_three {
     @digits ? 0 + join '', reverse grep defined, @digits : -1;
 }
 
-```
\ No newline at end of file
+sub dsort {
+    my @digits;
+    $digits[$_]++ for @_;
+    map +($_) x ($digits[$_] // 0), 0 .. 9;
+}
+
+```
diff --git a/challenge-245/jo-37/perl/ch-2.pl b/challenge-245/jo-37/perl/ch-2.pl
index ef90057f91..42372a8601 100755
--- a/challenge-245/jo-37/perl/ch-2.pl
+++ b/challenge-245/jo-37/perl/ch-2.pl
@@ -30,7 +30,7 @@ say largest_of_three(@ARGV);
 ### Implementation
 
 sub largest_of_three {
-	my (@digits, @ind, $mod) = sort @_;
+	my (@digits, @ind, $mod) = dsort(@_);
     for (0 .. $#digits) {
         # The digit modulo 3
         my $digit = $digits[$_] % 3;
@@ -51,6 +51,12 @@ sub largest_of_three {
     @digits ? 0 + join '', reverse grep defined, @digits : -1;
 }
 
+sub dsort {
+    my @digits;
+    $digits[$_]++ for @_;
+    map +($_) x ($digits[$_] // 0), 0 .. 9;
+}
+
 
 ### Examples and tests
 
@@ -66,6 +72,8 @@ sub run_tests {
     SKIP: {
         skip "tests" unless $tests;
 
+        say "@{[dsort(qw(1 2 3 4 3 2 3 5 6 7 7 7 1 1 1))]}";
+
         is largest_of_three(6, 4, 3), 63, 'single 1 mod 3';
         is largest_of_three(6, 5, 3), 63, 'single 2 mod 3';
         is largest_of_three(6, 4, 4, 3), 63, 'double 1 mod 3';
-- 
cgit 


From 73e8b8099a9bdf0342e02ee37381748655d6bbf7 Mon Sep 17 00:00:00 2001
From: Jörg Sommrey <28217714+jo-37@users.noreply.github.com>
Date: Sun, 3 Dec 2023 17:43:37 +0100
Subject: Solution to task 2 in O(N)

---
 challenge-245/jo-37/perl/ch-2.pl | 2 --
 1 file changed, 2 deletions(-)

diff --git a/challenge-245/jo-37/perl/ch-2.pl b/challenge-245/jo-37/perl/ch-2.pl
index 42372a8601..a698a9f578 100755
--- a/challenge-245/jo-37/perl/ch-2.pl
+++ b/challenge-245/jo-37/perl/ch-2.pl
@@ -72,8 +72,6 @@ sub run_tests {
     SKIP: {
         skip "tests" unless $tests;
 
-        say "@{[dsort(qw(1 2 3 4 3 2 3 5 6 7 7 7 1 1 1))]}";
-
         is largest_of_three(6, 4, 3), 63, 'single 1 mod 3';
         is largest_of_three(6, 5, 3), 63, 'single 2 mod 3';
         is largest_of_three(6, 4, 4, 3), 63, 'double 1 mod 3';
-- 
cgit