RogerBW's Blog

I’ve been doing the Weekly Challenges. The latest involved sorting words and modifying sequences. (Note that this is open until 7 May 2023.)

Task 1: Odd one Out

You are given a list of words (alphabetic characters only) of same size.

Write a script to remove all words not sorted alphabetically and print the number of words in the list that are not alphabetically sorted.

The simplest-to-program way to find out whether a string is sorted is to sort its contents, then compare with the original. Perl:

sub oddoneout($a) {
  my $ct = 0;
  foreach my $s (@{$a}) {
    my $t = join('', sort split '',$s);
    if ($s ne $t) {
      $ct++;
    }
  }
  return $ct;
}

A computationally cheaper approach, which I used in some languages where it felt more idiomatic, is to look at the characters pairwise, and bail out if character N-1 is greater in value than character N. PostScript:

/oddoneout {
    3 dict begin
    /ct 0 def
    {
        /s exch def
        1 1 s length 1 sub {
            /i exch def
            s i 1 sub get s i get gt {
                /ct ct 1 add def
                exit
            } if
        } for
    } forall
    ct
    end
} bind def

Task 2: Number Placement

You are given a list of numbers having just 0 and 1. You are also given placement count (>=1).

Write a script to find out if it is possible to replace 0 with 1 in the given list. The only condition is that you can only replace when there is no 1 on either side. Print 1 if it is possible otherwise 0.

One could try actually inserting the values, but I noticed that for each run of zeroes of length n I can perform (n - 1) / 2 (rounded down) replacements. Length 3 gives 1, as does length 4; length 5 gives 2, as does length 6; and so on.

So all I do is count the lengths of the zero runs, then work out from that the total number of possible replacements. If that's no lower than the number I'm asked for, return true.

I'm iterating over overlapping pairs of numbers, and using windowed or rotor in the languages that support it would make some sense – but I also need the index value, so it seemed easier to avoid the extra complication rather than mucking about with enumerate etc.

Rust:

fn numberplacement(a0: Vec<u8>, ct: u32) -> bool {

Set up a list that wraps the original with "1" entries, so that all runs of zero are bounded - this saves special-case code for the start and end of the array later.

    let mut a: Vec<u8> = vec![1; a0.len() + 2];
    a.splice( 1 ..= a0.len(), a0);
    let mut s = 0;
    let mut tt = 0;

Starting at the second entry and running to the end:

    for i in 1 .. a.len() {

Look for patterns of previous and current entry.

        match (a[i - 1], a[i]) {

If it's the start of a run, note the index.

            (1, 0) => { s = i; },

If it's the end of a run, add the number of possible substitutions.

            (0, 1) => { tt += (i - s) / 2; },

Otherwise, ignore.

            _ => (),
        }
    }
    ct <= tt as u32
}

…all right, I like match and I think it's clear, but it's easily enough phrased more conventionally, as in Raku:

sub numberplacement(@a0, $ct) {
    my @a = (1, );
    @a.append(@a0);
    @a.push(1);
    my $s = 0;
    my $tt = 0;
    for (1..@a.end) -> $i {
        if (@a[$i - 1] == 1 && @a[$i] == 0) {
            $s = $i;
        } elsif (@a[$i - 1] == 0 && @a[$i] == 1) {
            $tt += floor(($i - $s)/2);
        }
    }
    return $ct <= $tt;
}

Full code on github.