RogerBW's Blog

Perl Weekly Challenge 96: Reverse Distance 22 January 2021

I’ve been doing the Perl Weekly Challenges. The latest involved reversing words in a string and calculating Levenshtein distance. (Note that this is open until 24 January 2021.)

TASK #1 › Reverse Words

You are given a string $S.

Write a script to reverse the order of words in the given string. The string may contain leading/trailing spaces. The string may have more than one space between words in the string. Print the result without leading/trailing spaces and there should be only one space between words.

In Perl, this reduces trivially to "do you know how the split function works", a bit like the tr test back in #90.

sub rw {
  my $n=shift;
  return join(' ',reverse split ' ',$n);
}

In other languages it gets a little more interesting. Raku lets me put things in a sensible order:

  return $n.comb(/\S+/).reverse.join(' ');

Python makes me separate them:

def rw(n):
    t=n.split()
    t.reverse()
    return ' '.join(t)

Ruby lets me keep them in order:

  return n.split(' ').reverse.join(' ')

And Rust is… the only one of these languages that doesn't special-case split with a single space parameter to elide multiple spaces. Hey ho. But at least I have a grep-equivalent. I have to reverse in place as I do with Python.

fn rw(n: &str) -> String {
    let mut nr: Vec<&str>=n.split(' ').filter(|x| x.len()>0).collect();
    nr.reverse();
    let k=nr.join(" ");
    return k;
}

TASK #2 › Edit Distance

You are given two strings $S1 and $S2.

Write a script to find out the minimum operations required to convert $S1 into $S2. The operations can be insert, remove or replace a character. Please check out Wikipedia page for more information.

So this is Levenshtein distance (I do not think I have ever, in my computing career, had an actual use for this as distinct from the simpler "how many characters differ"), and therefore I shall stand on the feet of giants and implement Wagner-Fischer. There are lots of ways of making this less demanding of time and storage, which I do not use here. Here's the Raku version; they pretty much all look the same.

sub ed($s,$t) {
  my @ss=(0,$s.comb).flat;
  my @tt=(0,$t.comb).flat;
  my @d;
  for 0..@ss.end {
    push @d,[(0) xx (@tt.elems)];
  }
  map {@d[$_][0]=$_}, 1..@ss.end;
  map {@d[0][$_]=$_}, 1..@tt.end;
  for 1..@tt.end -> $j {
    for 1..@ss.end -> $i {
      my $sc=0;
      if (@ss[$i] ne @tt[$j]) {
        $sc=1;
      }
      @d[$i][$j]=min(
        @d[$i-1][$j]+1,
        @d[$i][$j-1]+1,
        @d[$i-1][$j-1]+$sc,
          );
    }
  }
  return @d[@ss.end][@tt.end];
}

(Except that, I find, Rust does have a built-in min function… but it takes only two parameters, or an iterator, not an arbitrary list of things. Feels wrong to turn this list into an iterator…)

            d[i][j]=min(
                d[i-1][j]+1,
                min(
                    d[i][j-1]+1,
                    d[i-1][j-1]+sc
                )
            );

Full code on github.

See also:
Perl Weekly Challenge 90: Ethiopian DNA

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 aeronautics aikakirja anecdote animation anime army astronomy audio audio tech aviation 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 cycling dead of winter doctor who documentary drama driving drone ecchi economics espionage essen 2015 essen 2016 essen 2017 essen 2018 essen 2019 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-nebula reread in brief avoid instrumented life julie enfield kickstarter learn to play leaving earth linux liquor lovecraftiana mecha men with beards museum music mystery naval 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 science fiction scythe second world war security shipwreck simutrans smartphone south atlantic war squaddies stationery steampunk stuarts suburbia superheroes suspense television the resistance 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