4
\$\begingroup\$

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.

  1. The characteristic axis of the facet.
  2. 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

2D cutting sequence

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
  • 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
\$\endgroup\$
  • 1
    \$\begingroup\$ Your 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. \$\endgroup\$ – Arnauld Jan 17 at 12:37
  • \$\begingroup\$ @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 \$\endgroup\$ – Hymns For Disco Jan 17 at 13:02
  • 2
    \$\begingroup\$ Also, could you perhaps add some test cases / examples for larger dimensions (like \$\geq4\$)? \$\endgroup\$ – Kevin Cruijssen Jan 17 at 14:15
  • 1
    \$\begingroup\$ @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 \$\endgroup\$ – Hymns For Disco Jan 17 at 14:33
  • 1
    \$\begingroup\$ Related challenge, for n=2 \$\endgroup\$ – xnor Jan 18 at 16:02
2
\$\begingroup\$

Python, 226 bytes

Assumes the lists O and V are defined, as well as the time T, either an int or a float.

Try it online

s=lambda x:int(x/abs(x));r=range;f=lambda O,V,T:"".join(map(lambda t:t[1],sorted(sum([[((i-o)/v,"%+d"%(s(v)*c))for i in r((v>0)-(v<0)*(o==0),int((o+T*v)//1)+(v>0),s(v))]for c,o,v in zip(r(len(O)),O,V)],[]),key=lambda t:t[0])))

The idea of the code is simple, first we loop over all coordinates, and for each coordinate we:

  1. find where the first cut is, depending on the sign of v and the origin being 0 or not, the first cut might be at -1, 0 or 1;
  2. find how far the ray goes in the time given with o + v*T (which then needs proper rounding to be an argument for the range function);
  3. find the time t for which each successive cut occurs, by solving o + v*t = i iff t = (i - o)/v, for the successive integer values of i (this amounts to finding the time for which the ray crosses the hyperplane x_c = i);
  4. sort everything by the time and drop the time, as it was just an auxiliary thing.

The code un-golfed:

# sign function, returns 1 for positive numbers and -1 for negative numbers
sgn = lambda x: int(x/abs(x))
l = []
# c is the coordinate we are in,
# o is the origin in this coordinate and v the velocity
for (c, o, v) in zip(range(len(O)), O, V):
    # find all the cuts for this coordinate
    sub_l = []
    # this is how far the ray goes, rounded to integers, in T seconds
    stop_at = int((o + T*v)//1) # if this is negative, //1 pushes the result away from 0
    if v > 0:
        stop_at += 1
    # this is where the first cut occurs (depends on o == 0 and the sign of v)
    if v > 0:
        start_at = 1
    elif o > 0:
        start_at = 0
    else:
        start_at = -1
    for i in range(start_at, stop_at, sgn(v)):
        # this is the time at which the ray cuts the x_c = i hyperplane
        t = (i - o)/v
        # append the time of the cut and the signed axis
        sub_l.append((t, "%+d"%(sgn(v)*c)))
    l.append(sub_l)
print(l)
# flatten list
l = sum(l, [])
# order list by the time at which the cut occurs
l.sort(key = lambda tup: tup[0])
# remove the times, keep the coordinates
l = map(lambda tup: tup[1], l)
# join and print
print("".join(l))

Then we just need to note a couple of things, like I can save some bytes if I redefine r = range or if I assign start_at = (v>0)-(v<0)*(o==0) and stop_at = int((o+T*v)//1)+(v>0).

I don't feel this is properly golfed, I just wrote a program that works and then crammed everything together. Please feel free to give me some feedback.

I used a flatten from https://stackoverflow.com/a/952946/2828287 and getting the sign of a number from https://stackoverflow.com/a/2763445/2828287

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ It will be interesting to see an explanation of this. One note though, I notice it fails to account for cuts in the negative direction (try a minus sign on one of the numbers in V) \$\endgroup\$ – Hymns For Disco Jan 23 at 2:06
  • 1
    \$\begingroup\$ @HymnsForDisco the code should work now with negative velocities. The TIO link includes your example but with V = [1, -0.618]. \$\endgroup\$ – RGS Jan 23 at 15:14
  • 2
    \$\begingroup\$ The standard on this site is that submissions should input either by function parameters or STDIN, and output by function return or STDOUT. They should either be programs or functions which perform the task - your code would be termed a snippet. See this meta post for more details. \$\endgroup\$ – Stephen Jan 23 at 15:34
  • \$\begingroup\$ @Stephen thank you for your comment. My edit should be acceptable now? I wrapped the "main code" around a lambda function. The TIO link has been updated. \$\endgroup\$ – RGS Jan 23 at 15:52
  • 1
    \$\begingroup\$ @RGS yes, that's right \$\endgroup\$ – Stephen Jan 23 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.