RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved analysing strings and picking over lists. (Note that this ends today.)

Task 1: Lexicographic Order

You are given an array of strings. Write a script to delete element which is not lexicographically sorted (forwards or backwards) and return the count of deletions.

As usual I code to the test case, so I don't bother with the actual deletion. If that were required, the logic wouldn't change much anyway.

Raku:

sub lexicographic(@a) {
    my $t = 0;

For each string…

    for @a -> $st {

Take the characters and sort them.

        my @q = $st.comb.sort;

If that's the same as the string, we have a forward sort, so continue.

        if (join('', @q) eq $st) {
            next;
        }

Otherwise, reverse and test again.

        @q = reverse @q;
        if (join('', @q) eq $st) {
            next;
        }

If we've got down to here, the string is not in order, so increment the count.

        $t++;
    }
    return $t;
}

The other languages look every similar, even PostScript (using the 1 { ... } repeat trick to make a fake loop I can break out of with exit).

/lexicographic {
    2 dict begin
    0 exch
    {
        /st exch def
        st s2a quicksort /q exch def
        1 {
            q a2s st deepeq {
                exit
            } if
            q reverse a2s st deepeq {
                exit
            } if
            1 add
        } repeat
    } forall
    end
} bind def

Task 2: Two out of Three

You are given three array of integers.

Write a script to return all the elements that are present in at least 2 out of 3 given arrays.

Hashes with defaults again, as seen in last week's part 1. Python:

from collections import defaultdict

def twoofthree(a):

Set up my default-zero hash.

  ct = defaultdict(lambda: 0)

For each of the input lists (I don't care that there are exactly three of them):

  for iv in a:

Convert it to a set (we don't care how many times it's in this list, just whether it's here or not)

    for n in set(iv):

and increment the count of lists in which that value has appeared.

      ct[n] += 1

Then filter that counter hash for items that occur at least twice.

  out = list(k for k, v in ct.items() if v >= 2)

We've given up ordering by using a hash, so sort the final output.

  out.sort()
  return out

Full code on github.