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.