This post is part of a series on Mohammad Anwar’s excellent Weekly Challenge, where hackers submit solutions in Perl, Raku, or any other language, to two different challenges every week. (It’s a lot of fun, if you’re into that sort of thing.)
Task #2 this week is described as follows:
You are given a list, @L, of three or more random integers between 1 and 50. A Noble Integer is an integer N in @L, such that there are exactly N integers greater than N in @L. Output any Noble Integer found in @L, or an empty list if none were found.
An interesting question is whether or not there can be multiple Noble Integers in a list.
For example, suppose we have list of 4 integers [2, 6, 1, 3].
Here we have 2 in the above list, known as Noble Integer, since there are exactly 2 integers in the list i.e. 3 and 6, which are greater than 2.
Therefore the script would print 2.
While Mohammad gave me credit for submitting this problem, I only suggested some wording changes right before it was published, so I didn’t have any sort of advantage going in.
The algorithm I came up with for finding Noble Integers is fairly simple and seems obvious: simply sort the array, and then for each array index, $i, @L.end - $i is the number of elements that come after. @L.end in Raku is $#L in Perl: the last index in the array.
To find a Noble Integer then, we just need to know if @L[$i] == @L.end - $i.
Perl
my @L = sort { $a <=> $b } @_;
map { $L[$_] == $#L - $_ ? $L[$_] : () } 0..$#L;
I’m using map instead of grep because I’m looping over the indicies, but I want the value as the result. Another option is to use map { $L[$_] } grep { ... } 0..$#L:
my @L = sort { $a <=> $b } @_;
map { $L[$_] } grep { $L[$_] == $#L - $_ } 0..$#L;
That’s probably just a bit clearer. Not a huge difference, in my opinion.
Raku
@L.sort.pairs.grep({ @L.end - .key == .value })».value;
What else do you need! pairs is nice. To be fair, Perl does have each, which I did use in an earlier iteration, but it is more cumbersome to use in cases like this.
There can be only one
The question of whether there can be more than one Noble Integer in a given list seems easy to answer: no.
Need more convincing? Here’s a quick and very informal proof by contradiction:
Hypothesis: there can be more than one Noble Integer in a list. Sort the list. Let n be a Noble Integer in list L, and suppose it is the smallest Noble Integer in the list. By definition, there are n more integers in the list after L.
Let x be a Noble Integer in L, greater than n. For x to exist, there would have to be at least n + 1 integers greater than x. Since the list is sorted, and x > n, there is no way we could have n + 1 integers greater than x, as that would mean there would be at least n + 2 integers greater than n, meaning n would not be a Noble Integer. Contradiction. Therefore, we reject our original hypothesis, meaning it is impossible for there to be more than one Noble Integer in a list.