| 12 January 2024 | Challenge 251 |
Lucky Cats
Task 1: Concatenation Value
Submitted by: Mohammad S Anwar
You are given an array of integers, @ints.
Write a script to find the concatenation value of the given array.
The concatenation of two numbers is the number formed by concatenating their numerals.
For example, the concatenation of 10, 21 is 1021.
The concatenation value of @ints is initially equal to 0.
Perform this operation until @ints becomes empty:
If there exists more than one number in @ints, pick the first element
and last element in @ints respectively and add the value of their
concatenation to the concatenation value of @ints, then delete the
first and last element from @ints.
If one element exists, add its value to the concatenation value of
@ints, then delete it.
Example 1
Input: @ints = (6, 12, 25, 1)
Output: 1286
1st operation: concatenation of 6 and 1 is 61
2nd operation: concaternation of 12 and 25 is 1225
Concatenation Value => 61 + 1225 => 1286
Example 2
Input: @ints = (10, 7, 31, 5, 2, 2)
Output: 489
1st operation: concatenation of 10 and 2 is 102
2nd operation: concatenation of 7 and 2 is 72
3rd operation: concatenation of 31 and 5 is 315
Concatenation Value => 102 + 72 + 315 => 48
Example 3
Input: @ints = (1, 2, 10)
Output: 112
1st operation: concatenation of 1 and 10 is 110
2nd operation: only element left is 2
Concatenation Value => 110 + 2 => 112
Solution
shift and pop return and remove the first resp. last element of an array.
Concatenating these elements gives the requested part of the value.
If there is only one element left in the list, it will be picked by the first operation.
The second operations yields undef in this case.
Substituting an undefined value from the second operation with the empty string thus covers this edge case.
Though the task does not restrict the given array to have non-negative values only, this should be required and leads to the following implementation:
sub concat_val {
my $val = 0;
while (@_) {
$val += shift() . (pop() // '');
}
$val;
}
See the full solution.
Task 2: Lucky Numbers
Submitted by: Mohammad S Anwar
You are given a m x n matrix of distinct numbers.
Write a script to return the lucky number, if there is one, or -1 if not.
A lucky number is an element of the matrix such that it is
the minimum element in its row and maximum in its column.
Example 1
Input: $matrix = [ [ 3, 7, 8],
[ 9, 11, 13],
[15, 16, 17] ];
Output: 15
15 is the only lucky number since it is the minimum in its row
and the maximum in its column.
Example 2
Input: $matrix = [ [ 1, 10, 4, 2],
[ 9, 3, 8, 7],
[15, 16, 17, 12] ];
Output: 12
Example 3
Input: $matrix = [ [7 ,8],
[1 ,2] ];
Output: 7
Preliminary Considerations
Note: This paragraph was rewritten as an excercise in using LaTeX.
We’ll ignore the precondition for the matrix elements to be distinct for a moment.
Let \(\check{M}_i^{(r)} := \min_j m_{ij}\) be the minimum over row \(i\) and
\(\hat{M}_k^{(c)} := \max_j m_{jk}\) the maximum over column \(k\).
For \(m_{ik}\) we can see that
\(m_{ik} \ge \check{M}_i^{(r)}\) and
\(m_{ik} \le \hat{M}_k^{(c)}\), leading to
\(\check{M}_i^{(r)} \le \hat{M}_k^{(c)}\) for all \(i, k\).
If \(\max \check{M}_i^{(r)} \lt \min \hat{M}_k^{(c)}\), then there is obviously no lucky number within the matrix as there is no element that is the minimum value in its row and the maximum value in its column at the same time.
Otherwise we have
\(m^* := \max \check{M}_i^{(r)} = \min \hat{M}_k^{(c)}k\).
Select \(i^*, k^*\) such that
\(\check{M}_{i^*}^{(r)} = \hat{M}_{k^*}^{(c)} = m^*\), i.e. a row and a colum containing the common minimum resp. maximum value.
Looking at \(m_{i^*k^*}\) the above inequalities lead to:
\(m_{i^*k^*} \ge m^*\) and
\(m_{i^*k^*} \le m^*\), leading to
\(m_{i^*k^*} = m^*\).
Therefore the element \(m_{i^*k^*}\) is a lucky number.
In the preceding considerations we didn’t make use of the uniqueness precondition. We may drop the precondition, but the question remains: What it is needed for at all?
I can only speculate about this. The described property of being “lucky” is a property of a matrix element. However, we are asked to find a lucky number, i.e. a matrix value. With non-unique elements we are able to construct a matrix that contains a “lucky” element but has the same value at other positions that are not “lucky”. In this case we cannot really state that this value is a lucky number. See the full solution for an example.
With unique values there can be only one lucky element. As each value corresponds unambiguously to one element, there is a unique lucky number in this case (if one exists at all).
Solution
Once again, this task can easily be solved using PDL.
We create a vector holding the minima of each row and a vector holding the maxima of each column.
If the maximum over the first vector equals the minimum over the second vector, this is the unique value of all lucky elements in the matrix.
use PDL;
sub lucky_number {
my $m = pdl @_;
my $minmax = $m->xchg(0, 1)->maxover->minimum;
$minmax == $m->minover->maximum ? $minmax : -1;
}
See the full solution.