| 30 August 2024 | Challenge 284 |
Relatively Lucky
Task 1: Lucky Integer
Submitted by: Mohammad Sajid Anwar
You are given an array of integers, @ints.
Write a script to find the lucky integer if found otherwise return -1.
If there are more than one then return the largest.
A lucky integer is an integer that has a frequency in the array equal to its value.
Example 1
Input: @ints = (2, 2, 3, 4)
Output: 2
Example 2
Input: @ints = (1, 2, 2, 3, 3, 3)
Output: 3
Example 3
Input: @ints = (1, 1, 1, 3)
Output: -1
Solution
The task may be almost literally transformed into the language of PDL:
We find the frequencies for @ints, sorted in ascending order by value, limit these to lucky numbers where the value equals the frequency and pick the largest (i.e. the final) value - or minus one.
use strict;
use warnings;
use PDL '2.017';
use PDL::NiceSlice;
sub lucky_integer {
my ($freq, $val) = rle long(@_)->qsort;
my $lucky = $val->where($freq == $val);
$lucky->isempty ? -1 : $lucky(-1;-);
}
See the full solution to task 1.
Task 2: Relative Sort
Submitted by: Mohammad Sajid Anwar
You are given two list of integers, @list1 and @list2.
The elements in the @list2 are distinct and also in the @list1.
Write a script to sort the elements in the @list1 such that the relative order of items in @list1 is same as in the @list2.
Elements that is missing in @list2 should be placed at the end of @list1 in ascending order.
Example 1
Input: @list1 = (2, 3, 9, 3, 1, 4, 6, 7, 2, 8, 5)
@list2 = (2, 1, 4, 3, 5, 6)
Output: (2, 2, 1, 4, 3, 3, 5, 6, 7, 8, 9)
Example 2
Input: @list1 = (3, 3, 4, 6, 2, 4, 2, 1, 3)
@list2 = (1, 3, 2)
Output: (1, 3, 3, 3, 2, 2, 4, 4, 6)
Example 3
Input: @list1 = (3, 0, 5, 0, 2, 1, 4, 1, 1)
@list2 = (1, 0, 3, 2)
Output: (1, 1, 1, 0, 0, 3, 2, 4, 5)
Solution
We may build two partitions from @list1:
- partition 1 contains all elements that appear in
@list2 - partition 2 contains the rest.
These partitions need to be sorted by different criteria and then be concatenated.
- For partition 1 we perform a simplified counting sort with an order as given by
@list2. - For partition 2 we perform a standard numerical sort.
As we need one pass through the list to build the two partitions anyway, we may perform the counting step for the counting sort along the way.
Afterwards we find the sorted partition 1 by collecting the counted number of items in the order given by @list2 and we numerically sort partition 2.
use strict;
use warnings;
use experimental 'signatures';
sub relative_sort ($list1, $list2) {
(\my %list2)->@{@$list2} = ();
my @part2;
for my $n (@$list1) {
if (exists $list2{$n}) {
$list2{$n}++;
} else {
push @part2, $n;
}
}
[
(map +($_) x $list2{$_}, @$list2),
(sort {$a <=> $b} @part2),
];
}
See the full solution to task 2.
If you have a question about this post or if you like to comment on it, feel free to open an issue in my github repository.