I’ve been doing the Weekly
Challenges. The
latest
involved string manipulation and sorting. (Note that this ends today.)
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
.
Well, one could do it that way.
But the result is the difference between the length of all equal
strings and the length of all the common substrings.
Thus in Crystal:
def equalstrings(a)
Generate character lists, removing duplicate strings.
ca = a.map { |x| x.chars() }.to_set.to_a
The maximum common substring length is that of the shortest string in
the bunch.
mmlen = ca.map { |x| x.size }.min
si = 0
0.upto(mmlen - 1) do |i|
si = i
Check each string for equality with the first at this position.
Ultimately what we want from this in si
is the index of the last
character that's the same in all of strings.
1.upto(ca.size - 1) do |s|
if ca[0][i] != ca[s][i]
if i == 0
return -1
end
si -= 1
break
end
end
end
Return the length of all the strings, minus the length of the common
substrings.
a.map { |x| x.size }.sum - a.size * (si + 1)
end
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.
Some languages can compare arrays. Some can't. Raku gets a basic
non-recursive array comparator.
sub arraycomp(@a, @b) {
if (@a.elems != @b.elems) {
return False;
}
for @a.kv -> $i, $c {
if (@b[$i] ne $c) {
return False;
}
}
True;
}
Then the main function. Start by breaking up the input into character
arrays, but this time transposing rows and columns (so the first
string is split into characters at position 0 of list 0, list 1, etc.)
sub sortcolumn(@a) {
my @vv;
for @a.kv -> $i, $s {
for $s.comb.kv -> $j, $c {
if ($i == 0) {
@vv.push([]);
}
@vv[$j].push($c);
}
}
Then sort each array, and count the number of arrays which are changed
by sorting.
my $tot = 0;
for @vv -> @x {
my @y = @x.sort;
unless (arraycomp(@x, @y)) {
$tot++;
}
}
$tot;
}
Full code on
github.