RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved an array mapping and a custom sort. (Note that this ends today.)

Task 1: Binary Prefix

You are given a binary array.

Write a script to return an array of booleans where the partial binary number up to that point is prime.

This is basically a slightly extended mapping. In Rust (which doesn't have built-in prime finding so I use my own code):

Integer square root. I don't really need this but it feels cleaner.

fn isqrt(s: u32) -> u32 {
    if s <= 1 {
        return s;
    }
    let mut x0 = s / 2;
    let mut x1 = (x0 + s / x0) / 2;
    while x1 < x0 {
        x0 = x1;
        x1 = (x0 + s / x0) / 2;
    }           
    return x0;
}

Primality tester by reasonably efficient trial division (2, 3, then 6n±1). Uses the isqrt function to establish an upper bound.

fn is_prime(n: u32) -> bool {
    if n == 1 {
        return false;
    }
    if n>2 && n%2==0 {
        return false;
    }
    if n>3 && n%3==0 {
        return false;
    }
    let lim = isqrt(n);
    let mut k6 = 0;
    loop {
        k6 += 6;
        for t in [k6 - 1,k6 + 1] {
            if t <= lim {
                if n % t == 0 {
                    return false;
                }
            } else {
                return true;
            }
        }
    }
}

The actual task is almost trivial: iterate over the input to generate the current value, test, output.

fn binaryprefix(a: Vec<u8>) -> Vec<bool> {
    let mut out = Vec::new();
    let mut n = 0;
    for x in a {
        n *= 2;
        if x == 1 {
            n += 1;
        }
        out.push(is_prime(n));
    }
    out
}

Task 2: Alien Dictionary

You are given a list of words and alien dictionary character order.

Write a script to sort lexicographically the given list of words based on the alien dictionary characters.

This basically needs a custom sort; my solutions to task 301 part 1 used something similar. I ended up using large integer encoding rather than a string mapping, because these are all fairly short strings and because it amused me; to do it "properly" I'd map each string with a lexicographic encoding. Anyway, Raku:

sub aliendictionary(@a, @dc) {

Get the maximum input string length.

  my $mxl = @a.map({$_.chars}).max;

Build the table of letter values (1 to 26; 0 is reserved for "no letter in this position").

  my %dh;
  for @dc.kv -> $i, $c {
    %dh{$c} = $i + 1;
  }
  my @b = @a;

Build the list of numeric encodings. Letter bu letter, add the letter's value (or 0 once we're off the end of the strhing).

  my %numerics;
  for @b -> $w {
    my $n = 0;
    my @cc = $w.comb;
    for 0 ..^ $mxl -> $i {
      $n *= 27;
      if ($i < $w.chars) {
        $n += %dh{@cc[$i]};
      }
    }
    %numerics{$w} = $n;
  }

Then sort using that encoding list.

  @b = @b.sort({ %numerics{$^a} <=> %numerics{$^b} });
  return @b;
}

Here's the "proper" version in Raku as a proof of concept. It builds the sort keys by sorting the given keys, then assigns them in order to a lexical map.

sub aliendictionary(@a, @dc) {
  my $mxl = @a.map({$_.chars}).max;
  my %dh;
  my @lx = @dc.sort;
  for @dc.kv -> $i, $c {
    %dh{$c} = @lx[$i];
  }
  my @b = @a;
  my %lex;
  for @b -> $w {
      %lex{$w} = $w.comb.map({%dh{$_}}).join("");
  }
  @b = @b.sort({ %lex{$^a} cmp %lex{$^b} });
  return @b;
}

Full code on github.