# RogerBW's Blog

The Weekly Challenge 215: Placing the Odd 07 May 2023

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

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 {
exit
} if
} for
} forall
ct
end
} bind def
``````

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.