RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved various string parsings. (Note that this ends today.)

I've had a busy few days, so I only answered these in Rust, Perl and PostScript.

Task 1: Balance String

You are given a string made up of lowercase English letters and digits only.

Write a script to format the give string where no letter is followed by another letter and no digit is followed by another digit. If there are multiple valid rearrangements, always return the lexicographically smallest one. Return empty string if it is impossible to format the string.

There are several distinct steps, but each of them is relatively straightforward. (Perl.)

sub balancestring($a) {

Step one: break down the string into a list of letters and a list of digits.

  my @letters;
  my @digits;
  foreach my $c (split '', $a) {
    if ($c =~ /[A-Z]/i) {
      push @letters, $c,
    } elsif ($c =~ /[0-9]/) {
      push @digits, $c;
    }
  }

If one of them is two or more longer than the other, there's no valid solution, so bail out now.

  if (scalar @digits > scalar @letters + 1 ||
      scalar @letters > scalar @digits + 1) {
    return "";
  }

Step two: sort each list, so that when they're output in order we'll get the lexicographically-first possibility.

  @digits = sort @digits;
  @letters = sort @letters;

Step three: assign "digits" and "letters" to "a" and "b" lists. If "letters" is longer, make that the "a" list instead. (At the same length, digits will be lex-first before letters.)

  my @a = @digits;
  my @b = @letters;
  if (scalar @letters == scalar @digits + 1) {
    @a = @letters;
    @b = @digits;
  }

Step four: assemble the output list from the first characters of "a" and "b", second characters, etc.

  my @out;
  foreach my $i (0 .. scalar @b - 1) {
    push @out, $a[$i];
    push @out, $b[$i];
  }

If the lists weren't the same length, push on the final character of "a".

  if (scalar @a > scalar @b) {
    push @out,$a[scalar @a - 1];
  }

Finally, return the output list as a string.

  join('', @out);
}

Task 2: Max Score

You are given a string, $str, containing 0 and 1 only.

Write a script to return the max score after splitting the string into two non-empty substrings. The score after splitting a string is the number of zeros in the left substring plus the number of ones in the right substring.

One could calculate this from both ends, but I found an approach that uses a single pass. Rust:

fn maxscore(a: &str) -> usize {

Initialise counters: how many zeroes are to the left of the current split point, and how many ones are to the right of it? We don't actually count the ones; there might be as many as (length of string). This number will always be (the actual number of ones left) plus (a fixed offset), and since that offset will be consistent, that's fine for our purposes.

    let mut zeroestoleft = 0;
    let mut onestoright = a.len();
    let mut maxscore = 0;

Look through the characters.

    for (i, c) in a.chars().enumerate() {
        match c {

If it's a 0, increment the number of zeroes to the left.

            '0' => zeroestoleft += 1,

If it's a 1, decrement the number of ones to the right.

            '1' => onestoright -= 1,
            _ => ()
        };

If we haven't got all the way to the end,

        if i + 1 < a.len() {

See if the score here is higher than before, and if so store it.

            maxscore = std::cmp::max(maxscore, zeroestoleft + onestoright);
        }
    }

The true count of ones to the right of the split, at the end of the string, is zero. So decrease the calculated maximum score by that, and that's the answer.

    maxscore - onestoright
}

Full code on github.