# 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= * len(list)
for i in n:
nr=
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=
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.