RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved various case and substring tests. (Note that this ends today.)

Task 1: Alternate Case

You are given a string containing an equal number of uppercase and lowercase English letters.

Write a script to the minimum number of adjacent character swaps needed to turn the given string into an alternate case string.

I'm handling this with a mapping and a breadth-first search. (In Perl.)

sub alternatecase($a) {

Start with the map. I don't care which specific letters are where, only which are upper and which lower case.

  my @uppers = map {($_ =~ /[A-Z]/)?1:0} split '',$a;

And I'll use my standard BFS scaffolding. One queue entry is [configuration of upper/lower case, count of swaps so far].

  my @queue;
  push @queue,[\@uppers, 0];

If there's any queue left, pull off an entry.

  while (scalar @queue > 0) {
    my ($up, $ct) = @{shift @queue};

Build up a list of possible swaps. If two adjacent letters are both upper or both lower case, we can either swap the first of the pair with the preceding letter or the second of the pair with the succeeding one. (This will produce duplicates. I might have used a set for this.)

    my @swaps;
    foreach my $i (0 .. scalar @{$up} - 2) {
      if ($up->[$i] == $up->[$i + 1]) {
        if ($i > 0) {
          push @swaps, $i - 1;
        }
        if ($i < scalar @{$up} - 2) {
          push @swaps, $i + 1;
        }
      }
    }

If there were no swaps (no adjacent matching letters), we have a solution, and because we're generating configurations in ascending cost order, it will be the one with lowest cost. Return it.

    if (scalar @swaps == 0) {
      return $ct;
    }

Otherwise, make copies of the input each with one swap implemented, and push them onto the queue with a higher cost.

    foreach my $sw (@swaps) {
      my @uq = @{$up};
      ($uq[$sw], $uq[$sw + 1]) = ($uq[$sw + 1], $uq[$sw]);
      push @queue, [\@uq, $ct + 1];
    }
  }

We probably won't get here, but just in case.

  0;
}

Task 2: Alternating Vowels Consonants

You are given three strings containing English alphabetic characters.

Find all the longest contiguous substrings common to all three strings that strictly alternate between vowels and consonants.

Longest common substring is of course a standard problem. But in this case I need all common substrings, because I want the longest ones that alternate vowel and consonant. (Possibly I could get more efficient, but I decided to separate functionality for possible later reuse.)

In Crystal: first support function, to extract common substrings.

def common_substring(a0)

Sort the input strings, by length ascending. (The longest common substring can be no longer than the shortest string.)

  a = a0.sort_by { |x| x.size }
  results = Array(String).new

Iterate through lengths, maximum down to 1

  (a[0].size - 1).downto(1) do |l|

Iterate through possible starting positions for a substring of that length.

    0.upto(a[0].size - l) do |offset|
      m = true

Extract that substring from the first string in the sorted list.

      sample = a[0][offset..offset + l - 1]

Check for its presence in each other string in the list. If it's not there, break out.

      iter = a.each
      iter.next
      while !(ax = iter.next).is_a?(Iterator::Stop)
        if ax.index(sample).nil?
          m = false
          break
        end
      end

If it was present in all, put it on the results list. if m results.push(sample) end end

If I wanted just the longest common substrings, I'd break out here if results contained anything rather than going round the loop again.

  end
  results
end

Second support function, determine whether a string is alternating vowels and consonants.

def is_avc(a)

Assume the string is alternating until shown otherwise.

  valid = true
  laststate = false

Iterate through the characters.

  a.chars.each_with_index do |c, i|

If it's a vowel, thisstate is true, otherwise it's false.

    thisstate = false
    case c
    when 'a', 'e', 'i', 'o', 'u'
      thisstate = true
    end

If we're not on the first character, and this and the previous character were both in the same state, the string isn't alternating.

    if i > 0 && thisstate == laststate
      valid = false
      break
    end

Otherwise update state and continue.

    laststate = thisstate
  end
  valid
end

Finally, the actual function to answer the question.

def alternatingvowelsconsonants(a)

Get a list of common substrings, and filter them for validity.

  c2 = common_substring(a).select{|x| is_avc(x)}

If there are any,

  if c2.size > 0

Find the length of the longest.

    l = c2[0].size

Filter the list again to strings that match that length, and return that.

    c2.select{|x| x.size == l}

Otherwise return an empty list.

  else
    [] of String
  end
end

Full code in all tagged languages is on codeberg.