RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved letter hunting and array construction. (Note that this ends today.)

Task 1: Greatest English Letter

You are given a string, $str, made up of only alphabetic characters [a..zA..Z].

Write a script to return the greatest english letter in the given string.

A letter is greatest if it occurs as lower and upper case. Also letter ‘b' is greater than ‘a' if ‘b' appears after ‘a' in the English alphabet.

So I want a list of letters that have appeared in both upper and lower case. I could do this with two sets and intersect them, but as it turned out I thought of bit flags first, so that's what I used. Perl:

sub greatestenglishletter($a) {
  my %m;

For each character,

  foreach my $c (split '', $a) {

get the upper-case version;

    my $uc = uc($c);

set flag to 1 for upper case, 2 for lower;

    my $flag = ($uc eq $c)?2:1;

and bitwise-or the hash value for the upper case character (defaulting to zero) with the flag.

    $m{$uc} |= $flag;
  }

Filter the hash for flag = 3, and sort the keys.

  my @k = sort grep {$m{$_} == 3} keys %m;

Return the last of the output values.

  return $k[-1] || '';
}

In Rust I can use a BTreeMap, which is always sorted. The retain method is quite neat too.

fn greatestenglishletter(a: &str) -> String {
    let mut m: BTreeMap<char, u32> = BTreeMap::new();
    for c in a.chars() {
        let uc = c.to_ascii_uppercase();
        let flag = if c.is_uppercase() { 1 } else { 2 };
        let fv = m.entry(uc).or_insert(0);
        *fv |= flag;
    }
    m.retain(|_, v| *v == 3);
    if m.len() > 0 {
        m.keys().last().unwrap().to_string()
    } else {
        "".to_string()
    }
}

Task 2: Target Array

You are given two arrays of integers, @source and @indices. The @indices can only contains integers 0 <= i < size of @source.

Write a script to create target array by insert at index $indices[i] the value $source[i].

So I have to insert at a set position in the growing output array. Pretty much everything has some sort of insert or splice method. JavaScript:

function targetarray(a, indices) {

Set up output array.

    let c = [];
    indices.forEach((ix, i) => {

If this value is going at the end, insert/splice might work, but push is simpler.

        if (ix == c.length) {
            c.push(a[i]);

Otherwise, insert it at the relevant spot.

        } else {
            c.splice(ix, 0, a[i]);
        }
    });
    return c;
}

PostScript arrays are of course immutable (ho ho). So I'll build up a gradually increasing stack, rotating it to get the right spot to insert the next value.

/targetarray {
    0 dict begin
    /indices exch def
    /a exch def

Keep track of the array's length, and mark bottom of stack.

    /d 0 def
    [

Get index values.

        indices enumerate.array {
            aload pop
            /ix exch def
            /i exch def

If we're not inserting at start or end, rotate the array in progress down to the right place.

            ix d ne ix 0 ne and {
                d ix neg roll
            } if

Push the value to top of stack.

            a i get

If the value wasn't being inserted at the end, rotate the array (including new value) back up to where it started.

            ix d ne {
                d 1 add ix 1 add roll
            } if

Add 1 to the length counter. (Yeah, I could use counttomark, but when I'm using the stack for operands as well it seems easier to do it this way.)

            /d d 1 add def
        } forall

Finish and return the array.

    ]
    end
} bind def

(I could have done this with astore, omitting the square brackets and finishing with d array astore, which I think is the "official" approach, but it doesn't seem any cleaner.)

Full code on github.