superprismatic Posted August 18, 2011 Report Share Posted August 18, 2011 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? Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 18, 2011 Report Share Posted August 18, 2011 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. Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted August 18, 2011 Report Share Posted August 18, 2011 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 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 18, 2011 Report Share Posted August 18, 2011 (edited) 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 Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 18, 2011 Report Share Posted August 18, 2011 Nice solution CaptainEd. Beat my first attempt by 3 moves. Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted August 18, 2011 Report Share Posted August 18, 2011 By only two moves, Dej Mar. But squeezing one or two more moves out looks very tough, what do you think? Quote Link to comment Share on other sites More sharing options...
0 Molly Mae Posted August 18, 2011 Report Share Posted August 18, 2011 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. Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted August 18, 2011 Report Share Posted August 18, 2011 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 Quote Link to comment Share on other sites More sharing options...
0 Molly Mae Posted August 18, 2011 Report Share Posted August 18, 2011 (edited) 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 Quote Link to comment Share on other sites More sharing options...
0 Molly Mae Posted August 19, 2011 Report Share Posted August 19, 2011 ...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. Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted August 19, 2011 Report Share Posted August 19, 2011 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! Quote Link to comment Share on other sites More sharing options...
0 CaptainEd Posted August 19, 2011 Report Share Posted August 19, 2011 For a racing experience that is similar and yet different, I've added a boat-race variant to this challenge (). Quote Link to comment Share on other sites More sharing options...
0 Guest Posted August 23, 2011 Report Share Posted August 23, 2011 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) Quote Link to comment Share on other sites More sharing options...
Question
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?
Link to comment
Share on other sites
12 answers to this question
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.