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)
- T >= 0
- All elements of Vector O will be in the range
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
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
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.
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
For 1 dimension, all non-empty cutting sequences will look like
More examples / test cases to be added
- 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
+01024 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