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.)

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.

Search
Archive
Tags 1920s 1930s 1940s 1950s 1960s 1970s 1980s 1990s 2000s 2010s 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech beer boardgaming book of the week bookmonth chain of command children chris chronicle church of no redeeming virtues cold war comedy computing contemporary cornish smuggler cosmic encounter coup covid-19 crime crystal cthulhu eternal cycling dead of winter doctor who documentary drama driving drone ecchi economics en garde espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 essen 2022 essen 2023 existential risk falklands war fandom fanfic fantasy feminism film firefly first world war flash point flight simulation food garmin drive gazebo genesys geocaching geodata gin gkp gurps gurps 101 gus harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo 2021 hugo 2022 hugo 2023 hugo 2024 hugo-nebula reread in brief avoid instrumented life javascript julian simpson julie enfield kickstarter kotlin learn to play leaving earth linux liquor lovecraftiana lua mecha men with beards mpd museum music mystery naval noir non-fiction one for the brow opera parody paul temple perl perl weekly challenge photography podcast politics postscript powers prediction privacy project woolsack pyracantha python quantum rail raku ranting raspberry pi reading reading boardgames social real life restaurant reviews romance rpg a day rpgs ruby rust scala science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance the weekly challenge thirsty meeples thriller tin soldier torg toys trailers travel type 26 type 31 type 45 vietnam war war wargaming weather wives and sweethearts writing about writing x-wing young adult
Special All book reviews, All film reviews
Produced by aikakirja v0.1