RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved base conversion and string analysis. (Note that this ends today.)

Task 1: Base N

You are given a number and a base integer.

Write a script to convert the given number in the given base integer.

In Perl:

sub basen($a, $base) {

The routine I'll be using to get base-N digits terminates when it sees zero, so I'll knock that out with a special case before doing anything else.

  if ($a == 0) {
    return "0";
  }

The digits to be used for higher bases are specified in the examples.

  my @digits = ('0' .. '9', 'A' .. 'Z', 'a' .. 'z', '+', '/');

As with the pattern I've used before, I'll use modulus and integer division to build up a list of digits least significant first.

  my @fields;
  my $aa = $a;
  while ($aa > 0) {
    push @fields, $aa % $base;
    $aa = int($aa / $base);
  }

Now I'll unwind that stack and append the digit characters to the output string.

  my $output = '';
  while (scalar @fields > 0) {
    $output .= @digits[pop @fields];
  }
  $output;
}

Task 2: Special Binary Substrings

You are given a binary string.

Write a script to return all non-empty substrings (distinct) that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.

[sic]

I end up simply testing each even-sized span of characters. In Crystal:

def specialbinarysubstrings(a)
  out = Array(String).new

Split the input string into individual characters.

  ac = a.chars

Iterate the start point across the string (all but the last character).

  0.upto(ac.size - 2) do |i|

Iterate the end point from the next character to the end of the string, in steps of 2. (Because an odd-length string can't have equal numbers of the two digits.)

    (i+1).step(to: ac.size - 1, by: 2) do |j|

Set up my measurement variables.

      lastchar = 'x'
      switches = 0
      balance = 0
      outstr = ""

Iterate over the characters in this span.

      i.upto(j) do |ct|

If the character isn't the same as the last one, increment switches.

        if ac[ct] != lastchar
          switches += 1
          lastchar = ac[ct]
        end

Increment balance for a 1, decrement for a 0.

        if ac[ct] == '0'
          balance -= 1
        else
          balance += 1
        end

Append the character in case we use this string.

        outstr += ac[ct]
      end

If there were equal ones and zeroes (balance = 0) and the character changed only twice (at the start of the string and at the permitted midpoint) add this string to the output list.

      if balance == 0 && switches == 2
        out.push(outstr)
      end
    end
  end
  out
end

Full code on codeberg.