RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved word and character counting. (Note that this ends today.)

Another minimal participation since I was away for much of the relevant week (or catching up), so I've just done this in the languages I enjoy most.

Task 1: Uncommon Words

You are given two sentences.

Write a script to return list of all uncommon words, order is not important.

Looking at the examples, it seemed that a word needed to appear only once across both strings to be listed in the output. So the easy approach was to treat them together. To preserve the examples' order, I used a two-pass approach with a counter.

In Perl:

sub uncommonwords($a, $b) {

Initialise the counter.

  my %c;

Set the counts for each word.

  foreach my $s ($a, $b) {
    foreach my $w (split ' ', $s) {
      $c{$w}++;
    }
  }

Run through the words again, appending to the output each which has a count of exactly 1.

  my @out;
  foreach my $s ($a, $b) {
    foreach my $w (split ' ', $s) {
      if ($c{$w} == 1) {
        push @out, $w;
      }
    }
  }
  \@out;
}

This gets rather more compact in Rust with the Counter class.

fn uncommonwords(a: &str, b: &str) -> Vec<String> {
    let mut c: Counter<&str> = Counter::new();
    for s in [a, b] {
        c += s.split_whitespace();
    }
    let mut out = Vec::new();
    for s in [a, b] {
        for w in s.split_whitespace() {
            if c[&w] == 1 {
                out.push(w.to_string());
            }
        }
    }
    out
}

and in PostScript I end up making a copy of the concatenated word list in wl to avoid generating it twice:

/uncommonwords {
    0 dict begin
    /b exch def
    /a exch def
    /wl [
        [ a b ] {
            ( ) strsplit
            aload pop
        } forall
    ] def
    /c wl tocounter def
    [
        wl {

Each word in the list is on the stack here; if it doesn't have a value of 1 in the counter, we throw it away, otherwise leave it in the array that's being constructed.

            dup
            c exch get 1 ne {
                pop
            } if
        } forall
    ]
    end
} bind def

(Yes, this is more verbose than it appears, as "tocounter" and "strsplit" are library functions I've had to write.)

Task 2: Outermost Parentheses

You are given a valid parentheses string.

Write a script to return the string after removing the outermost parentheses of every primitive string in the primitive decomposition of the given string.

In other words, for every sequence delimited by an outermost pair of brackets, append the sequence without that outermost pair to the answer.

Looking at the examples gave me a state machine model. In Rust:

fn outermostparentheses(a: &str) -> String {

Initialise the depth counter and output list.

    let mut d = 0;
    let mut out = String::new();

Iterate over characters.

    for c in a.chars() {
        match c {

If it's an open-paren, increment the depth counter. If current depth is more than 1 (i.e. this paren wasn't at the outermost layer), add the character to the output.

            '(' => {
                d += 1;
                if d > 1 {
                    out.push(c);
                }
            },

If it's an open-paren, decrement the depth counter. If current depth is now more than 0, add the character to the output.

            ')' => {
                d -= 1;
                if d > 0 {
                    out.push(c);
                }
            },
            _ => panic!("Bad char"),
        }
    }
    out
}

A validating version would add checks to ensure that depth never goes below 0, and is exactly 0 at the end of the input.

Full code in all tagged languages is on codeberg.