| 10 July 2026 | Challenge 381 |
All The Same
Task 1: Same Row Column
Submitted by: Mohammad Sajid Anwar
You are given a n x n matrix containing integers from 1 to n.
Write a script to find if every row and every column contains all the integers from 1 to n.
Example 1
Input: @matrix = ([1, 2, 3, 4],
[2, 3, 4, 1],
[3, 4, 1, 2],
[4, 1, 2, 3],)
Output: true
Example 2
Input: @matrix = ([1])
Output: true
Example 3
Input: @matrix = ([1, 2, 5],
[5, 1, 2],
[2, 5, 1],)
Output: false
Elements are out of range 1..3.
Example 4
Input: @matrix = ([1, 2, 3],
[1, 2, 3],
[1, 2, 3],)
Output: false
Example 5
Input: @matrix = ([1, 2, 3],
[3, 1, 2],
[3, 2, 1],)
Output: false
Solution
Starting the solution with a slightly different question:
Given an m x n matrix \(X = (x_{ij})\) and an p-sized vector \(a = (a^k)\):
Check if all rows of \(X\) contain all elements of \(a\).
With a Boolean hyper-matrix \(E = (e_{ij}^k)\) defined as
\[e_{ij}^k = \begin{cases} 1& \text{ if } x_{ij} = a^k\\ 0& \text{ otherwise} \end{cases}\]the above condition can be written as
\[\bigwedge_{i=1}^m\bigwedge_{k=1}^p\bigvee_{j=1}^n e_{ij}^k\]Such an expression can easily and efficiently be evaluated in languages supporting vectorized operations, such as PDL or J.
For this task, with the given square matrix \(M\), we want the numbers 1 ... N to be contained in all rows and columns.
To map this onto the above condition, we take
as \(M\) appended with its own transpose and
\[a = (1,\ldots,n)\]Perl
Append the transpose of the matrix to itself, compare it to a suitable dimensioned sequence of 1 ... n and perform the vectorized computation of the above formula.
use strict;
use warnings;
use PDL;
sub same_row_col {
my $m = long @_;
my $mat = $m->glue(1, $m->transpose);
my $num = (1 + sequence long, $m->dim(0))->dummy(0)->dummy(0);
($mat == $num)->reorder(0, 2, 1)->orover->and;
}
See the full solution to task 1.
J
In J its almost the same.
The verb e."1 does most of the job: check if each item of the left argument is contained in rows of the right argument.
Simpler than ($mat == $num)->reorder(0, 2, 1)->orover, which does basically the same.
same_row_col =: _(adverb define)
NB. append transposed matrix to itself
append_tr =. ([ , |:)
NB. test if items of left arg are
NB. contained in rows of right arg
in_row =. e."1
NB. numbers 1 ... n
nums =. >:@i.@#
NB. flatten to 1-d
ravel =. ,
NB. logical AND over all items
all =. *./
NB. append transposed matrix, test sequence
NB. 1 ... n in each row, flatten to 1-d and
NB. test if all items are one
([: all [: ravel nums in_row append_tr) f. : [:
)
The resulting verb and example 1:
same_row_col
[: *./ [: , >:@i.@# e."1 [ , |:
]ex1 =: 4 4 $ 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
same_row_col ex1
1
See the full solution.
Task 2: Smaller Greater Element
Submitted by: Mohammad Sajid Anwar
You are given an array of integers.
Write a script to find the number of elements that have both a strictly smaller and greater element in the given array.
Example 1
Input: @int = (2,4)
Output: 0
Not enough elements in the array.
Example 2
Input: @int = (1, 1, 1, 1)
Output: 0
Example 3
Input: @int = (1, 1, 4, 8, 12, 12)
Output: 2
The elements are 4 and 8.
Example 4
Input: @int = (3, 6, 6, 9)
Output: 2
Both instances of 6.
Example 5
Input: @int = (0, -5, 10, -2, 4)
Output: 3
The elements are 0, -2, and 4.
Solution
Most importantly, the given array should not be sorted as this would lead to a complexity of \(\mathcal{O}(n \log n)\), while the task can be solved in linear time.
Perl
Find the minimum and maximum values and identify all elements distinct from these. In scalar context this provides their count.
use strict;
use warnings;
use List::MoreUtils 'minmax';
sub smaller_greater {
my ($min, $max) = minmax @_;
grep $_ != $min && $_ != $max, @_;
}
See the full solution to task 2.
J
In J it is almost the same, though only the count is provided.
smaller_greater =: _(adverb define)
min =. <./
max =. >./
NB. test if elements of left arg
NB. are elements of right arg
in =. e.
not =. -.
sum =. +/
NB. find items that are neither min
NB. nor max and count these
([: sum [: not ] in min , max) f. : [:
)
The resulting verb and example 5:
smaller_greater
([: +/ [: -. ] e. <./ , >./) :[:
smaller_greater 0 _5 10 _2 4
3
See the full solution.