Hyperspace Racing

[Molly Mae]

I hope I'm not stepping on any toes here, but I had a lot of fun with Super's and Ed's Racing puzzles. Next comes Hyperspace Racing. =P

This is a variant on Superprismatic's challenge and Captain Ed's variation. The movement rules are the same, but include a 3rd dimension. In Super's challenge, you had to land on a series of marks in sequence; in Capt Ed's, the goal was to round a mark; in this challenge, you have to navigate through four spherical rings of radius 1 in any direction and in any order.

Goal: Move your spaceship around the course, navigate through all four spheres, and return to base (origin) in the minimum number of moves.

Movement: Your boat begins at the origin (0,0,0), with a velocity vector of (0,0,0).

Before each move, you specify an acceleration vector (a,b,c), where a, b, and c can independently take on integer values from the set (-1, 0, 1).

The move consists of: (a) update the velocity by adding the acceleration, and then (b) move the spaceship by the velocity vector.

Example: if the prior location was (10,11,12), and the prior velocity was (2,5,6), and you choose the acceleration vector (1,-1,0),

the new velocity becomes (3,4,6) and the new location becomes (13,15,18).

Course constraints: The course consists of an unordered series of four rings. A ring is a sphere of radius 1 with centers at the points provided below. Crossing through a sphere means passing through the center or any of the 6 adjacent points. Assume the course is "infinite", that is, from (-100,-100,-100) to (100,100,100)

Your path through the course must contain a move through each of the four rings in any order and in any direction.

The first ring is (-22,18,19)

The second sphere is (12,-12,26)

The third sphere is (38,-13, 0)

The fourth sphere is (-9,30,-18)

Return to base (origin)

[CaptainEd]

Lovely! "Passing through" a sphere means which?:

(a) a move ends on a sphere center or one of its 6 neighbors

(b) at least one of those 7 points lies on the line segment of a move

© something more complicated about the line and the volume surrounding the sphere center...

(d) other

Also, it appears that the origin itself is the 5th mark, and presumably is to be passed through in the same way?

What fun!

[Molly Mae]

Lovely! "Passing through" a sphere means which?:

(a) a move ends on a sphere center or one of its 6 neighbors

(b) at least one of those 7 points lies on the line segment of a move

© something more complicated about the line and the volume surrounding the sphere center...

(d) other

Also, it appears that the origin itself is the 5th mark, and presumably is to be passed through in the same way?

What fun!

For simplicity, the line segment must pass through the minimum and maximum of each axis (so I guess it's actually a cube and not a sphere). For instance, if the center of a ring is (1,5,9), the line must pass within 1 of each axis. Examples: (2,6,8), (0,6,10), and (1,4,9) would pass through that goal. (1,5,7) would not.

As for the origin: it must be your last stop. Starting there doesn't count. =P I guess I forgot to mention that the teleportation device is located at origin--it puts you there and takes you out when you're done.

[CaptainEd]

First off, I hit the sphere centers exactly, and I hit them at the end of the move, and I have no idea what the optimal sequence of spheres is.

0 0 0

-1 1 1

-3 3 2

-6 6 4

-10 9 7

-15 13 11

-19 16 15

-22 18 19 <==

-24 21 22

-25 25 24

-25 28 25

-24 30 25

-22 31 24

-19 32 23

-15 32 21

-12 31 19

-9 30 18 <==

-5 28 17

-1 25 16

2 21 15

4 17 15

5 13 16

5 9 18

6 5 21

6 1 24

7 -3 26

9 -7 27

10 -10 27

12 -12 26 <==

15 -13 24

19 -13 21

24 -13 17

29 -13 12

33 -13 8

36 -13 4

38 -13 0 <==

39 -12 -3

39 -10 -5

38 -7 -6

36 -5 -6

33 -4 -5

29 -3 -3

24 -2 -2

18 -1 -1

11 0 0

5 0 0

0 0 0

[Molly Mae]

First off, I hit the sphere centers exactly, and I hit them at the end of the move, and I have no idea what the optimal sequence of spheres is. 0 0 0 -1 1 1 -3 3 2 -6 6 4 -10 9 7 -15 13 11 -19 16 15 -22 18 19 <== -24 21 22 -25 25 24 -25 28 25 -24 30 25 -22 31 24 -19 32 23 -15 32 21 -12 31 19 -9 30 18 <== -5 28 17 -1 25 16 2 21 15 4 17 15 5 13 16 5 9 18 6 5 21 6 1 24 7 -3 26 9 -7 27 10 -10 27 12 -12 26 <== 15 -13 24 19 -13 21 24 -13 17 29 -13 12 33 -13 8 36 -13 4 38 -13 0 <== 39 -12 -3 39 -10 -5 38 -7 -6 36 -5 -6 33 -4 -5 29 -3 -3 24 -2 -2 18 -1 -1 11 0 0 5 0 0 0 0 0

I had 46, but went in sphere order 2143. My return to origin was much longer than I like.

0,0,0 | 1,-1,1 (going for 2)

1,-1,1 | 2,-2,2

3,-3,3 | 3,-3,3

6,-6,6 | 2,-2, 4

8,-8,10 | 2,-2,5

10,-10,15 | 1,-1,6

11,-11,21 | 0,0,5

11,-11,25 | -1,1,4 (! Going for 1)

10,-10,29 | -2,2,3

8,-8,32 | -3,3,2

5,-5,34 | -4,4,1

1,-1,33 | -5,5,0

-4,4,33 | -5,5,-1

-9,9,32 | -5,4,-2

-14,13,30 | -4,3,-3

-18,16,27 | -3,2,-4

-21,18,23 | -2,1,-5

-23,19,18 | -1,2,-6 (! going for 4)

-24,21,12 | 0,3,-7

-24,24,5 | 1,2,-6

-23,26,-1 | 2,2,-5

-21,28,-6 | 3,2,-4

-18,30,-10 | 4,1,-4

-14,30,-14 | 5,0,-3

-9,29,-17 | 4,-1,-2 (! going for 3)

-5,28,-19 | 5,-2,-1

0,26,-20 | 6,-3,0

6,23,-20 | 7,-4,1

13,19,-19 | 7,-5,2

20,14,-17 | 6,-6,3

26,8,-14 | 5,-7,4

31,1,-10 | 4,-7,5

35,-6,-5 | 3,-6,4

38,-12,-1 | 2,-5,3 (! going for origin)

40,-17,2 | 1,-4,2

41,-21,4 | 0,-3,1

41,-24,5 | -1,-2,0

40,-26,5 | -2,-1,-1

38,-27,4 | -3,0,-2

35,-27,2 | -4,1,-1

31,-26,1 | -5,2,-1

26,-24,0 | -6,3,0

20,-21,0 | -5,4,0

15,-17,0 | -5,5,0

10,-12,0 | -5,6,0

5,-6,0 | -5,6,0

0,0,0 (! origin)

[Smith]

I'd like some clarification, please. In the OP, it states "Before each move, you specify an acceleration vector (a,b,c), where a, b, and c can independently take on integer values from the set (-1, 0, 1)." But it seems to me that both Captain Ed and Molly Mae chose some vector accelerations way beyond these limits. Did I misunderstand?

[curr3nt]

The vectors they listed were the position (and velocity for Molly) not the acceleration.

[Smith]

"I see", said the moderately stupid Smith. Thanks, curr3nt (do you realize how desperately difficult it is to force my finger up to the "3" when I want to type an "e" in your name?).

[CaptainEd]

Thanks to Smith's reasonable question, I have included ddx, dx and x, as well as column headings. Hope this helps:

mv# ddx ddy ddz dx dy dz x y z

0 -1 1 1 0 0 0 0 0 0

1 -1 1 1 -1 1 1 -1 1 1

2 -1 1 0 -2 2 1 -3 3 2

3 -1 1 1 -3 3 2 -6 6 4

4 -1 0 1 -4 3 3 -10 9 7

5 -1 1 1 -5 4 4 -15 13 11

6 1 -1 0 -4 3 4 -19 16 15

7 1 -1 0 -3 2 4 -22 18 19

8 1 1 -1 -2 3 3 -24 21 22

9 1 1 -1 -1 4 2 -25 25 24

10 1 -1 -1 0 3 1 -25 28 25

11 1 -1 -1 1 2 0 -24 30 25

12 1 -1 -1 2 1 -1 -22 31 24

13 1 0 0 3 1 -1 -19 32 23

14 1 -1 -1 4 0 -2 -15 32 21

15 -1 -1 0 3 -1 -2 -12 31 19

16 0 0 1 3 -1 -1 -9 30 18

17 1 -1 1 4 -2 0 -5 28 18

18 1 -1 1 5 -3 1 0 25 19

19 -1 -1 1 4 -4 2 4 21 21

20 -1 -1 1 3 -5 3 7 16 24

21 -1 -1 -1 2 -6 2 9 10 26

22 -1 0 -1 1 -6 1 10 4 27

23 -1 0 0 0 -6 1 10 -2 28

24 1 1 -1 1 -5 0 11 -7 28

25 1 1 -1 2 -4 -1 13 -11 27

26 1 1 -1 3 -3 -2 16 -14 25

27 1 1 -1 4 -2 -3 20 -16 22

28 0 1 -1 4 -1 -4 24 -17 18

29 0 1 -1 4 0 -5 28 -17 13

30 1 1 -1 5 1 -6 33 -16 7

31 -1 1 -1 4 2 -7 37 -14 0

32 -1 0 1 3 2 -6 40 -12 -6

33 -1 0 1 2 2 -5 42 -10 -11

34 -1 0 1 1 2 -4 43 -8 -15

35 -1 0 1 0 2 -3 43 -6 -18

36 -1 0 1 -1 2 -2 42 -4 -20

37 -1 -1 1 -2 1 -1 40 -3 -21

38 -1 1 1 -3 2 0 37 -1 -21

39 -1 -1 1 -4 1 1 33 0 -20

40 -1 -1 1 -5 0 2 28 0 -18

41 -1 0 1 -6 0 3 22 0 -15

42 -1 0 1 -7 0 4 15 0 -11

43 -1 0 1 -8 0 5 7 0 -6

44 1 0 1 -7 0 6 0 0 0

Sorry about the formatting--I'm failing the editor intelligence test--I have made this be Courier, and manually formatted it with spaces so that everything will align in accurate columns. Unfortunately, you don't get to see that. Sorry...

Edited January 16, 2012 by CaptainEd

[CaptainEd]

It still does not exploit the possibility of a line segment passing through a target, which I'd think would allow more flexibility and a shorter path.

mv#

ddx

ddy

ddz

dx

dy

dz

x

y

z

0

0

0

0

0

0

1

1

-1

0

1

-1

0

1

-1

0

2

1

-1

0

2

-2

0

3

-3

0

3

1

-1

0

3

-3

0

6

-6

0

4

1

0

0

4

-3

0

10

-9

0

5

1

1

0

5

-2

0

15

-11

0

6

1

1

0

6

-1

0

21

-12

0

7

-1

0

0

5

-1

0

26

-13

0

8

-1

1

0

4

0

0

30

-13

0

9

-1

0

0

3

0

0

33

-13

0

10

0

0

-1

3

0

-1

36

-13

-1

11

-1

0

1

2

0

0

38

-13

-1

12

-1

0

1

1

0

1

39

-13

0

13

-1

-1

1

0

-1

2

39

-14

2

14

-1

-1

1

-1

-2

3

38

-16

5

15

-1

0

1

-2

-2

4

36

-18

9

16

-1

1

1

-3

-1

5

33

-19

14

17

-1

1

-1

-4

0

4

29

-19

18

18

-1

1

-1

-5

1

3

24

-18

21

19

-1

1

0

-6

2

3

18

-16

24

20

-1

1

-1

-7

3

2

11

-13

26

21

-1

0

-1

-8

3

1

3

-10

27

22

1

1

-1

-7

4

0

-4

-6

27

23

1

1

-1

-6

5

-1

-10

-1

26

24

1

1

-1

-5

6

-2

-15

5

24

25

1

1

-1

-4

7

-3

-19

12

21

26

1

-1

0

-3

6

-3

-22

18

18

27

1

-1

-1

-2

5

-4

-24

23

14

28

1

-1

-1

-1

4

-5

-25

27

9

29

1

-1

-1

0

3

-6

-25

30

3

30

1

-1

0

1

2

-6

-24

32

-3

31

1

-1

1

2

1

-5

-22

33

-8

32

1

-1

1

3

0

-4

-19

33

-12

33

1

-1

1

4

-1

-3

-15

32

-15

34

1

-1

1

5

-2

-2

-10

30

-17

35

-1

-1

1

4

-3

-1

-6

27

-18

36

-1

-1

1

3

-4

0

-3

23

-18

37

-1

-1

1

2

-5

1

-1

18

-17

38

-1

1

1

1

-4

2

0

14

-15

39

-1

0

1

0

-4

3

0

10

-12

40

0

0

0

0

-4

3

0

6

-9

41

0

1

1

0

-3

4

0

3

-5

42

0

0

1

0

-3

5

0

0

0

[CaptainEd]

mv# | ddx ddy ddz | dx dy dz | x y z

0 | 0 0 0 | 0 0 0 | 0 0 0

1 | 1 -1 0 | 1 -1 0 | 1 -1 0

2 | 1 -1 0 | 2 -2 0 | 3 -3 0

3 | 1 -1 0 | 3 -3 0 | 6 -6 0

4 | 1 0 0 | 4 -3 0 | 10 -9 0

5 | 1 1 0 | 5 -2 0 | 15 -11 0

6 | 1 1 0 | 6 -1 0 | 21 -12 0

7 | -1 0 0 | 5 -1 0 | 26 -13 0

8 | -1 1 0 | 4 0 0 | 30 -13 0

9 | -1 0 0 | 3 0 0 | 33 -13 0

10 | 0 0 -1 | 3 0 -1 | 36 -13 -1

11 | -1 0 1 | 2 0 0 | 38 -13 -1

12 | -1 0 1 | 1 0 1 | 39 -13 0

13 | -1 -1 1 | 0 -1 2 | 39 -14 2

14 | -1 -1 1 | -1 -2 3 | 38 -16 5

15 | -1 0 1 | -2 -2 4 | 36 -18 9

16 | -1 1 1 | -3 -1 5 | 33 -19 14

17 | -1 1 -1 | -4 0 4 | 29 -19 18

18 | -1 1 -1 | -5 1 3 | 24 -18 21

19 | -1 1 0 | -6 2 3 | 18 -16 24

20 | -1 1 -1 | -7 3 2 | 11 -13 26

21 | -1 0 -1 | -8 3 1 | 3 -10 27

22 | 1 1 -1 | -7 4 0 | -4 -6 27

23 | 1 1 -1 | -6 5 -1 | -10 -1 26

24 | 1 1 -1 | -5 6 -2 | -15 5 24

25 | 1 1 -1 | -4 7 -3 | -19 12 21

26 | 1 -1 0 | -3 6 -3 | -22 18 18

27 | 1 -1 -1 | -2 5 -4 | -24 23 14

28 | 1 -1 -1 | -1 4 -5 | -25 27 9

29 | 1 -1 -1 | 0 3 -6 | -25 30 3

30 | 1 -1 0 | 1 2 -6 | -24 32 -3

31 | 1 -1 1 | 2 1 -5 | -22 33 -8

32 | 1 -1 1 | 3 0 -4 | -19 33 -12

33 | 1 -1 1 | 4 -1 -3 | -15 32 -15

34 | 1 -1 1 | 5 -2 -2 | -10 30 -17

35 | -1 -1 1 | 4 -3 -1 | -6 27 -18

36 | -1 -1 1 | 3 -4 0 | -3 23 -18

37 | -1 -1 1 | 2 -5 1 | -1 18 -17

38 | -1 1 1 | 1 -4 2 | 0 14 -15

39 | -1 0 1 | 0 -4 3 | 0 10 -12

40 | 0 0 0 | 0 -4 3 | 0 6 -9

41 | 0 1 1 | 0 -3 4 | 0 3 -5

42 | 0 0 1 | 0 -3 5 | 0 0 0

Edited January 17, 2012 by CaptainEd

[Morningstar]

(^^^ I see you can edit again.)

Does the line have to end on the "sphere" or just pass through it?

[CaptainEd]

Morningstar, Molly Mae's answer to this seemed to me to say that each line segment has to pass through the cube no further than 1 in any dimension from the target point. I didnt quite get the statement about having to hit both min and max on a dimension. My answers so far have actually ended a line segment within the cube, because the Excel spreadsheet formulas I'm using to help me keep honest look dauntingly more complicated if I try to code a line-segment-intersects-a-cube function. I have the feeling that would save some more steps, though.

Molly Mae, this is interesting. doing a manual search of this space is tricky. The addition of the third dimension is good, and your diabolically pathological choices of locations is very well done! It feels like every pair of points is far apart, and every triad of points requires severe acceleration/deceleration. Great job!

Not done yet...

[Molly Mae]

Morningstar, Molly Mae's answer to this seemed to me to say that each line segment has to pass through the cube no further than 1 in any dimension from the target point. I didnt quite get the statement about having to hit both min and max on a dimension. My answers so far have actually ended a line segment within the cube, because the Excel spreadsheet formulas I'm using to help me keep honest look dauntingly more complicated if I try to code a line-segment-intersects-a-cube function. I have the feeling that would save some more steps, though.

Molly Mae, this is interesting. doing a manual search of this space is tricky. The addition of the third dimension is good, and your diabolically pathological choices of locations is very well done! It feels like every pair of points is far apart, and every triad of points requires severe acceleration/deceleration. Great job!

Not done yet...

Thanks, Captain. For the record: A line segment doesn't have to end in a cube. Because of the placement of points, I don't know how much difference that would actually make, since you're almost always turning on your heel after hitting a mark. But maybe I just can't see it. I think the hardest part is determining an order. The possible orders should have probably been added without the third dimension (or added the third dimension, but specified an order of points).

[CaptainEd]

I agree, guessing the best order is hard. I've published answers with two different orders (turns out, I didn't even identify when points were near-misses to marks, sorry...), and I have no idea yet what the optimal is.

I have a theoretical thought that sometimes, you'd turn around before or after hitting a mark, so as to get high enough velocity to get to the next one, which is why I imagine that it might be good for a line segment to pass through the mark. However, as I said, it takes some programming that I have not had time to do, so I can't show an optimized path that benefits from that.

Molly Mae, have you got below 42 yet?

[Molly Mae]

I agree, guessing the best order is hard. I've published answers with two different orders (turns out, I didn't even identify when points were near-misses to marks, sorry...), and I have no idea yet what the optimal is.

I have a theoretical thought that sometimes, you'd turn around before or after hitting a mark, so as to get high enough velocity to get to the next one, which is why I imagine that it might be good for a line segment to pass through the mark. However, as I said, it takes some programming that I have not had time to do, so I can't show an optimized path that benefits from that.

Molly Mae, have you got below 42 yet?

No, I haven't, but I've been running on the assumption that turning on the mark is optimal. I wonder now if maybe it isn't. Since one dimension will always be turning about, that should be the longest leg of that particular journey. I think perhaps defining a trip from point A to B based on the greatest expected distance, an optimal path could at least be limited to several possibilities. I understand that the velocity (mainly direction) will also play a large factor, so the turnaround dimension should likely have the shortest next path.

Edited January 19, 2012 by Molly Mae

[CaptainEd]

For what it's worth, here is a chart of the x, y, and z values in my recent 42 move solution. Plotting them this way made it a little easier to look for regions that wanted to be optimized. I think...

[Morningstar]

You think what? I'm a bit confused about the graph.

[CaptainEd]

Sorry to be vague.

This graph shows the sequences of x-, y-, and z-coordinates. To get to the next waypoint quickest, you want to accelerate halfway and then decelerate. The path will look like a smooth parabola, as you see in most of the graph. When I started, with a solution having 4 more moves, one or two of the parabolas were not perfect. That gave me a hint of where to look for potential improvement.

The words "I think..." were intended to convey that I am not certain that the graphing has actually helped.

[Morningstar]

I see.

[Molly Mae]

If you switched your first and second stops, do you think you could hit the y-coordinate "on the move" toward the third stop?

That graph is epic and really does paint a clear picture by eliminating some otherwise not-so-obvious wrong steps.

Edited January 25, 2012 by Molly Mae

[CaptainEd]

Haven't got a good solution yet. Partly because swapping the first two waypoints makes the first three legs dominated by 26, 26, and -60.

I like the fact that both the X and the Z travel 26 between the first and second waypoints. I can't tell yet whether it's good to have long legs (like 60) (because the number of steps is roughly the square root of the distance), or it's bad (because it's long anyway).