Weekly Challenge: Good shuffling

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.

Challenge, My solutions

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.

1. Set the variable this_count to zero. This will store the number of shuffle pairs for this value.
2. Set the variable multiplier to 2.
3. Set a variable called candidate to the product of value and multiplier.
4. If this is a shuffle_pair, increment the this_count value.
5. If the candidate is equal to or greater then 10^{length of value}, end the loop. As this number has more digits than the original, no shuffle pair can be found for this candidate.
6. Once the previous step is reached, increment the shuffle_pair value if this_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