tag:blogger.com,1999:blog-9124539381685751273.post635357765877600452..comments2023-06-19T04:35:06.263-07:00Comments on Skeptic's Play: Parachuting robotsmillerhttp://www.blogger.com/profile/05990852054891771988noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-9124539381685751273.post-44082101838007278852010-11-10T21:59:00.030-08:002010-11-10T21:59:00.030-08:00It was difficult to convince myself, but I'm s...It was difficult to convince myself, but I'm sure your solution is O(n), Danny. I was surprised that a zig-zagging solution could work, but it does. The fact that the robots double their distance at every step (rather than increasing it linearly) is crucial.millerhttps://www.blogger.com/profile/05990852054891771988noreply@blogger.comtag:blogger.com,1999:blog-9124539381685751273.post-70427689477605910272010-11-10T20:35:55.707-08:002010-11-10T20:35:55.707-08:00Just found this site and loving the puzzles! I ca...Just found this site and loving the puzzles! I came up with a solution that is a bit different, and I realize after reading the comments, not quite as good as Barefoot Bum, but I believe still O(N). Correct me if I'm wrong!<br /><br />Start by moving 1 unit to the right.<br />While haven't found other chute (or other bot):<br /> Turn around and double your distance<br />Once you find the chute, keep moving in same direction til you meet other bot.<br /><br />Using Excel to try different values I seem to get between 2N and 4N for total time (and also distance).<br /><br />Again, not as good as the move one, wait one. Still linear time though.Dannyhttps://www.blogger.com/profile/10404153565090996945noreply@blogger.comtag:blogger.com,1999:blog-9124539381685751273.post-70022415246896681892010-09-07T01:12:36.742-07:002010-09-07T01:12:36.742-07:00I think Barefoot Bum's got it, altho' we h...I think Barefoot Bum's got it, altho' we have to assume that each robot has the same understanding of "left" (which is safe to do given that they're presumably two dimensional).<br /><br />The ability to detect the other's parachute is pretty much essential since we need some event to trigger a change in the behaviour of one of them. Otherwise they would require a random number generator to tell them to occasionally change direction.<br /><br />If you consider both robots to be parts of a single machine for detecting parachutes, you very quickly realise that there is no need to have the robots search in both directions.<br /><br />The move 1, wait 1 algorithm is the most efficient because the total time taken to meet is shared equally between searching for the parachute and closing the gap after detection. Any increase in efficiency in one activity is more than matched by a greater decrease in efficiency in the other.Secret Squïrrelnoreply@blogger.comtag:blogger.com,1999:blog-9124539381685751273.post-63891672862352161172010-09-06T22:59:00.238-07:002010-09-06T22:59:00.238-07:00Barefoot Bum, unless I am mistaken, your solution ...Barefoot Bum, unless I am mistaken, your solution is O(N). It takes 2N steps to find the parachute, and then 2N more to find the robot.millerhttps://www.blogger.com/profile/05990852054891771988noreply@blogger.comtag:blogger.com,1999:blog-9124539381685751273.post-19050342473109595892010-09-06T15:29:00.298-07:002010-09-06T15:29:00.298-07:00If you can't wait, each robot can move two uni...If you can't wait, each robot can move two units to the left and then one unit to the right until it encounters the other parachute. Thanks to intrinsically knotted for spotting the parachute-spotting trick; without it, I don't think you can solve the problem in less than O(N^2) time.Larry Hamelinhttps://www.blogger.com/profile/08788697573946266404noreply@blogger.comtag:blogger.com,1999:blog-9124539381685751273.post-70292775988380936242010-09-06T15:23:57.242-07:002010-09-06T15:23:57.242-07:00O(N*3), actually: N*2 to find the other parachute,...O(N*3), actually: N*2 to find the other parachute, N to find the other robot.Larry Hamelinhttps://www.blogger.com/profile/08788697573946266404noreply@blogger.comtag:blogger.com,1999:blog-9124539381685751273.post-67359361407138409902010-09-06T15:22:14.865-07:002010-09-06T15:22:14.865-07:00Until you have encountered the other parachute, mo...Until you have encountered the other parachute, move one unit to the left and wait for one unit of time. Once you have encountered the other parachute, move one unit to the left without waiting. This is at least some improvement to O(N*2).Larry Hamelinhttps://www.blogger.com/profile/08788697573946266404noreply@blogger.comtag:blogger.com,1999:blog-9124539381685751273.post-39531574450206789502010-09-06T14:17:11.785-07:002010-09-06T14:17:11.785-07:00Really, there's an O(n) solution? I shall have...Really, there's an O(n) solution? I shall have to think harder! (I can think of some minor improvements to my first solution, but nothing yet that will improve the complexity.)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-9124539381685751273.post-59898285559473875632010-09-06T13:47:02.614-07:002010-09-06T13:47:02.614-07:00Yes! Robots can recognize the parachute on the gr...Yes! Robots can recognize the parachute on the ground. That solution works perfectly.<br /><br />However, the amount of time for the algorithm to complete is proportional to N^2, where N is the distance between the robots. It's possible to find an algorithm whose completion time is proportional to N. (For you CS geeks: I'm saying that you can find a O(N) solution.)millerhttps://www.blogger.com/profile/05990852054891771988noreply@blogger.comtag:blogger.com,1999:blog-9124539381685751273.post-74639510254923279612010-09-06T12:39:53.444-07:002010-09-06T12:39:53.444-07:00If the robots can identify the sight of a parachut...If the robots can identify the sight of a parachute on the ground, I can do it: <br /><br />Each robot, after it lands, should do the following:<br /><br />For n starting at 1 do:<br /><br />start: Move n units to the right. If a parachute is encountered during this travel, END.<br />Move n units to the left (back to the landing site).<br />Move n units to the left. If a parachute is encountered during this travel, END.<br />Move n units to the right (back to the landing site).<br />Increment n and GOTO start.<br /><br />Each robot will be moving in the same direction at the same speed at all times until one of them halts. Eventually, one will travel far enough in the correct direction to encounter the other's parachute, and will stop there. When the other robot returns to its own landing site, they will meet.Anonymousnoreply@blogger.com