RogerBW's Blog

Perl Weekly Challenge 80: missing numbers and jealous neighbours 29 September 2020

I’ve been doing the Perl Weekly Challenges. The latest involved missing numbers and more ranking of neighbours. (Note that this is open until 4 October 2020.)

TASK #1 › Smallest Positive Number Bits

You are given unsorted list of integers @N.

Write a script to find out the smallest positive number missing.

In other words, if there's no 1 to be found, output 1; if there's no 2, output 2; etc. So we dump the list (or at least the useful parts of it) into a hash for fast checking.

sub spn {
  my @list=@{shift @_};
  my %r=map {$_ => 1} grep {$_ > 0} @list;
  my $m=1;
  while (exists $r{$m}) {
    $m++;
  }
  return $m;
}

Another approach would be to sort the list and look at adjacent pairs of numbers until one found a gap, which might be better if you had a very long list; but this worked well enough. Raku is similar, though I used the Set structure rather than a hash with irrelevant values; after all, this sort of thing is what it's for.

sub spn(@list) {
  my $r=set grep {$_ > 0}, @list;
  my $m=1;
  while ($r{$m}:exists) {
    $m++;
  }
  return $m;
}

Python also has sets. (The frozenset is the immutable sort, and I don't need to change it. I also dropped the positivity constraint, because non-positive numbers won't get checked anyway and this looked cleaner.)

def spn(list):
    r=frozenset(list)
    m=1
    while m in r:
        m += 1
    return m

And what's this, another language? Well, Ruby is the native language of Discourse and I've had to learn a bit of it to write my dice-roller plugin. Here I use a plain hash and unwrap the one-liner, which seems to be a more Rubyish way of doing things. (Ruby does have sets too, but I didn't know about them at the time.)

def spn(list)
  r=Hash.new
  for x in list
    if x > 0
      r[x]=1
    end
  end
  m=1
  while r.has_key?(m)
    m += 1
  end
  return m
end

TASK #2 › Count Candies

You are given rankings of @N candidates.

Write a script to find out the total candies needed for all candidates. You are asked to follow the rules below:

a) You must given at least one candy to each candidate.

b) Candidate with higher ranking get more candies than their mmediate neighbors on either side.

The first example makes this clearer: "ranking" values are actually "score" values, with larger numbers indicating a higher ranking. Then the second example makes it less clear, giving one entry a bonus of two for being higher than both its neighbours; I don't think this is what's intended, though it gives the right result.

This felt quite like last week's rainy histograms, and I solved it with a similar approach: generate a second list containing the indices of the first list in ascending, or at least non-descending, order. Using that order, assign to each index a value that's one greater than its lower neighbours' values.

sub cc {
  my @list=@{shift @_};

Generate the second list:

  my @n=sort {$list[$a] <=> $list[$b]} (0..$#list);
  my @k;
  foreach my $i (@n) {

The minimum value we'll assign is 1.

    my @nr=(1);

If we have a lower neighbour, and it's smaller than us, we put its assigned value plus 1 on the list of possible assignment values.

    if ($i > 0 && $list[$i-1] < $list[$i]) {
      if (defined $k[$i-1]) {
        push @nr,$k[$i-1]+1;
      }
    }

Ditto for the upper neighbour.

    if ($i < $#list && $list[$i+1] < $list[$i]) {
      if (defined $k[$i+1]) {
        push @nr,$k[$i+1]+1;
      }
    }

Assign the highest value in the list.

    $k[$i]=max(@nr);
  }

Return the total.

  return sum(@k);
}

Raku works almost identically:

sub cc(@list) {
  my @n=sort {@list[$^a] <=> @list[$^b]}, (0..@list.end);
  my @k;
  for @n -> $i {
    my @nr=(1);
    if ($i > 0 && @list[$i-1] < @list[$i]) {
      if (defined @k[$i-1]) {
        push @nr,@k[$i-1]+1;
      }
    }
    if ($i < @list.end && @list[$i+1] < @list[$i]) {
      if (defined @k[$i+1]) {
        push @nr,@k[$i+1]+1;
      }
    }
    @k[$i]=max(@nr);
  }
  return sum(@k);
}

Python isn't as happy with uninitialised elements, so rather than muck about with that I set them all to zero.

def cc(list):
    n=sorted(range(len(list)), key=lambda x: list[x])
    k=[0] * len(list)
    for i in n:
        nr=[1]
        if (i > 0 and list[i-1] < list[i]):
            nr.append(k[i-1]+1)
        if (i < len(list)-1 and list[i+1] < list[i]):
            nr.append(k[i+1]+1)
        k[i]=max(nr)
    return sum(k)

And similarly in Ruby - with a lovely baroque initialisation syntax!

def cc(list)
  n=(0...list.length).sort_by {|x| list[x]}
  k=Array.new(list.length) {0}
  for i in n
    nr=[1]
    if i > 0 && list[i-1] < list[i]
      nr.push(k[i-1]+1)
    end
    if i < list.length-1 && list[i+1] < list[i]
      nr.push(k[i+1]+1)
    end
    k[i]=nr.max
  end
  return k.sum
end

Full code on github.


  1. Posted by RogerBW at 12:47pm on 06 October 2020

    For part 1, several people sorted the list first - which I suppose is fair enough. Perl's hash lookups are heavily optimised, so any time I have a problem that takes the form "is value X in list Y" I tend to reach for a hash.

    I suspect a more stylish way, in languages that can do it, would be to take the difference between the (infinite) set of positive integers and the input set, then find the lowest value.

    For part 2, there was some confusion over just what the problem was meant to be (the second example used reasoning not consistent with the problem statement to get the same result). Those who interpreted as I did split between iterating back and forth between neighbours and working in ascending rank order.

Add A Comment

Your Name
Your Email
Your Comment

Your submission will be ignored if any field is left blank, but your email address will not be displayed. Comments will be processed through markdown.

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 base commerce battletech beer boardgaming book of the week bookmonth chain of command children 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 geodata gin gurps gurps 101 harpoon historical history horror hugo 2014 hugo 2015 hugo 2016 hugo 2017 hugo 2018 hugo 2019 hugo 2020 hugo-nebula reread humour in brief avoid instrumented life kickstarter learn to play leaving earth linux lovecraftiana mecha men with beards museum mystery naval non-fiction one for the brow opera perl perl weekly challenge photography podcast politics 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 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