Inputs:
The program or function should take 2 vector-like (e.g. a list of numbers) O and V of the same number of dimensions, and a number T (all floating-point numbers or similar)
Constraints:
- T >= 0
- All elements of Vector O will be in the range
[0,1)
Output:
The program or function should output the N dimensional cutting sequence given an infinite ray whose origin is the first vector, and whose velocity is the second vector. The sequence should include every cut the ray makes on the time interval (0, T]
, appearing in order of when they occur. Details on the format and specification of the sequence are explained below
Cutting sequence
In a N dimensional Cartesian coordinate system, there exist axis-aligned unit coordinate facets, e.g. the integer points on a 1 dimensional number line, the unit grid lines on a 2D grid, planes like x = 1
, z =- 10
or y = 0
in 3D space. As this problem is generalized to N dimensions, from here forward we will no longer use lettered axes, but instead number the axes starting with 0. Every facet can be defined by some equation like Axis j = k
, where j
and k
are integers, and j
is the characteristic axis of the facet.
As the ray extends through N dimensional space, it intersects these facets. This is called a cut. Each of these cuts is described by 2 things.
- The characteristic axis of the facet.
- The direction of the cut, i.e. whether the ray extending positively or negatively with respect to the characteristic axis.
Hence each cut shall be outputted in the sequence as a string of a plus or minus sign corresponding to the direction of the cut, then the number (base 10) of the characteristic axis of the cut facet.
The sequence will be outputted as a continuous string of these cuts, e.g. +0+1+0+0+1-2+0
Examples
This image from the Wikipedia page for Cutting Sequence shows a 2D example. This is equivalent to O=[0,0] V=[1,0.618] T = 6.5
, where the output is +0+1+0+0+1+0+1+0+0+1
For 1 dimension, all non-empty cutting sequences will look like +0+0+0...
or -0-0-0...
More examples / test cases to be added
Special cases
- If two or more cuts occur at exactly the same time (to the precision of your numeric type), they must appear in the sequence in order of their axis from least to greatest
- Your program should be accurate for extreme input values
- e.g. for
V=[1, -0.0009765625]
, the sequence will have a repeating pattern of+0
1024 times and then a-1
. This pattern should hold exactly for arbitrarily large values of T
- e.g. for
- Your program must always output a sequence, e.g.
- If Vector V has a length 0, the program should not loop indefinitely, but output an empty sequence.
- If the inputs are of 0 dimensions, the program should output an empty sequence
-0.0009765625
is likely to work in most languages as it is a power of \$2\$. But arbitrary floating point values will inexorably lead to floating point accuracy errors, unless the challenge is limited to languages that support arbitrary precision. \$\endgroup\$