diff options
| -rw-r--r-- | challenge-245/jo-37/blog/Blog.md | 14 | ||||
| -rwxr-xr-x | challenge-245/jo-37/perl/ch-2.pl | 8 |
2 files changed, 19 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..a698a9f578 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 |