The Weekly Challenge - 263 (April 1st 2024)
Task #1: Target Index
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 $k[2] = 2
Sorted array is (1, 2, 2, 3, 4, 5), index 1 and 2 have value 2.
Example 2
Input: @ints = (1, 2, 4, 3, 5), $k = 6 Output: ()
No entries have value 6 – so no matches.
Example 3
Input: @ints = (5, 3, 2, 4, 2, 1), $k = 4 Output: (4)
Sorted array is (1, 2, 2, 3, 4, 5), value at index 4 is equal to 4.
Solution
It looks like we need to sort – BUT WE DON’T – we know that the first index will be the number of numbers less than $k, and the number of matching numbers is the number of numbers equal to $k.
Like last week, we use the spaceship operator to compute the values larger/smaller than $k.
If we create the counts array (0) x 3, then the number smaller are in $c[-1] OR $c[2], the number the same are in $c[0].
So we just need to output the list of numbers starting at $c[2] of length $c[0]…
challenge-263-task-1 - perl
sub target_index {
my( $k, @c ) = ( pop, 0, 0, 0 );
$c[ $_ <=> $k ]++ for @_;
$c[2] .. $c[2] + $c[0] - 1
}
Spaceship operator <=> returns values -1,0,1 depending on the sign of the difference.
Task #2: Merge Items
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] ]
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
We don’t need to know which group the count is from – in fact the code below works if you have 1, 2, 3 or even 100 lists.
We loop through every pair in every list updating the count for the key…
We code simplify the code to use:
$code{ $_->[0] } += $_->[1] for map { @{$_} } @_;
but this could have memory issues as you have to create a new array and loop over it. So we use two loops instead. One example of where code golf can cause a major inefficiency.
We store the values of the hash and return the keys and values as a list of pairs rather than the normal hash structure.
challenge-263-task-2 - perl
sub merge_items {
my %c;
for( @_ ) {
$c{ $_->[0] } += $_->[1] for @{$_}
}
map { [ 0 + $_ => $c{$_} ] } keys %c
}
Note we add 0 to the key value to cast as a number.
About The Weekly Challenge
The weekly challenge was set up Mohammad Anwar approximately 5 years ago - each Monday two problems are set for the "team" to solve.
These are posted at: