| 05 April 2024 | Challenge 263 |
Which Witch?
This week brings a new occasion for some PDL witchery.
Task 1: Target Index
Submitted by: Mohammad Sajid Anwar
You are given an array of integers, @ints and a target element $k.
Write a script to return the list of indices in the sorted array where the element is same as the given target element.
Example 1
Input: @ints = (1, 5, 3, 2, 4, 2), $k = 2
Output: (1, 2)
Sorted array: (1, 2, 2, 3, 4, 5)
Target indices: (1, 2) as $ints[1] = 2 and $ints[2] = 2
Example 2
Input: @ints = (1, 2, 4, 3, 5), $k = 6
Output: ()
No element in the given array matching the given target.
Example 3
Input: @ints = (5, 3, 2, 4, 2, 1), $k = 4
Output: (4)
Sorted array: (1, 2, 2, 3, 4, 5)
Target index: (4) as $ints[4] = 4
Solution
With which as one of PDL’s “primitive” functions, this task can be solved as a one-liner.
use strict;
use warnings;
use PDL;
sub t_idx {
my $k = shift;
which $k == pdl(@_)->qsort;
}
See the full solution.
Task 2: Merge Items
Submitted by: Mohammad Sajid Anwar
You are given two 2-D array of positive integers, $items1 and $items2 where element is pair of (item_id, item_quantity).
Write a script to return the merged items.
Example 1
Input: $items1 = [ [1,1], [2,1], [3,2] ]
$items2 = [ [2,2], [1,3] ]
Output: [ [1,4], [2,3], [3,2] ]
Item id (1) appears 2 times: [1,1] and [1,3]. Merged item now (1,4)
Item id (2) appears 2 times: [2,1] and [2,2]. Merged item now (2,3)
Item id (3) appears 1 time: [3,2]
Example 2
Input: $items1 = [ [1,2], [2,3], [1,3], [3,2] ]
$items2 = [ [3,1], [1,3] ]
Output: [ [1,8], [2,3], [3,3] ]
Example 3
Input: $items1 = [ [1,1], [2,2], [3,3] ]
$items2 = [ [2,3], [2,4] ]
Output: [ [1,1], [2,9], [3,3] ]
Solution
At first glance the given items look like sparse vectors, which is disproved by Example 2, where an index appears twice within the same list.
Nevertheless following a sparse vector approach, again utilizing the magic of PDL.
The supplementary module PDL::CCS provides a convenient implementation of “compressed column storage” sparse vectors, matrices etc.
- First we create a list of 2-d ndarrays from the given data.
- Next we identify all indices contained within the ndarrays.
- Then we build a sparse vector that has zero values at the previously found index positions.
- All item values are then added to their corresponding index position in the sparse vector.
- Finally we pair the indices with their value sums.
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
use PDL::CCS;
sub merge_items {
my @pdl = map pdl($_), @_;
my $which = null->glue(0, map $_((0)), @pdl)->uniq;
my $sum = PDL::CCS::Nd->newFromWhich($which->dummy(0), zeroes($which),
missing => 'BAD');
$sum->indexND($_(0)) += $_(1) for null->glue(1, @pdl)->dog;
$which->cat($sum->whichVals)->xchg(0, 1);
}
See the full solution.