Re: Faster (but uglier) PWC 350-2 solutions

FWIW my solution just limits the range of witnesses:

        for my $witness (2..int((10**length($i) - 1) / $i)) {
            if ($i_sorted eq join '', sort split //, $i * $witness) {
                if (++$pairs == $count) {
                    ++$qualifying_integers;
                    next I;
                }
            }
        }
        # maximum witness can't be more than i's first digit
        for my $witness (2..substr $i, 0, 1) {
            if (!( $i % $witness ) && $i_sorted eq join '', sort split
+ //, $i / $witness) {
                if (++$pairs == $count) {
                    ++$qualifying_integers;
                    next I;
                }
            }
        }
[download]

and tries to limit the ops executed in the loop body. To take advantage of other witness elimination, you'd unwrap the outer loop and have special code for e.g multiples of 3, but that if a lot of duplication. You'd get a much better speed bump using Inline for at least the "does it have the same digits" check. My go solution is much much faster. But all the conversions from numbers to strings to runes make it a lot longer.

Python was interesting; it lacks the ability to continue an outer loop, so the two inner loop approach needed an additional flag variable. But Python's iterator design made a single inner loop possible, at a slight speed penalty but producing the tersest code.

Comment on Re: Faster (but uglier) PWC 350-2 solutions Download Code

Replies are listed 'Best First'.
Re^2: Faster (but uglier) PWC 350-2 solutions by Anonymous Monk on Dec 10, 2025 at 16:01 UTC
You'd get a much better speed bump using Inline for at least the "does it have the same digits" check. No. Chained transliterations are too trivial, any subroutine (or C function) call seems more expensive. Results are not too different with "return 1" line uncommented. use Inline C => <<'END_OF_C'; int histcmp( SV* sv1, SV* sv2 ) { // return 1; STRLEN len; char* s1 = SvPVbyte( sv1, len ); char* s2 = SvPVbyte( sv2, len ); char h1[ 10 ]; char h2[ 10 ]; memset( h1, 0, sizeof( h1 )); memset( h2, 0, sizeof( h2 )); for ( int i = 0; i < len; i ++ ) { h1[ s1[ i ] - '0' ] ++; h2[ s2[ i ] - '0' ] ++; } return memcmp( h1, h2, 10 ); } END_OF_C sub pwc_c { my ( $from, $to, $target ) = @_; use integer; my @witnesses = ([ 4, 7 ], [ 2 .. 9 ]); my ( %pairs, $j ); for ( my $i = ( $from + 2 ) / 3 * 3; $i <= $to; $i += 3 ) { my $k = $i % 9 ? 0 : 1; for ( @{ $witnesses[ $k ]}) { last if length( $j = $i * $_ ) != length( $i ); $pairs{ $i }{ $j } = $_ unless histcmp( $i, $j ) } for ( @{ $witnesses[ $k ]}) { last if length( $j = $i / $_ ) != length( $i ); $pairs{ $i }{ $j } = -$_ unless $i % $_ \|\| exists $pairs{ $j } && exists $pairs{ $j }{ $i } \|\| histcmp( $i, $j ) } } return scalar grep { %$_ >= $target } values %pairs } cmpthese -3, { pwc_c => sub { pwc_c( 1500, 2500, 1 )}, ugly => sub { ugly( 1500, 2500, 1 )}, }; cmpthese -3, { pwc_c => sub { pwc_c( 13_427_000, 14_100_000, 2 )}, ugly => sub { ugly( 13_427_000, 14_100_000, 2 )}, }; # Rate pwc_c ugly # pwc_c 2865/s -- -12% # ugly 3251/s 13% -- # Rate pwc_c ugly # pwc_c 3.42/s -- -9% # ugly 3.75/s 10% -- [download]	[reply] [d/l]
Re^2: Faster (but uglier) PWC 350-2 solutions by LanX (Saint) on Dec 10, 2025 at 00:09 UTC
In the first loop you check for $i being A and in the second for $i being B hence `$i / $witness` . That's a different interpretation° of the task `B = A * k` , the OP was only doing the A part. Cheers Rolf _{(addicted to the Perl Programming Language :) see Wikisyntax for the Monastery} °) According to Choroba that's the fun part of PWC ;-)	[reply] [d/l] [select]
Re^3: Faster (but uglier) PWC 350-2 solutions by ysth (Canon) on Dec 10, 2025 at 00:46 UTC
None of the examples involve finding A given B, but that just means they work either way. But to me the problem statement is clear: "the number of integers $i in the range $from <= $i <= $to that belong to at least $count different shuffle pairs".	[reply]
Re^4: Faster (but uglier) PWC 350-2 solutions by LanX (Saint) on Dec 10, 2025 at 02:05 UTC
See, different interpretations! All examples list the smallest A first. And B = A * k is explicit about k being an integer. For the other way k would need to be a fraction. Let's agree that only God knows. (and probably Choroba ;-) Cheers Rolf _{(addicted to the Perl Programming Language :) see Wikisyntax for the Monastery}	[reply]
Re^2: Faster (but uglier) PWC 350-2 solutions by Anonymous Monk on Dec 10, 2025 at 18:19 UTC
My go solution is much much faster. How much (if I may)? I've never run Go nor have it; at ATO (can link if requested), your Go function runs in ~600 mks and ~900 ms for Examples 2 and 4 arguments respectively. I know it's a silly test. Perl results from my previous answer, for the same args, are better when run locally at rather old PC	[reply]
Re^2: Faster (but uglier) PWC 350-2 solutions by Anonymous Monk on Dec 09, 2025 at 23:12 UTC
I think if in e.g. "Example 2" the `$to` was e.g. 8500, then your solution would find all 3 pairs again and report false positives. I.e. stronger accounting is required. I'm not sure I'm happy with my own accounting, on the 2nd thought. If `$count` in "Example 3" was not "5" but "1", then how many items would be added to the result for "1428570"? 1 or 5? The "at least" in the wording of the challenge seems to imply that "1". Or such is my interpretation (PWC ambiguous as usual). But then it follows, that you can't break out early with "`next I;`". Because there will be false positives later if `$to` was higher (see?). I had a similar "`next OUTER;`" in initial drafts, but then decided against it.	[reply] [d/l] [select]
Re^3: Faster (but uglier) PWC 350-2 solutions by ysth (Canon) on Dec 09, 2025 at 23:42 UTC
I don't know what you mean by false positives? The test is how many numbers in the range are part of at least count pairs. Having both ends of a pair in the range just means both numbers count. And each number only counts once. Can you explain what you think is ambiguous? (Agreed that PWC often is; usually the examples clarify, but not always.)	[reply]
Re^4: Faster (but uglier) PWC 350-2 solutions by Anonymous Monk on Dec 10, 2025 at 10:11 UTC
The test is how many numbers in the range are part of at least count pairs. Didn't they ask for "different pairs"? 1782 and 7128 belong to the same pair. OTOH, "1428570 belongs to 5 different shuffle pairs" -- yeah, how else, what's the alternative? What does that even mean to "belong to several pairs which are not different"? Replicate any as much as I please? Perhaps your interpretation is correct, if only by Occam's razor, just remove one meaningless word globally in the task. Sorry, never mind.	[reply]