RogerBW's Blog

The Weekly Challenge 226: Shuffling Zeroes 23 July 2023

I’ve been doing the Weekly Challenges. The latest involved string convolution and array reduction. (Note that this ends today.)

Task 1: Shuffle String

You are given a string and an array of indices of same length as string.

Write a script to return the string after re-arranging the indices in the correct order.

Each entry is the index into the target string: so a entry of 3 at position 0 means "take character 0 from the original, and place it at position 3 in the output".

There are two language features that affect how this problem gets solved. First, are strings casually treated as character arrays? If so (JavaScript, Kotlin, PostScript, Python, Ruby), I can index into them. Otherwise (Lua, Perl, Raku, Rust), I split the string into an array so that I can index into that.

Second, are strings invariant? If they aren't (PostScript, Ruby), then I can build an output string and insert characters into it in arbitrary order. If they are invariant or simply if they aren't casually write-indexable (JavaScript, Kotlin, Lua, Perl, Python, Raku, Rust), I do the same with an array and then combine it.

Rust:

fn shufflestring(st: &str, mp: Vec<usize>) -> String {
    let q = st.chars().collect::<Vec<char>>();
    let mut r = vec![' '; q.len()];
    for (i, ix) in mp.iter().enumerate() {
        r[*ix] = q[i];
    }
    r.iter().collect::<String>()
}

PostScript:

/shufflestring {
    4 dict begin
    /mp exch def
    /st exch def
    /r st length string def
    0 1 mp length 1 sub {
        /ix exch def
        r mp ix get st ix get put
    } for
    r
    end
} bind def

Task 2: Zero Array

You are given an array of non-negative integers, @ints.

Write a script to return the minimum number of operations to make every element equal zero.

In each operation, you are required to pick a positive number less than or equal to the smallest element in the array, then subtract that from each positive element in the array.

One could do this by the iterative process shown, but it's easier to give it some thought and see that that process maps to "always pick the highest possible positive number" and therefore the answer is the number of distinct non-zero values in the input. In other words, we can use a set (where available) or a hash (where not) and it's a very straightforward three-step process, here in Perl:

sub zeroarray($a) {

Turn the array into a set (or hash).

  my %s = map {$_ => 1} @{$a};

Delete set/hash key zero.

  delete $s{0};

Return the number of keys left.

  return scalar keys %s;
}

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 2300ad 3d printing action advent of code aeronautics aikakirja anecdote animation anime army astronomy audio audio tech base commerce battletech bayern 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 essen 2024 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