| 05 September 2025 | Challenge 337 |
Smaller Oddities
Task 1: Smaller Than Current
Submitted by: Mohammad Sajid Anwar
You are given an array of numbers, @num1.
Write a script to return an array, @num2, where $num2[i] is the count of all numbers less than or equal to $num1[i].
Example 1
Input: @num1 = (6, 5, 4, 8)
Output: (2, 1, 0, 3)
index 0: numbers <= 6 are 5, 4 => 2
index 1: numbers <= 5 are 4 => 1
index 2: numbers <= 4, none => 0
index 3: numbers <= 8 are 6, 5, 4 => 3
Example 2
Input: @num1 = (7, 7, 7, 7)
Output: (3, 3, 3, 3)
Example 3
Input: @num1 = (5, 4, 3, 2, 1)
Output: (4, 3, 2, 1, 0)
Example 4
Input: @num1 = (-1, 0, 3, -2, 1)
Output: (1, 2, 4, 0, 3)
Example 5
Input: @num1 = (0, 1, 1, 2, 0)
Output: (1, 3, 3, 4, 1)
Solution
In PDL, a solution could be as simple as
($num->dummy(0) >= $num)->sumover - 1;
But as this operates on all pairs from the list, it has a complexity of \(\mathcal{O}(n^2)\), which is not desirable.
Trying something more efficient.
In a sorted list we find the number of items not larger than the current item as the number of items preceding it plus the number of items equal to itself succeeding it. The number of preceding items equals the zero-based position of the current item and the number of succeeding equal items corresponds to a reverse local enumeration.
By not just sorting the list but indexing it with the result of an index sort, the sorted ndarray is connected to its parent via data-flow. Modifications in the sorted ndarray will propagate to the unsorted parent.
This approach is dominated by the sort, leading to a complexity of \(\mathcal{O}(n \log n)\).
Here is a step-by-step solution to example 5 in the
PDL shell:
Create the number array:
pdl> do_print 1
1
pdl> $num = long 0, 1, 1, 2, 0
[0 1 1 2 0]
Create a sorted view:
pdl> $sort = $num($num->qsorti)
[0 0 1 1 2]
Note: This sort is not stable, which does not harm here as equal items will receive the same value in the end.
Reverse enumerate the sorted array, overwriting the parent’s data:
pdl> $sort .= $sort(-1:0)->dummy(0)->enumvec->(-1:0)
[1 0 1 0 0]
Add positions:
pdl> $sort += sequence $num
[1 1 3 3 4]
Look at the result:
pdl> $num
[1 3 3 4 1]
Put everything together:
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
sub smaller_than_current {
my $num = pdl @_;
my $sort = $num($num->qsorti);
$sort .= $sort(-1:0)->dummy(0)->enumvec->(-1:0);
$sort += sequence $num;
$num;
}
See the full solution to task 1.
Task 2: Odd Matrix
Submitted by: Mohammad Sajid Anwar
You are given row and col, also a list of positions in the matrix.
Write a script to perform action on each location (0-indexed) as provided in the list and find out the total odd valued cells.
For each location (r, c), do both of the following:
a) Increment by 1 all the cells on row r.
b) Increment by 1 all the cells on column c.
Example 1
Input: $row = 2, $col = 3, @locations = ([0,1],[1,1])
Output: 6
Initial:
[ 0 0 0 ]
[ 0 0 0 ]
Apply [0,1]:
Increment row 0:
Before After
[ 0 0 0 ] [ 1 1 1 ]
[ 0 0 0 ] [ 0 0 0 ]
Increment col 1:
Before After
[ 1 1 1 ] [ 1 2 1 ]
[ 0 0 0 ] [ 0 1 0 ]
Apply [1,1]:
Increment row 1:
Before After
[ 1 2 1 ] [ 1 2 1 ]
[ 0 1 0 ] [ 1 2 1 ]
Increment col 1:
Before After
[ 1 2 1 ] [ 1 3 1 ]
[ 1 2 1 ] [ 1 3 1 ]
Final:
[ 1 3 1 ]
[ 1 3 1 ]
Example 2
Input: $row = 2, $col = 2, @locations = ([1,1],[0,0])
Output: 0
Initial:
[ 0 0 ]
[ 0 0 ]
Apply [1,1]:
Increment row 1:
Before After
[ 0 0 ] [ 0 0 ]
[ 0 0 ] [ 1 1 ]
Increment col 1:
Before After
[ 0 0 ] [ 0 1 ]
[ 1 1 ] [ 1 2 ]
Apply [0,0]:
Increment row 0:
Before After
[ 0 1 ] [ 1 2 ]
[ 1 2 ] [ 1 2 ]
Increment col 0:
Before After
[ 1 2 ] [ 2 2 ]
[ 1 2 ] [ 2 2 ]
Final:
[ 2 2 ]
[ 2 2 ]
Example 3
Input: $row = 3, $col = 3, @locations = ([0,0],[1,2],[2,1])
Output: 0
Initial:
[ 0 0 0 ]
[ 0 0 0 ]
[ 0 0 0 ]
Apply [0,0]:
Increment row 0:
Before After
[ 0 0 0 ] [ 1 1 1 ]
[ 0 0 0 ] [ 0 0 0 ]
[ 0 0 0 ] [ 0 0 0 ]
Increment col 0:
Before After
[ 1 1 1 ] [ 2 1 1 ]
[ 0 0 0 ] [ 1 0 0 ]
[ 0 0 0 ] [ 1 0 0 ]
Apply [1,2]:
Increment row 1:
Before After
[ 2 1 1 ] [ 2 1 1 ]
[ 1 0 0 ] [ 2 1 1 ]
[ 1 0 0 ] [ 1 0 0 ]
Increment col 2:
Before After
[ 2 1 1 ] [ 2 1 2 ]
[ 2 1 1 ] [ 2 1 2 ]
[ 1 0 0 ] [ 1 0 1 ]
Apply [2,1]:
Increment row 2:
Before After
[ 2 1 2 ] [ 2 1 2 ]
[ 2 1 2 ] [ 2 1 2 ]
[ 1 0 1 ] [ 2 1 2 ]
Increment col 1:
Before After
[ 2 1 2 ] [ 2 2 2 ]
[ 2 1 2 ] [ 2 2 2 ]
[ 2 1 2 ] [ 2 2 2 ]
Final:
[ 2 2 2 ]
[ 2 2 2 ]
[ 2 2 2 ]
Example 4
Input: $row = 1, $col = 5, @locations = ([0,2],[0,4])
Output: 2
Initial:
[ 0 0 0 0 0 ]
Apply [0,2]:
Increment row 0:
Before After
[ 0 0 0 0 0 ] [ 1 1 1 1 1 ]
Increment col 2:
Before After
[ 1 1 1 1 1 ] [ 1 1 2 1 1 ]
Apply [0,4]:
Increment row 0:
Before After
[ 1 1 2 1 1 ] [ 2 2 3 2 2 ]
Increment col 4:
Before After
[ 2 2 3 2 2 ] [ 2 2 3 2 3 ]
Final:
[ 2 2 3 2 3 ]
Example 5
Input: $row = 4, $col = 2, @locations = ([1,0],[3,1],[2,0],[0,1])
Output: 8
Initial:
[ 0 0 ]
[ 0 0 ]
[ 0 0 ]
[ 0 0 ]
Apply [1,0]:
Increment row 1:
Before After
[ 0 0 ] [ 0 0 ]
[ 0 0 ] [ 1 1 ]
[ 0 0 ] [ 0 0 ]
[ 0 0 ] [ 0 0 ]
Increment col 0:
Before After
[ 0 0 ] [ 1 0 ]
[ 1 1 ] [ 2 1 ]
[ 0 0 ] [ 1 0 ]
[ 0 0 ] [ 1 0 ]
Apply [3,1]:
Increment row 3:
Before After
[ 1 0 ] [ 1 0 ]
[ 2 1 ] [ 2 1 ]
[ 1 0 ] [ 1 0 ]
[ 1 0 ] [ 2 1 ]
Increment col 1:
Before After
[ 1 0 ] [ 1 1 ]
[ 2 1 ] [ 2 2 ]
[ 1 0 ] [ 1 1 ]
[ 2 1 ] [ 2 2 ]
Apply [2,0]:
Increment row 2:
Before After
[ 1 1 ] [ 1 1 ]
[ 2 2 ] [ 2 2 ]
[ 1 1 ] [ 2 2 ]
[ 2 2 ] [ 2 2 ]
Increment col 0:
Before After
[ 1 1 ] [ 2 1 ]
[ 2 2 ] [ 3 2 ]
[ 2 2 ] [ 3 2 ]
[ 2 2 ] [ 3 2 ]
Apply [0,1]:
Increment row 0:
Before After
[ 2 1 ] [ 3 2 ]
[ 3 2 ] [ 3 2 ]
[ 3 2 ] [ 3 2 ]
[ 3 2 ] [ 3 2 ]
Increment col 1:
Before After
[ 3 2 ] [ 3 3 ]
[ 3 2 ] [ 3 3 ]
[ 3 2 ] [ 3 3 ]
[ 3 2 ] [ 3 3 ]
Final:
[ 3 3 ]
[ 3 3 ]
[ 3 3 ]
[ 3 3 ]
Solution
Solving an example in the PDL shell.
Choosing one that has distinguishable dimensions and a non-uniform solution:
$row = 4, $col = 3, @locations = ([3,1],[2,1],[3,2],[0,1])
Build a zero matrix in the requested dimensions and a 2xN ndarray of locations:
pdl> do_print 1
1
pdl> $m = zeroes long, 3, 4
[
[0 0 0]
[0 0 0]
[0 0 0]
[0 0 0]
]
pdl> $loc = indx [[3,1],[2,1],[3,2],[0,1]]
[
[3 1]
[2 1]
[3 2]
[0 1]
]
Sort rows and colums:
pdl> $sort = $loc->xchg(0,1)->qsort
[
[0 2 3 3]
[1 1 1 2]
]
Run-length encode the rows and columns:
pdl> ($freq, $indx) = $sort->rle
$PDL1 =
[
[1 1 2]
[3 1 0]
]
;
$PDL2 =
[
[0 2 3]
[1 2 0]
]
;
Here we find the unique rows 0, 2, 3 with frequencies 1, 1, 2 and the unique columns 1, 2 with frequencies 3, 1.
Entries corresponding to zero frequencies have to be ignored and are set to BAD:
pdl> $freq->inplace->setvaltobad(0)
[
[ 1 1 2]
[ 3 1 BAD]
]
pdl> $indx->inplace->copybad($freq)
[
[ 0 2 3]
[ 1 2 BAD]
]
The following part is tricky and almost undocumented.
We may actually use BAD as an index in a
dice operation.
For dice this is not documented.
dice uses
dice_axis internally, where it isn’t documented neither.
Finally dice_axis uses
index1d, where BAD is allowed.
Apply all row operations in a single step by setting non-zero frequency rows to their corresponding frequency. Rows are: 0, 2, 3.
pdl> $m(,$indx(,(0))) .= $freq(,(0))->dummy(0)
[
[1 1 1]
[1 1 1]
[2 2 2]
]
pdl> $m
[
[1 1 1]
[0 0 0]
[1 1 1]
[2 2 2]
]
Apply all column operations in a single step by adding the column frequency to non-zero frequency columns. First visualize the columns to be added. Columns are: 1, 2.
pdl> $freq(,(1))->dummy(1, 4)
[
[ 3 1 BAD]
[ 3 1 BAD]
[ 3 1 BAD]
[ 3 1 BAD]
pdl> $m($indx(,(1))) += $freq(,(1))
[
[ 4 2 BAD]
[ 3 1 BAD]
[ 4 2 BAD]
[ 5 3 BAD]
]
Look at the result:
pdl> $m
[
[1 4 2]
[0 3 1]
[1 4 2]
[2 5 3]
]
Put everything together:
use strict;
use warnings;
use PDL;
use PDL::NiceSlice;
use experimental 'signatures';
sub odd_matrix ($row, $col, @loc) {
my $m = zeroes long, $col, $row;
my ($freq, $indx) = indx(@loc)->xchg(0,1)->qsort->rle;
$freq->inplace->setvaltobad(0);
$indx->inplace->copybad($freq);
$m(,$indx(,(0))) .= $freq(,(0))->dummy(0);
$m($indx(,(1))) += $freq(,(1));
$m;
}
Addendum
By spying on other solutions I realized that I hadn’t read the task carefully enough.
My solution lacked the final step: Count the odd elements.
In the example above this reads as:
pdl> sum $m % 2
6
Likewise, the return value from odd_matrix would be
sum $m % 2;
instead of just $m.
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.