Merge pull request #7273 from Util/branch-for-challenge-195

Add TWC 195 blog post and solutions by Bruce Gray

6 files changed, 205 insertions, 0 deletions

diff --git a/challenge-195/bruce-gray/blog.txt b/challenge-195/bruce-gray/blog.txt
new file mode 100644
index 0000000000..53d34f05c8
--- /dev/null
+++ b/challenge-195/bruce-gray/blog.txt
@@ -0,0 +1 @@
+https://blogs.perl.org/users/bruce_gray/2022/12/twc-195-special_speedy_frequency.html
diff --git a/challenge-195/bruce-gray/perl/ch-1.pl b/challenge-195/bruce-gray/perl/ch-1.pl
new file mode 100644
index 0000000000..a02c0b897a
--- /dev/null
+++ b/challenge-195/bruce-gray/perl/ch-1.pl
@@ -0,0 +1,30 @@
+use v5.36;
+use List::Util qw<uniq>;
+
+sub task1 ( $n ) {
+    return 0 + grep { length == uniq split '' } 1..$n;
+}
+
+
+my @tests = (
+    [ 15, 14 ],
+    [ 35, 32 ],
+
+    [            99,        90 ],
+    [           200,       162 ],
+    [           180,       147 ],
+    [         1_000,       738 ],
+    [        10_000,     5_274 ],
+    [       100_000,    32_490 ],
+    [     1_000_000,   168_570 ],
+#    [    10_000_000,   712_890 ],
+#    [   100_000_000, 2_345_850 ],
+#    [ 1_000_000_000, 5_611_770 ],
+#    [ 9_876_543_210, 8_877_690 ],
+);
+use Test::More;
+plan tests => 0+@tests;
+for (@tests) {
+    my ($in, $expected) = @{$_};
+    is task1($in), $expected, "task1($in) == $expected";
+}
diff --git a/challenge-195/bruce-gray/perl/ch-1_inline.pl b/challenge-195/bruce-gray/perl/ch-1_inline.pl
new file mode 100644
index 0000000000..4ad91318f6
--- /dev/null
+++ b/challenge-195/bruce-gray/perl/ch-1_inline.pl
@@ -0,0 +1,45 @@
+use v5.36;
+use Inline 'C';
+my @tests = (
+    [ 15, 14 ],
+    [ 35, 32 ],
+
+    [            99,        90 ],
+    [           200,       162 ],
+    [           180,       147 ],
+    [         1_000,       738 ],
+    [        10_000,     5_274 ],
+    [       100_000,    32_490 ],
+    [     1_000_000,   168_570 ],
+    [    10_000_000,   712_890 ],
+    [   100_000_000, 2_345_850 ],
+    [ 1_000_000_000, 5_611_770 ],
+    [ 9_876_543_210, 8_877_690 ],
+);
+use Test::More;
+plan tests => 0+@tests;
+for (@tests) {
+    my ($in, $expected) = @{$_};
+    is count_special($in), $expected, "count_special($in) == $expected";
+}
+__END__
+__C__
+int is_special(long x) {
+    int ds[10];
+    memset(ds, 0, 10*sizeof(int));
+    while (x) {
+        if (ds[x % 10]++)
+            return 0;
+        x /= 10;
+    }
+    return 1;
+}
+int count_special(long in) {
+    long x = in > 9876543210 ? 9876543210 : in;
+    int  r = 0;
+    for ( ; x ; x-- ) {
+        if ( is_special(x) )
+            r++;
+    }
+    return r;
+}
diff --git a/challenge-195/bruce-gray/perl/ch-2.pl b/challenge-195/bruce-gray/perl/ch-2.pl
new file mode 100644
index 0000000000..23841e64ae
--- /dev/null
+++ b/challenge-195/bruce-gray/perl/ch-2.pl
@@ -0,0 +1,26 @@
+use v5.36;
+use List::Util    qw<min>;
+use List::UtilsBy qw<max_by>;
+
+sub task2 (@ns) {
+    my %bag;
+    $bag{$_}++ for grep { $_ % 2 == 0 } @ns;
+    return -1 if not %bag;
+
+    return min max_by { $bag{$_} } keys %bag;
+}
+
+
+my @tests = (
+    [ [1,1,2,6,2],  2 ], # Of 2 and 6, 2 appears the most.
+    [ [1,3,5,7  ], -1 ], # No even numbers
+    [ [6,4,4,6,1],  4 ], # Of 4 and 6, both appear twice, so pick 4 (the smallest).
+    
+    [ [2,4,4,6,6],  4 ], # Make sure min of evens does not impact min of max-group
+);
+use Test::More;
+plan tests => 0+@tests;
+for (@tests) {
+    my ($in, $expected) = @{$_};
+    is task2(@{$in}), $expected, "task2(@{$in}) == $expected";
+}
diff --git a/challenge-195/bruce-gray/raku/ch-1.raku b/challenge-195/bruce-gray/raku/ch-1.raku
new file mode 100644
index 0000000000..aa09d4398c
--- /dev/null
+++ b/challenge-195/bruce-gray/raku/ch-1.raku
@@ -0,0 +1,88 @@
+# https://oeis.org/A073531  Number of n-digit positive integers with all digits distinct.
+constant @n-digits-distinct     = 0, 9, |( 9 X* [\*] (9...1) );
+constant @n-digits-distinct-sum = [\+] @n-digits-distinct;
+
+# See blog post for explanation.
+sub task1 ( UInt $n --> UInt ) {
+    constant MAX = 9_876_543_210;
+    return &?ROUTINE(MAX) if $n > MAX;
+
+    # Knuth's "falling powers"; kfp(9,3) == 9*8*7
+    sub kfp ($n, $k) { [*] ( ($n-$k) ^.. $n ) }
+
+    my $nc = $n.chars;
+    my @totals;
+
+    push @totals, @n-digits-distinct-sum[$nc - 1];
+
+    my SetHash $used;
+    for $n.comb».Numeric.kv -> UInt $k, UInt $digit {
+
+        my UInt $combinations_in_rightward_places = kfp(9 - $k, $nc - $k - 1);
+
+        my Range $space_below_digit = (      0 + (1 if $k == 0   ) )
+                                   .. ( $digit - (1 if $k < $nc-1) );
+
+        my Set $using_for_this_digit = $space_below_digit (-) $used;
+
+        push @totals, $using_for_this_digit.elems
+                    * $combinations_in_rightward_places;
+
+        $used{$digit}++;
+    }
+
+    return @totals.sum;
+}
+# This version is simpler to understand, but does not perform as well.
+# It does the initial optimization to skip over about .log10 places,
+# then generates all the combinations with the correct leading digit,
+# filters on which ones are less than $n.
+sub task1_one_big_skip ( UInt $n --> UInt ) {
+    constant MAX = 9_876_543_210;
+    return &?ROUTINE(MAX) if $n > MAX;
+
+    my @totals;
+    my $lead  = $n.substr(0, 1);
+    my $core  = $n.chars - 1;
+
+    push @totals, @n-digits-distinct-sum[$core];
+
+    push @totals, +combinations(9,$core) * ([*] 1..$core) * ($lead-1);
+
+    my $L3 = 0;
+    for (0..9).grep(* != $lead).combinations($core) -> @comb {
+        $L3 += +@comb.permutations.grep: { ($lead ~ .join) <= $n };
+    }
+    push @totals, $L3;
+    return @totals.sum;
+}
+
+
+my @tests =
+    ( 15, 14 ),
+    ( 35, 32 ),
+
+    (            99,        90 ),
+    (           200,       162 ),
+    (           180,       147 ),
+    (         1_000,       738 ),
+    (        10_000,     5_274 ),
+    (       100_000,    32_490 ),
+    (     1_000_000,   168_570 ),
+    (    10_000_000,   712_890 ),
+    (   100_000_000, 2_345_850 ),
+    ( 1_000_000_000, 5_611_770 ),
+    ( 9_876_543_210, 8_877_690 ),
+;
+use Test;
+plan 1+@tests;
+
+is (map &task1, 1..99),
+   (flat (1..10,10..20,20..30,30..40,40..50,50..60,60..70,70..80,80..90,90)),
+   "First 99";
+
+for @tests -> ($in, $expected) {
+    my $got = task1($in);
+
+    is $got, $expected, "task1($in) == $expected";
+}
diff --git a/challenge-195/bruce-gray/raku/ch-2.raku b/challenge-195/bruce-gray/raku/ch-2.raku
new file mode 100644
index 0000000000..d38fca4107
--- /dev/null
+++ b/challenge-195/bruce-gray/raku/ch-2.raku
@@ -0,0 +1,15 @@
+sub task2 (@ns) { @ns.grep( * %% 2 ).Bag.max({ .value, -.key }).?key // -1 }
+
+
+my @tests =
+    ( (1,1,2,6,2),  2 ), # Of 2 and 6, 2 appears the most.
+    ( (1,3,5,7  ), -1 ), # No even numbers
+    ( (6,4,4,6,1),  4 ), # Of 4 and 6, both appear twice, so pick 4 (the smallest).
+
+    ( (2,4,4,6,6),  4 ), # Make sure min of evens does not impact min of max-group
+;
+use Test;
+plan +@tests;
+for @tests -> ($in, $expected) {
+    is task2($in), $expected, "task2($in) == $expected";
+}