This is my response to The Weekly Challenge #350.
Input: $str = "abcaefg"
Output: 5
Good substrings of length 3: abc, bca, cae, aef and efg
Input: $str = "xyzzabc"
Output: 3
Good substrings of length 3: "xyz", "zab" and "abc"
Input: $str = "aababc"
Output: 1
Good substrings of length 3: "abc"
Input: $str = "qwerty"
Output: 4
Good substrings of length 3: "qwe", "wer", "ert" and "rty"
Input: $str = "zzzaaa"
Output: 0
#! /usr/bin/env raku
unit sub MAIN ($str where $str.chars > 0, :v(:$verbose)); # [1]
my $good = 0; # [2]
for 0 .. $str.chars - 3 -> $i # [3]
{
my $substring = $str.substr($i, 3); # [4]
my $is-good = $substring.comb.Bag.elems == 3; # [5]
$good++ if $is-good; # [6]
say ": Candidate: '$substring' { $is-good ?? "is good ($good)" !! "" }"
if $verbose;
}
say $good; # [7]
[1] A string with at least one character.
[2] The number of good substrings we encounter.
[3] Iterate over the starting positions (index) of all the substrings with length 3.
[4] Get the substring.
[5] Turn the substring into individual characters and that
array into a Bag, a hash-like structure that counts the
frequencies. The string is good if we have three distinct characters
(keys in the hash).
See docs.raku.org/routine/Bag for more information about Bag.
[6] Count it, if it is good.
[7] Print the result.
Running it:
$ ./good-substrings qabcaefg
5
$ ./good-substrings xyzzabc
3
$ ./good-substrings aababc
1
$ ./good-substrings qwerty
4
$ ./good-substrings zzzaaa
0
Looking good.
With verbose mode:
$ ./good-substrings -v abcaefg
: Candidate: 'abc' is good (1)
: Candidate: 'bca' is good (2)
: Candidate: 'cae' is good (3)
: Candidate: 'aef' is good (4)
: Candidate: 'efg' is good (5)
5
$ ./good-substrings -v xyzzabc
: Candidate: 'xyz' is good (1)
: Candidate: 'yzz'
: Candidate: 'zza'
: Candidate: 'zab' is good (2)
: Candidate: 'abc' is good (3)
3
$ ./good-substrings -v aababc
: Candidate: 'aab'
: Candidate: 'aba'
: Candidate: 'bab'
: Candidate: 'abc' is good (1)
1
$ ./good-substrings -v qwerty
: Candidate: 'qwe' is good (1)
: Candidate: 'wer' is good (2)
: Candidate: 'ert' is good (3)
: Candidate: 'rty' is good (4)
4
$ ./good-substrings -v zzzaaa
: Candidate: 'zzz'
: Candidate: 'zza'
: Candidate: 'zaa'
: Candidate: 'aaa'
0
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 B = A * k where k is called the witness of the pair.
1359 * 7 = 9513.
123876 * 3 = 371628123876 * 7 = 867132$from, $to, and $count returns the
number of integers $i in the range $from <= $i <= $to$count different shuffle pairs.
Input: $from = 1, $to = 1000, $count = 1
Output: 0
There are no shuffle pairs with elements less than 1000.
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)
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.
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.
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)
#! /usr/bin/env raku
unit sub MAIN (UInt :f(:$from), # [1]
UInt :t(:$to) where $to >= $from, # [1a]
UInt :c(:$count), # [1b]
:v(:$verbose));
my $good = 0; # [2]
for $from .. $to -> $current # [3]
{
my $canonical = $current.comb.sort.join; # [4]
my $length = $current.chars; # [5]
my $shuffle = 0; # [6]
my @verbose; # [7]
for 2 .. Inf -> $multiplier # [8]
{
my $new = $current * $multiplier; # [9]
last if $new.chars > $length; # [10]
my $canon = $new.comb.sort.join; # [11]
if $canonical eq $canon # [12]
{
$shuffle++; # [13]
@verbose.push: "$new (x $multiplier)"; # [14]
if $shuffle == $count # [15]
{
say ": $current -> { @verbose.join(", ") } (count $shuffle)"
if $verbose;
$good++; # [16]
last; # [17]
}
}
}
}
say $good; # [18]
[1] Named arguments for the three integer arguments. I use the UInt
(Unsigned Int) type, to prevent negative values.
See docs.raku.org/type/UInt for more information about the UInt type.
[2] The result will end up here.
[3] Iterate over the values in the from .. to range.
[4] Get the canonical version of the current value, by sorting the digits and gluing them back together.
[5] The length of the current value, to be used in [10].
[6] The number of found shuffled variants.
[7] Use by verbose mode, to collect the shuffled values.
[8] Iterate over all posible multipliers.
[9] Get the multiplum.
[10] Exit the loop if we get too many digits.
[11] Get the canonical form of this candidate.
[12] Are the two canoinical form equal? Note string comparison, so that anyleadinbg zeros are taken into account. Not that it actually matteres here...
[13] Count the shuffled value.
[14] Set up for verbose mode.
[15] Have we reached the target? If so, be verbose if so requested.
[16] Count the value.
[17] Finish the loop, as we do not care for more shuffled pairs than the given limit.
[18] Print the result.
Running it:
$ ./shuffle-pairs -f=1 -t=1000 -c=1
0
$ ./shuffle-pairs -f=1500 -t=2500 -c=1
3
$ ./shuffle-pairs -f=1000000 -t=1500000 -c=5
2
$ ./shuffle-pairs -f=13427000 -t=14100000 -c=2
11
$ ./shuffle-pairs -f=1030 -t=1130 -c=1
Looking good.
With verbose mode:
$ ./shuffle-pairs -f=1 -t=1000 -c=1 -v
0
$ ./shuffle-pairs -f=1500 -t=2500 -c=1 -v
: 1782 -> 7128 (x 4) (count 1)
: 2178 -> 8712 (x 4) (count 1)
: 2475 -> 7425 (x 3) (count 1)
3
$ ./shuffle-pairs -f=1000000 -t=1500000 -c=5 -v
: 1428570 -> 2857140 (x 2), 4285710 (x 3), 5714280 (x 4), 7142850 (x 5), \
8571420 (x 6) (count 5)
: 1429857 -> 2859714 (x 2), 4289571 (x 3), 5719428 (x 4), 7149285 (x 5), \
8579142 (x 6) (count 5)
2
$ ./shuffle-pairs -f=13427000 -t=14100000 -c=2 -v
: 13428567 -> 26857134 (x 2), 53714268 (x 4) (count 2)
: 13428657 -> 26857314 (x 2), 53714628 (x 4) (count 2)
: 13567842 -> 27135684 (x 2), 54271368 (x 4) (count 2)
: 13568427 -> 27136854 (x 2), 67842135 (x 5) (count 2)
: 13874526 -> 41623578 (x 3), 83247156 (x 6) (count 2)
: 13875246 -> 41625738 (x 3), 83251476 (x 6) (count 2)
: 14002857 -> 28005714 (x 2), 42008571 (x 3) (count 2)
: 14025897 -> 28051794 (x 2), 70129485 (x 5) (count 2)
: 14028570 -> 28057140 (x 2), 42085710 (x 3) (count 2)
: 14028597 -> 28057194 (x 2), 42085791 (x 3) (count 2)
: 14029857 -> 28059714 (x 2), 42089571 (x 3) (count 2)
11
$ ./shuffle-pairs -f=1030 -t=1130 -c=1 -v
: 1035 -> 3105 (x 3) (count 1)
: 1089 -> 9801 (x 9) (count 1)
2
Som more, just for fun:
$ ./shuffle-pairs -f=13427000 -t=14100000 -c=3 -v
: 13428567 -> 26857134 (x 2), 53714268 (x 4), 67142835 (x 5) (count 3)
: 13428657 -> 26857314 (x 2), 53714628 (x 4), 67143285 (x 5) (count 3)
: 14002857 -> 28005714 (x 2), 42008571 (x 3), 70014285 (x 5) (count 3)
: 14028570 -> 28057140 (x 2), 42085710 (x 3), 70142850 (x 5) (count 3)
: 14028597 -> 28057194 (x 2), 42085791 (x 3), 70142985 (x 5) (count 3)
: 14029857 -> 28059714 (x 2), 42089571 (x 3), 70149285 (x 5) (count 3)
6
$ ./shuffle-pairs -f=13427000 -t=14100000 -c=4 -v
0
And that's it.