RogerBW's Blog

Perl Weekly Challenge 83: Length and Inversion 23 October 2020

I’ve been doing the Perl Weekly Challenges. The latest involved string manipulation and a numerical search. (Note that this is open until 25 October 2020.)

Task #1 › Words Length

You are given a string $S with 3 or more words.

Write a script to find the length of the string except the first and last words ignoring whitespace.

Given the constraint, I regard myself as being absolved from validating the parameter. There are basically four steps to the problem:

  • Split string into words
  • Remove first and last words
  • Remove whitespace
  • Find the length of what's left

But with Perl I can combine the first two into one:

  $s =~ s/^\S+\s+(.*?)\s+\S+$/$1/;

which is as readable as regular expressions usually are, but basically means "given the pattern word-space-something-space-word, return just the something". Then it's simple:

  $s =~ s/\s+//g;
  return length($s);

Raku works similarly except for =~ turning to ~~ and parameters being immutable.

sub wl($so) {
  my $s=$so;
  $s ~~ s/^\S+\s+(.*?)\s+\S+$/$0/;
  $s ~~ s:g/\s+//;
  return $s.chars;
}

In Python I split the string into an array of words, then rejoin some of it without the spaces.

def wl(s):
    a=s.split()
    return len(''.join(a[1:len(a)-1]))

though I find it a bit ugly that join and split are class methods while len isn't. Ruby seems more elegant in this regard (and lets me do frankly perverse things with the range operator):

def wl(s)
  a=s.split(' ')
  return a[1...-1].join('').length
end

Task #2 › Flip Array

You are given an array @A of positive numbers.

Write a script to flip the sign of some members of the given array so that the sum of the all members is minimum non-negative.

Given an array of positive elements, you have to flip the sign of some of its elements such that the resultant sum of the elements of array should be minimum non-negative(as close to zero as possible). Return the minimum no. of elements whose sign needs to be flipped such that the resultant sum is minimum non-negative.

I added a third example case so that the tests wouldn't be satisfactorily completed by just returning 1…

Because I'm looking for a minimum non-negative sum there aren't obvious short-cuts. (All right, I could drop out if I've found a solution that gives 0 as the answer.) So in Perl I use a bitmask: one bit per element, bit set means invert that element. To avoid summing more than needed, I start with a sum of the whole thing, then subtract the inverted elements twice.

sub fa {
  my @a=@_;
  my $n = (1 << scalar @a);
  my $ss=sum(@a);
  my $ls;
  my $li;
  foreach my $mask (1..$n-1) {
    my $s=$ss;
    my $m=1;
    my $inv=0;
    foreach my $i (0..$#a) {
      if ($m & $mask) {
        $inv++;
        $s -= 2*$a[$i];
      }
      $m <<= 1;
    }
    if ($s>=0 && (!defined $ls || $s < $ls || ($ls == $s && $inv < $li))) {
      $ls=$s;
      $li=$inv;
    }
  }
  return $li;
}

The other languages all have some sort of operator that'll spit out combinations of elements from a particular list, so I use that instead. Raku's is still the best, because it'll spit out combinations of all lengths in a single operation if you ask it to.

Mild confusion over operator precedence led to me dropping the ($s >= 0) test out of the big conditional in Raku, and I left it separate for the other languages.

sub fa(**@a) {
  my $ss=sum(@a);
  my $ls;
  my $li;
  for @a.combinations(1..@a.elems) -> $l {
    my $s=$ss-2*sum($l);
    if ($s >= 0) {
      if ((!defined $ls) || $s < $ls || ($ls == $s && $l.elems < $li)) {
        $ls=$s;
        $li=$l.elems;
      }
    }
  }
  return $li;
}

Python's combinations are only those of a single length. Since those lengths are a thing I'm iterating through anyway, not a problem; it's just a doubly-nested loop.

By carelessness, I omitted the li=0 on first pass, and it still worked. That's not a thing I feel should happen; I assume Python has some way of making it be treated as an error which I haven't found yet.

def fa(*a):
    ss=sum(a)
    ls=ss
    li=0
    for inv in range(1,len(a)):
        for l in combinations(a,inv):
            s=ss-2*sum(l)
            if (s >= 0):
                if (ls == ss or s < ls or (s == ls and inv < li)):
                    ls=s
                    li=inv
    return li

And Ruby is basically the same, though I think I'm finally getting the knack of the natively Ruby way of doing loops with local variables.

def fa(*a)
  ss=a.sum
  ls=ss
  li=0
  1.upto(a.length) do |inv|
    a.combination(inv) do |l|
      s=ss-2*l.sum
      if s >= 0
        if (ls == ss or s < ls or (s == ls and inv < li))
          ls=s
          li=inv
        end
      end
    end
  end
  return li
end

For this particular set of problems, Ruby was the language that I found most fun to write.

Full code on github.


  1. Posted by RogerBW at 01:16pm on 26 October 2020

    In part 1, some people liked to split the entire string into words, rather than only the first and last.

    In part 2, nobody seems to have come up with anything better than brute force, either bitmask or combinations.

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