| 08 August 2025 | Challenge 333 |
Shift and Duplicate
Task 1: Straight Line
Submitted by: Mohammad Sajid Anwar
You are given a list of co-ordinates.
Write a script to find out if the given points make a straight line.
Example 1
Input: @list = ([2, 1], [2, 3], [2, 5])
Output: true
Example 2
Input: @list = ([1, 4], [3, 4], [10, 4])
Output: true
Example 3
Input: @list = ([0, 0], [1, 1], [2, 3])
Output: false
Example 4
Input: @list = ([1, 1], [1, 1], [1, 1])
Output: true
Example 5
Input: @list = ([1000000, 1000000], [2000000, 2000000], [3000000, 3000000])
Output: true
Solution
The task can easily be extended to any number of points in \(n\) dimensions.
There are several ways to specify a straight line in an \(n\)-dimensional space. One of them that is not too obvious comes handy in this task:
We regard the \(n\)-dimensional space as a hyperplane
\(H\) within an \(n+1\)-dimensional vector space \(V\), shifted from zero in the \((n+1)^{th}\)-dimension by a nonzero constant.
Choosing a shift of 1.
Any two linear independent vectors \(u,v \in V\) span a 2-dimensional subspace \(A(u,v)\) in \(V\).
When \(u\) and \(v\) are not parallel to \(H\), the intersection \(A(u,v) \cap V\) represents a straight line in \(H\).
Given a set of \(k\) \(n\)-dimensional points \(p^i =(p_1^i,\ldots,p_n^i)\) for \(1 \le i \le k\), we regard these as vectors in \(H\) via \(p^i \mapsto q^i = (p_1^i,\ldots,p_n^i, 1)\).
From the above consideration, these vectors are located on a straight line if and only if there are at most two linear independent vectors in \(q^i\). The case of only a single linear independent vector within \(q^i\) is pathological: all \(q^i\) are equal then.
This is equivalent to a maximum rank
of 2 for the matrix
Example:
Looking at a 2-d plane, that we regard as the \(z = 1\) plane in 3-d space.
Choosing two vectors \(u = (6, 0, 2)\) and \(v = (0, 18, 2)\) and build the linear combination
\(w = 2u + v = (12, 0, 4) + (0, 18, 2) = (12, 18, 6)\).
Scaling these vectors to \(u^*, v^*, w^* \in H\):
\(u^* = (3, 0, 1), v^* = (0, 9, 1), w^* = (2, 3, 1)\).
\(u^*, v^* \text{ and } w^*\) are on a straight line and correspond to the 2-d points
\((3, 0), (0, 9) \text{ and } (2, 3)\).
Using PDL’s
mrank function to calculate the matrix’ rank.
use strict;
use warnings;
use PDL;
use PDL::LinearAlgebra;
sub straight_line {
mrank(pdl(@_)->append(1)) <= 2;
}
See the full solution to task 1.
Task 2: Duplicate Zeros
Submitted by: Mohammad Sajid Anwar
You are given an array of integers.
Write a script to duplicate each occurrence of zero, shifting the remaining elements to the right. The elements beyond the length of the original array are not written.
Example 1
Input: @ints = (1, 0, 2, 3, 0, 4, 5, 0)
Output: (1, 0, 0, 2, 3, 0, 0, 4)
Each zero is duplicated.
Elements beyond the original length (like 5 and last 0) are discarded.
Example 2
Input: @ints = (1, 2, 3)
Output: (1, 2, 3)
No zeros exist, so the array remains unchanged.
Example 3
Input: @ints = (1, 2, 3, 0)
Output: (1, 2, 3, 0)
Example 4
Input: @ints = (0, 0, 1, 2)
Output: (0, 0, 0, 0)
Example 5
Input: @ints = (1, 2, 0, 3, 4)
Output: (1, 2, 0, 0, 3)
Solution
Adding 1 to the logical negation of zero and nonzero provides a suitable repetition factor (2 resp. 1) for each value.
Finally slice the result.
use strict;
use warnings;
sub duplicate_zeros {
(map {($_) x (!$_ + 1)} @_)[0 .. $#_];
}
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.