TASK #1 › Common Base String
Submitted by: Mohammad S Anwar
You are given 2 strings, $A and $B.
Write a script to find out common base strings in $A and $B.
A substring of a string $S is called base string if repeated concatenation of the substring results in the string.
Example 1:
Input:
$A = "abcdabcd"
$B = "abcdabcdabcdabcd"
Output:
("abcd", "abcdabcd")
Example 2:
Input:
$A = "aaa"
$B = "aa"
Output:
("a")
My usual starting point is how we get the input?
we are given two string. so how about get two individual variables?
sub MAIN ( Str \A, Str \B ) {
say A, ",", B;
}
shell> raku ch-1.raku a aaa
a,aaa
BTW, if we don't want to (or won't) change the value of variable
we can use "\varname" syntax, and "varname" is now immutable.
so, "A", "B" are both immutable variables now.
Most principle part of this challenge is "how we get sub string of a string?" and no problem, we have substr method
sub MAIN ( Str \A, Str \B ) {
B.substr( 0 .. 1 ).say;
}
shell> raku ch-1.raku a aaa
aa
as you can see "0 .. 1" is a Range and they are index numbers in here.
.. so we have to say "'table for 1' to a waiter when you have 'a' company" ... no... please don't..
the base word must contains the substr from the beginning of each words otherwise it couldn't be a base word
before we go further, one more thing we should know about a handy operator "x" String repetition operator
shell> raku # interactive shell for raku 😍
To exit type 'exit' or '^D'
> "o" x 5
ooooo
It does not make sense to make a longer base string than any of given string so I added some restriction.
sub MAIN ( Str \A, Str \B ) {
my ( @answer, $shorter );
# shorter version of bellow
# $shorter = A.chars < B.chars ?? A !! B
if A.chars < B.chars {
$shorter = A;
}
else {
$shorter = B;
}
for 1..$shorter.chars -> $num-char {
my $mcb = $shorter.substr( ^$num-char ); # mcb: maybe common base string
# `-> another way of A.substr( 0..$num-char);
next unless A.chars %% $num-char and B.chars %% $num-char;
if ( A eq $mcb x ( A.chars div $num-char )
and
B eq $mcb x ( B.chars div $num-char ) ) {
@answer.push( $mcb );
}
}
@answer.say;
}
okay. this is "a" solution.
Raku has really excellent documentation.
please check the document if we are curious about something.
%% operator : https://docs.raku.org/routine/$PERCENT_SIGN$PERCENT_SIGN
and if we add more (really) convenient sugar onto the
comparison block, it would be changed ...
...
if ( A eq $mcb x ( A.chars div $num-char )
and
B eq $mcb x ( B.chars div $num-char ) ) {
@answer.push( $mcb );
...
becomes
...
if (A,B).map(
-> $str {
$mcb x ( $str.chars div $num-char ) } ).all == True {
@answer.push( $mcb );
...
good. looks trendy functional programming. :-]
".all" looks magic for me. we should try.
how about any ?
shell> raku
To exit type 'exit' or '^D'
> any( 1 == 0, "abc" eq "def", ("I love Raku".substr(0,5) eq ("I love Perl".substr(0,5)))) == True
any(False, False, True)
> (any( 1 == 0, "abc" eq "def", ("I love Raku".substr(0,5) eq ("I love Perl".substr(0,5)))) == True).so
True
but one more thing ....
there is a gcd in Raku
e.g. greatest common divisor
A, B string must have the length of multiple of common divisor.
shell> raku
To exit type 'exit' or '^D'
> "abc".chars gcd "abcabc".chars
3
so I could make another solution by using new friend "gcd"
sub MAIN ( Str \A, Str \B ) {
my @words = A, B;
my @answer;
my $gcd = A.chars gcd B.chars;
for 1..$gcd -> $maybe-cd {
if $gcd %% $maybe-cd {
note "$maybe-cd is common divisor";
my $mcb = A.substr(^$maybe-cd);
if @words.map(
{ $mcb x ($_.chars div $maybe-cd)
eq
$_ } ).all == True {
note "found a base substring: $mcb";
@answer.push( $mcb );
}
}
}
note "therefore:";
@answer.join(", ").put;
}
shell> raku ch-1.blog.raku "abcdabcd" "abcdabcdabcdabcd"
1 is common divisor
2 is common divisor
4 is common divisor
found a base substring: abcd
8 is common divisor
found a base substring: abcdabcd
therefore:
abcd, abcdabcd
and... one more solution which is based on the gcd and indices
I like this one most.
sub MAIN(*@a) {
say (1..([gcd] @a>>.chars)).
map(->\k{my \w = @a[0].substr(^k);
next if any @a.map({.indices(w).elems!= .chars/k});
w } )
}
More explain needed due to more concept goes through the code, but I'm still learning raku so... it is something like ...
> ("what I told" ~~ True, "today" ne "tommorrow", "I don't know something but it's working so I used.".so eq True).all.so
False
so, please wait for another episode :-)
Thank you ~~ !!!
Top comments (0)