Descartes Racing.......

[superprismatic]

Let's have a race in the cartesian plane. We define a point as a pair, (x,y), where

x and y are both integers. We will start the race at the point (0,0). Then, we stop

at the points (18,20), (14,12), (35,25), (30,8), then back to (0,0), in that order.

In order to tell how we can move each time, we have a movement vector (a,b). if we are

at point (x,y) and the movement vector is (a,b), the next point we will visit is (x+a,y+b).

The movement vector starts at (0,0). Before each move, we may add or subtract 1 from

either or both or none of the elements of the movement vector, then we use it to move.

To move from (0,0) to (18,20), for example, we can move as follows:

01. at point (0,0); movement vector=(0,0); new movement vector=(-1,1); new point=(-1,1)

02. at point (-1,1); movement vector=(-1,1); new movement vector=(-2,2); new point=(-3,3)

03. at point (-3,3); movement vector=(-2,2); new movement vector=(-3,2); new point=(-6,5)

04. at point (-6,5); movement vector=(-3,2); new movement vector=(-2,3); new point=(-8,8)

05. at point (-8,8); movement vector=(-2,3); new movement vector=(-1,4); new point=(-9,12)

06. at point (-9,12); movement vector=(-1,4); new movement vector=(0,3); new point=(-9,15)

07. at point (-9,15); movement vector=(0,3); new movement vector=(1,3); new point=(-8,18)

08. at point (-8,18); movement vector=(1,3); new movement vector=(2,2); new point=(-6,20)

09. at point (-6,20); movement vector=(2,2); new movement vector=(3,1); new point=(-3,21)

10. at point (-3,21); movement vector=(3,1); new movement vector=(4,1); new point=(1,22)

11. at point (1,22); movement vector=(4,1); new movement vector=(5,0); new point=(6,22)

12. at point (6,22); movement vector=(5,0); new movement vector=(6,-1); new point=(12,21)

13. at point (12,21); movement vector=(6,-1); new movement vector=(6,-1); new point=(18,20)

In this example, it took 13 moves to get from (0,0) to (18,20). Our next target is (14,12),

but we are stuck with our movement vector of (6,-1) which we can change before we use it to

get to our next point. The problem is to go from (0,0) back to (0,0) stopping at the points

(18,20), (14,12), (35,25), and (30,8) (in that order, along the way) in the fewest number of

moves. Are you up to the challenge?

[Guest]

cur coor|  move

0,0  	0,0

0,0  	1,1

1,1  	2,2

3,3  	3,3

6,6  	3,4

9,10	3,3

12,13  3,4

15,17  3,3

18,20  2,2

20,22  1,1

21,23  0,0

21,23  -1,-1

20,22   -2,-2

18,20   -2,-3

16,17   -1,-3

15,14   -1,-2

14,12	0,-1

14,11   1, 0

15,11	2,1

17,12	3,2

19,14	4,3

23,17	5,3

28,20	4,3

32,23	3,2

35,25 	2,1

37,26	1,0

38,26    0,-1

38,25	-1,-2

37,23   -1,-3

36,20	-1,-4

35,16   -1,-3

34,13   -1,-2

33,11   -1,-2

32,9 	-2,-1

30,8  	-3,-1

27,7 	-4,-1

23,6 	-5,-1

18,5 	-5,-1

13,4 	-4,-1

9,3  	-3,-1

6,2  	-3,-1

3,1  	-3,-1

0,0

43 moves.

[CaptainEd]

x y a b

0 0 1 1

1 1 2 2

3 3 3 3

6 6 4 4

10 10 3 4

13 14 2 3

15 17 2 2

17 19 1 1

18 20 1 0

19 20 0 -1

19 19 -1 -2

18 17 -2 -2

16 15 -1 -2

15 13 -1 -1

14 12 0 0

14 12 1 1

15 13 2 2

17 15 3 3

20 18 4 3

24 21 4 2

28 23 3 2

31 25 2 1

33 26 1 0

34 26 1 -1

35 25 1 -2

36 23 0 -3

36 20 -1 -4

35 16 -2 -4

33 12 -3 -4

30 8 -4 -3

26 5 -5 -2

21 3 -6 -1

15 2 -7 -1

8 1 -8 -1

0 0 -9 -1

[Guest]

1: ( 0, 0) [ 1, 1] !!!

 2: ( 1, 1) [ 2, 2]

 3: ( 3, 3) [ 3, 3]

 4: ( 6, 6) [ 4, 4]

 5: (10,10) [ 3, 4]

 6: (13,14) [ 2, 3]

 7: (15,17) [ 2, 2]

 8: (17,19) [ 1, 1]

 9: (18,20) [ 0, 0] !!!

10: (18,20) [-1,-1]

11: (17,19) [-2,-2]

12: (15,17) [-1,-3]

13: (14,14) [ 0,-2]

14: (14,12) [ 1,-1] !!!

15: (15,11) [ 2, 0]

16: (17,11) [ 3, 1]

17: (20,12) [ 4, 2]

18: (24,14) [ 4, 3]

19: (28,17) [ 3, 3]

20: (31,20) [ 2, 2]

21: (33,22) [ 1, 2]

22: (34,24) [ 1, 1]

23: (35,25) [ 1, 0] !!!

24: (36,25) [ 2,-1]

25: (38,24) [ 1,-2]

26: (39,22) [ 1,-3]

27: (40,19) [ 0,-4]

28: (40,15) [-1,-3]

29: (39,12) [-2,-2]

30: (37,10) [-3,-1]

31: (34, 9) [-4,-1]

32: (30, 8) [-5,-2] !!!

33: (25, 6) [-6,-3]

34: (19, 3) [-6,-2]

35: (13, 1) [-7,-1]

36: ( 6, 0) [-6, 0]

37: ( 0, 0)         !!! 

Edited August 18, 2011 by Dej Mar

[Guest]

Nice solution CaptainEd. Beat my first attempt by 3 moves.

[CaptainEd]

By only two moves, Dej Mar. But squeezing one or two more moves out looks very tough, what do you think?

[Molly Mae]

The fastest method using only x and a, I get 33 moves. Using only y and b, I get 31.

This is number of moves for x and y independently of the other (but taking into consideration direction change for next move) until arrival at each destination:

1. 8, 8

2. 4, 6

3. 10, 9

4. 4, 6

5. 7, 2

Will reanalyse shortly. Some can be modified (see 4,6) to include "turnaround time" as I like to call it.

[CaptainEd]

Good idea, Molly, that establishes lower bounds. I think I can improve your x's

1,2,3,4,3,2,2,1 (18)--8 steps

0-1-2-1 (14)--4 steps

012344322 (35)--9 steps

1,0-1-2-3 (30)--5 steps

-4-5-6-7-8 (0)--5 steps

[Molly Mae]

Best I could find is:

y b

1 1

2 3

3 6

4 10

4 14

3 17

2 19

1 20 !!

0 20

-1 19

-2 17

-2 15

-2 13

-1 12 !!

0 12

1 13

2 15

3 18

3 21

2 23

1 24

1 25

0 25 !!

-1 24

-2 22

-2 20

-3 17

-4 13

-5 8 !!

-4 3

-3 0 !!

...x...y

1. 8, 8

2. 4, 6

3. 9, 9

4. 5, 6

5. 5, 2

If y can't be improved for any instance of y > x (steps 2 and 4) at the expense of a longer trip where x > y, the shortest trip should be the sum of the larger from each step.

1. 8

2. 6

3. 9

4. 6

5. 5

= 34

Edited August 18, 2011 by Molly Mae

[Molly Mae]

...x...y

1. 8, 8

2. 4, 5

3. 9, 9

4. 5, 7

5. 5, 2

b..y

1 1

2 3

3 6

4 10

4 14

3 17

2 19

1 20 ! -> 12

0 20

-1 19

-2 17

-3 14

-2 12 ! ->25

-1 11

0 11

1 12

2 14

3 17

2 19

3 22

2 24

1 25 ! -> 8

0 25

-1 24

-2 22

-3 19

-4 15

-3 12

-4 8 ! -> 0

-4 4

-4 0 !

Reduces the time for the second leg of the trek at the cost of a longer trip on the 4th leg. -1 and +1 = No net gain.

34 is looking like our lower limit.

[CaptainEd]

Molly Mae, I fear you are right. My heart tells me that any time I'm not accelerating or decelerating, I'm wasting time (these are places where the acceleration is 0, rather than 1 or -1). There are a half dozen of those in my 2-D solution, and a smaller number in your 1D solutions. Yet they seem to all be necessary in order to prepare to land on the next waypoint, or to do so while preparing for the subsequent path (or for marking time because of the longer distance in the other dimension).

I very much enjoy your penultimate "flight home" from 35,25 in the Y dimension--two steps from 8 to 0 is awesome!

[CaptainEd]

For a racing experience that is similar and yet different, I've added a boat-race variant to this challenge ().

[Guest]

There are (at least) 672 different ways to race from (0,0) to (0,0)

in the minimum 34 steps with stopping at each of the four intervening check points.

A] 8 steps between (0,0) and (18,20):

(1,1), (2,2), (3,3), (4,4), (3,4), (2,3), (2,2), (1,1)

(1,1), (2,2), (3,3), (3,4), (3,4), (3,3), (2,2), (1,1)

B] 6 steps between (18,20) and (14,12):

(1,0), ( 0,-1), (-1,-2), (-2,-2), (-1,-2), (-1,-1)

(1,0), ( 0,-1), (-1,-2), (-1,-2), (-2,-2), (-1,-1)

(0,0), ( 0,-1), (-1,-2), (-1,-2), (-1,-2), (-1,-1)

(0,0), ( 0,-1), ( 0,-2), (-1,-2), (-2,-2), (-1,-1)

(0,0), ( 0,-1), (-1,-2), (-2,-2), (-1,-2), ( 0,-1)

(0,0), (-1,-1), (-1,-2), (-1,-2), (-1,-2), ( 0,-1)

(0,0), (-1,-1), (-2,-2), (-1,-2), ( 0,-2), ( 0,-1)

C] 15 steps between (14,12) and (30,8) [with stop at (35,25)]:

C1a] 9 steps between (14,12) and (35,25):

(0,0), (1,1), (2,2), (3,3), (4,3), (3,2), (3,1), (3,1), (2,0)

(0,0), (1,1), (2,1), (3,2), (4,3), (3,3), (3,2), (3,1), (2,0)

(0,0), (1,1), (2,2), (3,3), (4,3), (4,2), (3,1), (2,1), (2,0)

(0,0), (1,1), (2,1), (3,2), (4,3), (4,3), (3,2), (2,1), (2,0)

C1b] 6 steps between (35,25) and (30,8):

(1,-1), (0,-2), (0,-3), (-1,-4), (-2,-4), (-3,-3)

(1,-1), (0,-2), (0,-3), (-1,-4), (-2,-3), (-3,-4)

(1,-1), (0,-2), (0,-3), (-1,-4), (-2,-4), (-3,-4)

-or-

C2a] 10 steps between (14,12) and (35,25):

(0,0), (1,1), (2,2), (3,3), (4,3), (4,2), (3,2), (2,1), (1,0), (1,-1)

(0,0), (1,1), (1,2), (2,3), (3,3), (4,2), (4,2), (3,1), (2,0), (1,-1)

(0,0), (1,1), (2,2), (3,2), (4,3), (4,3), (3,2), (2,1), (1,0), (1,-1)

(0,0), (1,1), (1,2), (2,2), (3,3), (4,3), (4,2), (3,1), (2,0), (1,-1)

C2b] 5 steps between (35,25) and (30,8):

(1,-2), (0,-3), (-1,-4), (-2,-4), (-3,-4)

D] 5 steps between (30,8) and (0,0):

(-4,-3), (-5,-2), (-6,-2), (-7,-1), (-8,0)

(-4,-3), (-5,-2), (-6,-1), (-7,-1), (-8,-1)

(-4,-2), (-5,-2), (-6,-2), (-7,-1), (-8,-1)