Weekly Challenge 350
Each week Mohammad S. Anwar sends out The Weekly Challenge, a chance for all of us to come up with solutions to two weekly tasks. My
solutions are written in Python first, and then converted to Perl. It's a great way for us all to practice some coding.
Task 1: Good Substrings
Task
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.
My solution
This is relatively straight forward, so doesn't require much explanation. I have a variable called i that starts at zero and ends with three less than the length of the string. For each iteration, I extract the the three letters starting at the specified position. If the three letters are unique, I add one to the count variable.
def good_substr(input_string: str) -> int:
count = 0
for i in range(len(input_string) - 2):
substr = input_string[i:i + 3]
if len(set(substr)) == 3:
count += 1
return count
In Python, I convert the three characters to a set. If the length of the set is 3, I know all characters are unique (sets can only store unique values). In Perl, I use a %chars hash. If a letter is already seen, it will return 0.
sub is_unique ($substr) {
my %chars;
foreach my $char (split //, $substr) {
return 0 if exists $chars{$char};
$chars{$char} = 1;
}
return 1;
}
Examples
$ ./ch-1.py abcaefg
5
$ ./ch-1.py xyzzabc
3
$ ./ch-1.py aababc
1
$ ./ch-1.py qwerty
4
$ ./ch-1.py zzzaaa
0
Task 2: Shuffle Pairs
Task
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 B = A × k where 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.
My solution
This is an interesting challenge as the solution requires some thinking. Additionally there was an error with the original page, so I raised a pull request to fix it.
I start by setting the shuffle_pairs variable to zero. I have a loop with the variable value that starts at from and ends with to (inclusive). As from is a reserved word in Python, I use the variables start and end.
For each iteration of value, I do the following.
- Set the variable
this_countto zero. This will store the number of shuffle pairs for this value. - Set the variable
multiplierto 2. - Set a variable called
candidateto the product ofvalueandmultiplier. - If this is a shuffle_pair, increment the
this_countvalue. - If the
candidateis equal to or greater then 10length of value, end the loop. As this number has more digits than the original, no shuffle pair can be found for this candidate. - Once the previous step is reached, increment the
shuffle_pairvalue ifthis_count >= count.
def shuffle_pairs(start: int, stop: int, count: int) -> int:
shuffle_pairs = 0
for value in range(start, stop + 1):
this_count = 0
multiplier = 2
while True:
candidate = value * multiplier
if candidate >= 10 ** len(str(value)):
break
if is_shuffle_pair(value, candidate):
this_count += 1
multiplier += 1
if this_count >= count:
shuffle_pairs += 1
return shuffle_pairs
The Perl solution follows the same logic.
Examples
$ ./ch-2.py 1 1000 1
0
$ ./ch-2.py 1500 2500 1
3
$ ./ch-2.py 1000000 1500000 5
2
$ ./ch-2.py 13427000 14100000 2
11
$ ./ch-2.py 1030 1130 1
2