| 05 December 2025 | Challenge 350 |
Shuffled Strings
Task 1: Good Substrings
Submitted by: Mohammad Sajid Anwar
You are given a string.
Write a script to return the number of good substrings of length three in the given string.
A string is good if there are no repeated characters.
Example 1
Input: $str = "abcaefg"
Output: 5
Good substrings of length 3: abc, bca, cae, aef and efg
Example 2
Input: $str = "xyzzabc"
Output: 3
Good substrings of length 3: "xyz", "zab" and "abc"
Example 3
Input: $str = "aababc"
Output: 1
Good substrings of length 3: "abc"
Example 4
Input: $str = "qwerty"
Output: 4
Good substrings of length 3: "qwe", "wer", "ert" and "rty"
Example 5
Input: $str = "zzzaaa"
Output: 0
Solution
Perl
Using a regex to solve this task.
- capture a single character
- look ahead for:
- negative look ahead for same character
- capture the next single character
- negative look ahead for the first or second captured characters
- another character
This regex will match any good substring of length 3. As the second capture is not of interest for the final result, the complete positive look-ahead assertion is encapsulated in a postponed sub-expression that does not participate in the visible capture groups.
sub good_substrings {
scalar (() = shift =~ /(.)(?=(??{qr{(?!$1)(.)(?!$1|\g{-1}).}}))/g);
}
See the full solution to task 1.
J
Following a completely numeric approach in J.
Let x be the size of the good substrings.
Whether an array y does contain exactly x different values can be checked with the sentence:
x = #~. y
Transformed into a monadic verb operating on y this can be written as:
x&=@:#@:~.
This verb shall be applied to all infixes of size x from the input array y:
x(x&=@:#@:~.)\ y
resulting an an indicator array that has a 1 for every x-good substring.
The sum over these indicators produces the desired result for length x:
GoodStrings =: {{+/ x(x&=@:#@:~.)\ y}}
echo 3 GoodStrings 'xyzzabc'
For this implementation it it irrelevant if the input data is a string or a numeric array.
See the full solution.
Task 2: Shuffle Pairs
Submitted by: E. Choroba
If two integers A <= B have the same digits but in different orders, we say that they belong to the same shuffle pair if and only if there is an integer k such that A = B * k. k is called the witness of the pair.
For example, 1359 and 9513 belong to the same shuffle pair, because 1359 * 7 = 9513.
Interestingly, some integers belong to several different shuffle pairs. For example, 123876 forms one shuffle pair with 371628, and another with 867132, as 123876 * 3 = 371628, and 123876 * 7 = 867132.
Write a function that for a given $from, $to, and $count returns the number of integers $i in the range $from <= $i <= $to that belong to at least $count different shuffle pairs.
PS: Inspired by a conversation between Mark Dominus and Simon Tatham at Mastodon.
Example 1
Input: $from = 1, $to = 1000, $count = 1
Output: 0
There are no shuffle pairs with elements less than 1000.
Example 2
Input: $from = 1500, $to = 2500, $count = 1
Output: 3
There are 3 integers between 1500 and 2500 that belong to shuffle pairs.
1782, the other element is 7128 (witness 4)
2178, the other element is 8712 (witness 4)
2475, the other element is 7425 (witness 3)
Example 3
Input: $from = 1_000_000, $to = 1_500_000, $count = 5
Output: 2
There are 2 integers in the given range that belong to 5 different shuffle pairs.
1428570 pairs with 2857140, 4285710, 5714280, 7142850, and 8571420
1429857 pairs with 2859714, 4289571, 5719428, 7149285, and 8579142
The witnesses are 2, 3, 4, 5, and 6 for both the integers.
Example 4
Input: $from = 13_427_000, $to = 14_100_000, $count = 2
Output: 11
6 integers in the given range belong to 3 different shuffle pairs,
5 integers belong to 2 different ones.
Example 5
Input: $from = 1030, $to = 1130, $count = 1
Output: 2
There are 2 integers between 1020 and 1120 that belong to at least one shuffle pair:
1035, the other element is 3105 (witness k = 3)
1089, the other element is 9801 (witness k = 9)
Solution
Perl
Every number in the given range is split into digits, which are then sorted and rejoined, resulting in a normalized digit string.
Find the maximum factor for the number such that the product with the number does not exceed its length. This factor can be found as:
\[m = \bigg\lfloor\frac{10^{\lfloor\lg n\rfloor + 1} - 1}{n}\bigg\rfloor\]Generate the list of all valid multiples of the number and filter for those that yield the same normalized digit string.
Store the number with its pair partners if there are at least $count of them.
use strict;
use warnings;
use experimental 'signatures';
sub shuffle_pairs ($from, $to, $count) {
my @pairs;
for my $i ($from .. $to) {
my $si = join '', sort split //, $i;
my $m = int +(10**(int(log($i)/log(10)) + 1) - 1) / $i;
my @pals =
grep $si eq join('', sort split //, $_),
map $_ * $i,
2 .. $m;
push @pairs, [$i, \@pals] if @pals >= $count;
}
@pairs;
}
See the full solution to task 2.
J
Though I didn’t expect any useful results from trying to solve the task in J, I regarded it as an exercise. The steps to be performed are similar to the perl solution.
Starting with the maximum factor as in the Perl solution, which can be written as:
m =. <. n %~ 10^ >: <. 10^. n
This factor may be used to generate the list of all multiples of \(n\) (including itself):
l =. (>: i. m) * n
Split a number into digits and sort these:
s =. /:~ ": n
or, as a verb:
sd =. /:~&:":"0
Applied to the list and boxing the results:
p =. ;/ sd l
Finally count the matches of the first item (\(n\)’s sorted digits) with the remaining elements:
+/ ({. = }.) p
These steps are assembled into the definition of the verb ShufflePairs, that will calculate the number of shuffle pairs the given number belongs to (see below).
The intermediate steps need to be expressed as tacit verbs, though.
Next comes a dyadic verb producing all numbers in the range from to to inclusive:
FromTo =: {{x + i. 1 + y - x}}
The result of ShufflePairs compared to the requested count can either be used to count the pairs or - if used as a selector mask - to list the A’s in the given range.
ShufflePairs =: 3 : 0
sd =. /:~&:":"0
mult =. <.&:(] %~ 10&^&:(>:&:(<.&:(10&^.))))
mlist =. >:&:i.&:mult * ]
pairs =. ;/&:sd&:mlist
+/ ({. = }.) boxopen pairs y
)
FromTo =: {{x + i. 1 + y - x}}
assert. 0 = +/ 1&<:&:ShufflePairs"0 (1 FromTo 1000)
assert. 3 = +/ 1&<:&:ShufflePairs"0 (1500 FromTo 2500)
assert. 2 = +/ 5&<:&:ShufflePairs"0 (1000000 FromTo 1500000)
assert. 11 = +/ 2&<:&:ShufflePairs"0 (13427000 FromTo 14100000)
assert. 2 = +/ 1&<:&:ShufflePairs"0 (1030 FromTo 1130)
NB. echo (count&<:&:ShufflePairs"0 # ]) 13427000 FromTo 14100000
The very fact that this exercise lead to a working solution was a surprise. Moreover, it runs almost as fast as the perl implementation - which has undergone a number of optimization cycles.
$ time perl/ch-2.pl 13427000 14100000 2
11
real 0m4.920s
user 0m4.903s
sys 0m0.016s
$ time j/ch-2.ijs 13427000 14100000 2
11
real 0m5.018s
user 0m4.968s
sys 0m0.050s
See the full solution.