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.