Weekly Challenge 314 Task 1
Equal Strings
This post is a mixture of Jupyter Notebook[1] cells where I workout a solution for the Weekly Challenge Task 1[2], some commentary with my thought process and the final working function in Python, which is then hopefully translated to Perl.
Task 1: Equal Strings
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.
Rather than removing the rightmost character I’ll work from left to right comparing the characters and when they differ I have the length of each string which will remain. Then taking the length of each string from the remaining length I can find the number of operations to make the strings equal.
Playing with the example input:
from itertools import zip_longest
strings = ("abc", "abb", "ab")
list(zip_longest(*strings, fillvalue=None))
[('a', 'a', 'a'), ('b', 'b', 'b'), ('c', 'b', None)]
From this example it looks like 2 characters need to be removed from the right of the strings to make all equal. All characters in the first 2 positions are the same and there are 2 characters in the third position.
To find the number of characters the same from left to right in all strings I could do the following:
count_same = 0
for z in zip(*strings):
if not len(set(z)) == 1:
break
count_same += 1
count_same
2
this can be reduced to a generator expression by using takewhile and a lambda expression:
from itertools import takewhile
sum(1 for _ in takewhile(lambda z: len(set(z)) == 1, zip(*strings)))
2
To calculate the number of operations needed across all strings:
operations = sum(len(s) - count_same for s in strings)
operations
2
Putting all of this together the final function looks like this:
#!/usr/bin/env python3
from itertools import takewhile
def equal_strings(*strings):
""" Given three strings. You are allowed to remove the rightmost character
of a string to make all equals, return the number of operations to make it
equal otherwise -1.
>>> equal_strings("abc", "abb", "ab")
2
>>> equal_strings("ayz", "cyz", "xyz")
-1
>>> equal_strings("yza", "yzb", "yzc")
3
"""
count = sum(1 for _ in takewhile(lambda z: len(set(z)) == 1, zip(*strings)))
return sum(len(s) - count for s in strings) if count else -1
if __name__ == "__main__":
import doctest
doctest.testmod(verbose=True)
Trying:
equal_strings("abc", "abb", "ab")
Expecting:
2
ok
Trying:
equal_strings("ayz", "cyz", "xyz")
Expecting:
-1
ok
Trying:
equal_strings("yza", "yzb", "yzc")
Expecting:
3
ok
1 items had no tests:
__main__
1 items passed all tests:
3 tests in __main__.equal_strings
3 tests in 2 items.
3 passed and 0 failed.
Test passed.
Perl Solution
My Perl solution has a lot more lines of code.
#!/usr/bin/env perl
use v5.35;
use Test2::Bundle::More;
use List::Util qw/zip_shortest/;
sub equalStrings {
my @strings = @_;
my $count = 0;
my @strings_split = map { [split //, $_] } @strings;
for my $z (zip_shortest(@strings_split)){
my %chars = map { $_ => 1 } @$z;
if (keys %chars == 1){
$count++;
} else {
last;
}
}
my $operations = 0;
if ($count != 0){
for my $string (@strings){
$operations += (length($string) - $count);
}
}
$operations == 0 ? return -1 : return $operations;
}
is(equalStrings("abc", "abb", "ab"), 2, "Example 1");
is(equalStrings("ayz", "cyz", "xyz"), -1, "Example 2");
is(equalStrings("yza", "yzb", "yzc"), 3, "Example 3");
done_testing();
ok 1 - Example 1
ok 2 - Example 2
ok 3 - Example 3
1..3