Weekly Challenge: Sorted equally – DEV Community

Weekly Challenge 314

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

Equal Strings

Task

You are given three strings.

You are allowed to remove the rightmost character of a string to make all equals.

Write a script to return the number of operations to make it equal otherwise -1.

My solution

With these challenges, it’s sometimes more efficient to do things differently to achieve the same result, and that is the case with this task.

While this tasks says three strings are provided, my code will take any number of strings.

For this task, I determine the longest string where all the characters are the same. I start by defining the variables shortest_length and combined_length. As the names suggest, the first value is the length of the shortest string. The combined_length variable stores the length of all strings combined.

def equal_strings(strs: list) -> int:
    shortest_length = min(len(s) for s in strs)
    combined_length = sum(len(s) for s in strs)

I have a variable l which starts with the length of the shortest string and goes back to one. For each length I check if all the string of the specified length are the same.

If they are, I can work out the characters which were deleted (which is what we are looking for) by subtracted the remaining characters (the number of items times the length) from the combined_length value.

    for l in range(shortest_length, 0, -1):
        if all_same(s[0:l] for s in strs):
            return combined_length - len(strs) * l

The all_same functions uses the generator in the middle line and returns a boolean if they are all the same. In Python this is a one liner. Turning the generator into a set will result in one value as sets only hold unique values.

def all_same(strs: Generator[str]) -> bool:
    return len(set(strs)) == 1

The Perl version of this sub is also a one liner, but uses a different approach. It checks if all strings are the same as the first string.

sub all_same(@substrs) {
    return all { $_ eq $substrs[0] } @substrs;
}

Finally, I return -1 if the iterator is exhausted and the first character is not the same.

    return -1

Examples

$ ./ch-1.py abc abb ab
2

$ ./ch-1.py ayz cyz xyz
-1

$ ./ch-1.py yza yzb yzc
3

Task 2: Sort Column

You are given a list of strings of same length.

Write a script to make each column sorted lexicographically by deleting any non sorted columns.

Return the total columns deleted.

My solution

As we only need the number of columns deleted, there no actual deletion involved in this solution.

I start this task by checking that all strings are the same length. If they are not, I raise an exception.

I then have an iterator called idx that loops from 0 to one less than the length of the strings. I create a list (array in Perl) called characters that has the characters from each string at the position idx. If the sorted list is different than the original list, I add one to the unsorted_count variable.

def sort_column(strs: list) -> int:
    if any(len(s) != len(strs[0]) for s in strs):
        raise ValueError('Strings are not of the same length')

    unsorted_count = 0

    for idx in range(len(strs[0])):
        characters = [s[idx] for s in strs]
        if characters != sorted(characters):
            unsorted_count += 1

    return unsorted_count

As Perl does not have an easy way to compared two arrays for eqaulity, I took a slightly different approach. For the Perl solution, I have an inner loop to check if the letter in the characters array is less than the previous one. If it is, it means the letters are not in lexicographic order, and I can add to the unsorted_count value and exit the inner loop.

  O: for my $idx ( 0 .. length( $strs[0] ) - 1 ) {
        # Check that the characters at position idx are sorted
        my @characters = map { substr( $_, $idx, 1 ) } @strs;

        foreach my $sub_idx ( 1 .. $#characters ) {
            if ( $characters[ $sub_idx - 1 ] gt $characters[$sub_idx] ) {
                # If the character at this position is less than the last one
                #  it is not sorted
                $unsorted_count++;
                next O;
            }
        }
    }

Examples

$ ./ch-2.py swpc tyad azbe
2

$ ./ch-2.py cba daf ghi
1

$ ./ch-2.py a b c
0