Cutting Sequence for N dimensions

Question

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

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

Answer 1

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