Weekly Challenge: Base substrings

Weekly Challenge 384

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. Unless otherwise stated, Copilot (and other AI tools) have NOT been used to generate the solution. It's a great way for us all to practice some coding.

Challenge, My solutions

Task 1: Base N

Task

You are given a number and a base integer.

Write a script to convert the given number in the given base integer.

My solution

For this challenge, I start by checking n is not a negative integer and base is between 2 and 64.

def base_n(num: int, base: int) -> str:
    if not 1 <= base <= 64:
        raise ValueError(f"Invalid base value: {base}")
    if num < 0:
        raise ValueError(f"Number {num} must be non-negative")

I then separate n into the digits in the specified base. This is the same code that was used in Challenge 379.

    digits = []
    while True:
        i, j = divmod(num, base)
        digits.insert(0, j)

        if i == 0:
            break

        num = i

The last step is to define the strings that represent each character, and return that.

    alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/"
    return "".join(alphabet[i] for i in digits)

One thing to note is that Base 64 (as defined in RFC 4648) uses upper case letters (0-25), lower case letters (26-51), numbers (52-61) and two extra characters (62 and 63). It's clear from the fifth example that in this case, the numbers come before the letters.

Examples

$ ./ch-1.py 42 2
101010

$ ./ch-1.py 15642094 16
EEADEE

$ ./ch-1.py 493 8
755

$ ./ch-1.py 2228519 36
1BRJB

$ ./ch-1.py 123456789 64
7MyqL

Task 2: Special Binary Substrings

Task

You are given a binary string.

Write a script to return all non-empty substrings (distinct) that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

My solution

For this task, I start by checking that input_string contains only ones and zeros.

def special_binary_substrings(input_string: str) -> list[str]:
    if not re.search(r"^[01]+$", input_string):
        raise ValueError("Invalid input provided")

I then generate a set (hash in Perl) of all valid substrings.

    half_length = int(len(input_string) / 2)
    valid_substring = {
        substring
        for l in range(1, half_length + 1)
        for substring in generate_substring(l)
    }

The generate_substring function will generate the substrings of l zeros and l ones and visa versa.

def generate_substring(l: int) -> tuple:
    return ("0" * l + "1" * l, "1" * l + "0" * l)

The last step is to find all the substrings that are in the valid_substring set. For this, I use a double loop. The outer loop is called start from 0 to two less than the length of the string. The inner loop is end from one more than start to the length of the string, two at a time (since all solutions must have an even number of digits).

    results = []
    for start in range(len(input_string) - 1):
        for end in range(start + 1, len(input_string), 2):
            substring = input_string[start : end + 1]
            if substring in valid_substring:
                results.append(substring)

    return results

For the Perl solution, I use $length instead of end, as this is the parameter that the substring function uses.

sub main ($input_string) {
    if ( $input_string !~ /^[01]+$/ ) {
        die "Invalid input provided\n";
    }

    my %valid_substring = ();
    my $half_length     = int( length($input_string) / 2 );
    foreach my $l ( 1 .. $half_length ) {
        $valid_substring{ "0" x $l . "1" x $l } = 1;
        $valid_substring{ "1" x $l . "0" x $l } = 1;
    }

    my @results = ();
    my $l       = length($input_string);
    foreach my $start ( 0 .. $l - 2 ) {
        for ( my $length = 2 ; $length <= $l - $start ; $length += 2 ) {
            my $substring = substr( $input_string, $start, $length );
            if ( exists $valid_substring{$substring} ) {
                push @results, $substring;
            }
        }
    }

    say "(" . join( ", ", map { qq{"$_"} } @results ) . ")";
}

Examples

$ ./ch-2.py 0101
("01", "10", "01")

$ ./ch-2.py 000111
("000111", "0011", "01")

$ ./ch-2.py 000011
("0011", "01")

$ ./ch-2.py 10011100
("10", "0011", "01", "1100", "10")

$ ./ch-2.py 00000
()