RogerBW's Blog

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

Again it's been a busy week so I didn't do the full set of languages.

Task 1: Longest Parenthesis

You are given a string containing only ( and ).

Write a script to find the length of the longest valid parenthesis.

PostScript will simply interpret this, if you aren't careful about escaping the input. But my approach was to go character by character in each possible sub-sequence, with a depth counter that pops up or down by one for left and right parentheses. If it ever goes below zero, the sequence is invalid; if it's not at zero at the end, the sequence is invalid. I'm sure this could be done more efficiently; for example by taking the longest sub-sequences first and exiting at once when a valid one is found.

Perl:

sub longestparenthesis($aa) {

Set up a character array, and a maximum length counter.

  my @a = split '', $aa;
  my $ml = 0;

Look at each possible subsequence. (If I iterated R in reverse I could do this more efficiently.)

  foreach my $l (0 .. $#a) {
    foreach my $r ($l .. $#a) {

Here we're looking at the subsequence from L to R inclusive.

      my $depth = 0;
      my $valid = 1;

Iterate over the characters, tracking depth, dropping out if we go below zero.

      foreach my $i ($l .. $r) {
        if ($a[$i] eq '(') {
          $depth++;
        } else {
          $depth--;
          if ($depth < 0) {
            $valid = 0;
            last;
          }
        }
      }

If we didn't get back to zero depth, it's invalid.

      if ($depth != 0) {
        $valid = 0;
      }

Otherwise track the length.

      if ($valid) {
        $ml = max($ml, $r - $l + 1);
      }
    }
  }
  $ml;
}

Task 2: Magic Expression

You are given a string containing only digits and a target integer.

Write a script to insert binary operators +, - and * between the digits in the given string that evaluates to target integer.

For some languages that don't have a casual expression parser and evaluator built in (e.g. Rust), this is much harder, and I can't be bothered to write one. This is therefore one of the very few cases in which Ruby code won't work in Crystal with only minor modifications.

I find that these days I itch slightly when I commit an eval. That's probably a good thing.

I've done combinatorial products before but here I did it the crude way.

JavaScript:

function magicexpression(number, target) {
    const n = number.split('');
    const l = number.length - 1;

counter holds the operator indices.

    let counter = new Array(l).fill(0);
    let out = [];
    const rx = new RegExp("(^|[^0-9])0[0-9]");
    LOOP:
    while (true) {

Increment the counter. (Skip 0-0-0, probably shouldn't, didn't notice the error until I'd implemented it in other languages too.)

        let i = 0;
        counter[i]++;
        while (counter[i] == 4) {
            counter[i] = 0;
            i++;
            if (i < l) {
                counter[i]++;
            } else {
                break LOOP;
            }
        }

Assemble the expression string based on counter values.

        let ex = "";
        for (let i = 0; i < l; i++) {
            ex += n[i];
            ex += ["", '+', '-', '*'][counter[i]];
        }
        ex += n[l];

If it has a leading zero, bail out

        if (ex.search(rx) != -1) {
            continue LOOP;
        }

Otherwise evaluate it and compare to the answer.

        if (eval(ex) == target) {
            out.push(ex);
        }
    }

Sort the results.

    out.sort();
    return out;
}

Full code on github.