4
1
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
1Your program should be accurate for extreme input values : what does this concretely mean? Your example with
-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. – Arnauld – 2020-01-17T12:37:01.777@Arnauld due to the fact that the problem is concerned with a regular grid of n-dimensional hypercubes, outputs will be theoretically identical for starting conditions that have the some offset with respect to the hypercube that contains them, hence the 2nd input constraint. This also means that with any valid starting condition, you can always re-base your coordinates to equivalent small values that give you a comfortable amount of precision. If you don't do that, your program is liable to become increasingly inaccurate as T gets larger – Hymns For Disco – 2020-01-17T13:02:29.383
If I understand your comment correctly, the values we calculate will have a somewhat similar precision as the input precision (so
1e-10
/0.0000000001
in case of-0.0009765625
). But even if this indeed is true, I think @Arnauld is also asking whether the precision of this input can have a larger precision than the default of most languages (i.e. Java has a double/float precision of 16, so a value like0.123456789123456789123456789
would actually be0.12345678912345678
). Java also hasBigDecimal
as arbitrary alternative, but most languages won't be able to exceed a precision of 16. – Kevin Cruijssen – 2020-01-17T14:08:26.233So can the precision of the input-values be arbitrary large as well? – Kevin Cruijssen – 2020-01-17T14:09:10.703
2Also, could you perhaps add some test cases / examples for larger dimensions (like $\geq4$)? – Kevin Cruijssen – 2020-01-17T14:15:21.427
1@KevinCruijssen your program can accept any input type you like, provided its a vector-like type of float-like numbers. The point about the inputs is that having an extreme large or small input (again, still within your chosen data-type), shouldn't affect the accuracy of your output. It is accepted that most numeric types are not arbitrarily precise, and cannot be 100% accurate for every input case, but the program should be theoretically correct if it were run with arbitrary precision, and giving extreme inputs shouldn't make it less accurate – Hymns For Disco – 2020-01-17T14:33:18.663
@HymnsForDisco Thanks, that clarifies it. – Kevin Cruijssen – 2020-01-17T14:41:21.490
An example of an offending algorithm would be one that successively adds the ray velocity to its origin (assuming floating point). Obviously at some point as ray position becomes large, the lesser digits of the mantissa of the velocity will no longer have an effect in a floating point add of the two. In this case, each axis will have a "stopping point", where eventually the relatively small value being added no longer results in the position float getting larger. – Hymns For Disco – 2020-01-17T14:41:45.920
1Related challenge, for n=2 – xnor – 2020-01-18T16:02:37.460
Does this mean I win? XD – RGS – 2020-01-27T08:55:18.017