21 replies to this topic

[CaptainEd]

Spoiler for Sorry, still unable to edit. Here's another try at 42 steps

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 by CaptainEd, 17 January 2012 - 06:47 AM.

[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 by Molly Mae, 19 January 2012 - 08:06 PM.

[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.