| 28 February 2025 | Challenge 310 |
Odd Sets
Task 1: Arrays Intersection
Submitted by: Mohammad Sajid Anwar
You are given a list of array of integers.
Write a script to return the common elements in all the arrays.
Example 1
Input: $list = ( [1, 2, 3, 4], [4, 5, 6, 1], [4, 2, 1, 3] )
Output: (1, 4)
Example 2
Input: $list = ( [1, 0, 2, 3], [2, 4, 5] )
Output: (2)
Example 3
Input: $list = ( [1, 2, 3], [4, 5], [6] )
Output: ()
Solution
PDL has a function
setops (and
intersect as a wrapper) to find set intersections.
Both have in common that these operate on two sets, whereas in this task we shall handle a variable number of sets.
Simply looping over the given sets would solve the task, but we may play around with some of PDL’s features.
When encasing the loop in a broadcast_define‘ed function, it becomes broadcasting aware.
Let’s try it.
Obviously this will not lead to the simplest solution, but it is a nice new lesson in PDL for me.
We define a function intersect_over that takes a 2-d ndarray as input - the list of sets - and produces a 1-d ndarray as output - the intersection over all sets.
When we take the sets as columns of a 2-d ndarray, all of them have to be of the same size.
As this is obviously not a precondition in this task, we need to fill the sets with some kind of “non-elements”.
Here PDL’s BAD values come handy.
But then the question arises, how to handle a set that has BAD values only: shall we treat it as the empty set or shall we ignore it?
Though it might seem counter-intuitive, we’ll follow the latter interpretation.
See below for the reason behind this decision.
We take a temporary set that will be initialized with the first given set and afterwards is replaced with the intersection of itself and the next set from the list.
The result is filled with BAD values to the uniform length of the input sets.
Here is the definition of intersect_over:
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
broadcast_define 'intersect_over(a(m,n);[o]b(n))' => over {
my $tmp;
for my $set ($_[0]->xchg(0, 1)->dog) {
$tmp = $set, next unless defined $tmp;
next unless $set->ngood;
$tmp = intersect $tmp, $set;
}
my $card = $tmp->nelem;
$tmp->reshape($_[1]->dims);
$_[1] .= $tmp->setbadif(sequence($tmp) >= $card);
};
This function enables a simple solution for this task,
where we instruct the PDL constructor to append BAD values for missing elements.
sub arrays_intersection {
local $PDL::undefval = long->badvalue;
my $list = long(@_)->xchg(0, 1);
$list->badflag(1);
intersect_over($list, my $res = null);
$res;
}
Performing example 1 in the pdl shell, where we need to filter out the BAD values from the result:
pdl> do "./ch-1.pl"
pdl> do_print 1
1
pdl> $ex1 = arrays_intersection([1, 2, 3, 4], [4, 5, 6, 1], [4, 2, 1, 3])
[1 4 BAD BAD]
pdl> $ex1->($ex1->isgood;?)
[1 4]
Now coming back to broadcasting.
As our function intersect_over is broadcasting-aware, we may provide higher-dimensional ndarrays as input, such as processing all three examples simultaneously by “stacking” the arrays:
pdl> $all = arrays_intersection([[1, 2, 3, 4], [4, 5, 6, 1], [4, 2, 1, 3]],
> [[1, 0, 2, 3], [2, 4, 5]],
> [[1, 2, 3], [4, 5], [6]])
[
[ 1 4 BAD BAD]
[ 2 BAD BAD BAD]
[BAD BAD BAD BAD]
]
pdl> p $_($_->isgood;?) for $all->dog
[1 4]
[2]
Empty[0]
Finally: Why do we interpret an all-BAD column as “missing” instead of “empty”?
Example 2 has only two sets.
When stacking all three examples together, there is one complete set missing in example 2 that will be represented by BAD values.
Interpreting it as “empty”, would give a different result.
In contrast, an all-BAD row in the output represents the empty set.
See the full solution to task 1.
Task 2: Sort Odd Even
Submitted by: Mohammad Sajid Anwar
You are given an array of integers.
Write a script to sort odd index elements in decreasing order and even index elements in increasing order in the given array.
Example 1
Input: @ints = (4, 1, 2, 3)
Output: (2, 3, 4, 1)
Even index elements: 4, 2 => 2, 4 (increasing order)
Odd index elements : 1, 3 => 3, 1 (decreasing order)
Example 2
Input: @ints = (3, 1)
Output: (3, 1)
Example 3
Input: @ints = (5, 3, 2, 1, 4)
Output: (2, 3, 4, 1, 5)
Even index elements: 5, 2, 4 => 2, 4, 5 (increasing order)
Odd index elements : 3, 1 => 3, 1 (decreasing order)
Solution
Using PDL we create two slices from the list of numbers corresponding to even resp. odd indices.
As the slices are connected to the original data, we may individually
sort them
inplace according to the requested order.
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
sub sort_odd_even {
my $ints = long \@_;
$ints(0:-1:2)->inplace->qsort;
$ints(1:-1:2)->(-1:0)->inplace->qsort;
$ints;
}
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.