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.

Comments on this post are now closed. If you have particular grounds for adding a late comment, comment on a more recent post quoting the URL of this one.