Brain Quiz #12

Okay, here’s something new for us to try. You have 2 identical robots, and each must be given an identical set of commands. These robots will then be dropped out of a plane and parachute down to random locations on a straight line that extends infinitely in opposite directions (As in, it doesn’t wrap around and meet up with itself or anything, so it’s not like the equator or anything). When the robots land, the parachutes detach, and remain where they landed. Neither robot knows where the other robot is being dropped, so they wouldn’t know which direction it was in or anything. Your job is to program these robots to collide with each other.

The robots only have room for 10 commands, and you can choose from the following:
Move Left one unit.
Move Right one unit.
Skip the next command, unless there’s a parachute on this space.
Go to a specific command number.

So here’s an example of a program:
10 Go Right.
20 Go Left.
30 SKIP the next command unless there’s a parachute.
40 GOTO 10.

Make sense? Okay, your goal is to make them collide, and you only get 10 commands spaces. [Meaning, your program only consists of 10 lines of “code”. Not to be confused with “10 moves”, which would be something different.”] Each command takes one cycle to execute (including GOTO’s and SKIPs), and each movement moves 1 standard unit (we can call it a foot if that helps, but it doesn’t really matter) An extra 5 points for the first answer that guarentees a collision. A bonus 5 points for the most efficient/quickest answer. (The answer that would get them to collide the fastest in most situations). Ties split the bonus points.

Difficulty Rating: 14

14 thoughts on “Brain Quiz #12

  1. 10 Go Right.
    20 SKIP the next command unless there’s a parachute.
    30 GOTO 50.
    40 GOTO 10
    50 Go Right.
    60 Go Right.
    70 Go Right.
    80 Go Right.
    90 Go Right.
    100 GOTO 50.

  2. 10 GO LEFT
    20 SKIP
    30 GOTO 10
    40 GO LEFT
    50 GO LEFT
    60 GO LEFT
    70 GO LEFT
    80 GO LEFT
    90 GO LEFT
    100 GOTO 40

    That should get them to collide as quickly as possible.

  3. 10 Go Left
    20 SKIP… Parachute
    30 GOTO 50
    40 GOTO 10
    50 Go Left
    60 GOTO 50
    __________________________

    this was *tough*. basically the key is to have one robot figure out that it’s the left-most robot. Once one has done that it can hurry up while the other one spends more cycles in the “SKIP… Parachute” checks.

    i struggled until i spent more time thinking about the whole “cycle” verbage you had in there.

  4. I really don’t understand this one, so I will be patiently waiting for your next question…I have never understood programing, when we had it in math class we skipped those sections…oh well.

  5. 0 Go left
    1 Go right
    2 Go left
    3 If Parachute, skip next
    4 Goto 0
    5 Go left
    6 Goto 5

    I’m glad the rating was high, because that took me some pondering. I’m very curious to see how to evaluate efficiency, since they can land 2 or 2 million moves apart. Or maybe there’s an answer that works differently from mine.

  6. I think more details needed to be included in regards to the timing issues of things, but perhaps that’s only because I don’t do a whole lot of programming.

    10 Go left
    20 Go left
    30 Go right
    40 Skip unless parachute
    50 Goto 70
    60 Goto 10
    70 Go left
    80 Go left
    90 Go left
    100 Goto 70

    This way, once the one of them finds a parachute, then it will be going 3 times faster than the other one to catch up (I think I could have made it go much faster, but I didn’t understand “Each command takes one cycle to execute.”

    If that means that after one set of commands, it would wait for the other robot to finish all of its commands, then I would go with this program

    10 Go left
    20 Skip next unless parachute
    30 Goto 50
    40 Goto 10
    50 Go left
    60 Go left
    70 Go left
    80 Go left
    90 Go left
    100 Goto 50

    By the rationale mention before about the timing, this way once a robot got to the first parachute, it would go 5 spaces left for each 1 space of the other one, catching up faster (again, I didn’t understand the timing of the programming issue).

    Whichever one is best, that’s the one I’m submitting as my answer, Cubs win,

    -R to the B

  7. Oops, misread the commands.
    Let’s try again:

    0 Move left
    1 Skip next unless parachute
    2 Goto 6
    3 Move right
    4 Move left
    5 Goto 0
    6 Move left
    7 Move left
    8 Move left
    9 Goto 6

    I’ll feel very stupid if I messed up again.

    Also, I’m going to submit an alternate answer that catches up slightly slower but gets to the parachute faster:

    0 Move left
    1 Skip next unless parachute
    2 Goto 4
    3 Goto 0
    4 Move left
    5 Move left
    6 Move left
    7 Move left
    8 Move left
    9 Goto 4

  8. Just to be a smarty-pants (or follow my blunders with yet more blunders, should I be mistaken again), I further hypothesize that my second answer is the fastest, causing a collision in approximately 5x cycles, where x is the number of units separating the robots when they land.

  9. Here’s the best that I could come up with:
    00 Go Left
    10 Skip next unless Parachute
    20 Goto 40
    30 Goto 00
    40 Go Left
    50 Go Left
    60 Go Left
    70 Go Left
    80 Go Left
    90 Goto 40

    It would appear the Klaas, Pcg, Paul, and Rob all found the same solution, and they’ll each get another 2 points [dividing 5/2 is hard with integers)

    Unless I’m mistreading something, John’s solution works only if the robots land right next to each other (they’d collide on teh 6th command execution) Otherwise, they both just run to the left forever (each discovering its own parachute after the first loop. Jeff’s solution works by keeping the robut who hasn’t found a parachute slow, then letting the parchute-finding robut move at normal pace. It works, but appears to be a bit slower than the other solutions.

  10. Smarty-pants again, with more fun facts about robots:

    The robots each move x spaces, the distance between their landings, at their initial speed, n. Then one speeds up, and they end up traveling farther before they collide, but the time it takes to close the gap is equal to the time it would take to go x units at their relative speed, p (that is, the difference between the initlal speed, which one robot is still going, and the faster speed that the pursuing robot is now going).
    So the formula for the average time to collision is T(x)=1/n + 1/p, which translates to T(x)=(n+p/np)x.

    So my first answer, had it been coded right, would have had an initial speed of .2 (one move per 5 cycles) and a chase speed of .3 (faster robot going .5), so they would collide in 8.33x cycles. That’s also what Jeff’s answer would do, except if the robots landed directly adjacent to each other, in which case they would never collide.

    The winning answer starts at 1/3 and speeds up to 5/6, so the chase speed is .5 and it catches up in 5x cycles.

    The first of my corrected answers keeps the initial speed low, at the expense of a few lines that could be used to speed up the pursuing robot, and ends up taking 6.82x.

    One other possible answer, which falls between the two, would be
    0 move left
    1 skip next unless parachute
    2 goto 5
    3 goto 4
    4 goto 0
    5 move left
    6 move left
    7 move left
    8 move left
    9 goto 5

    That burns once cycle (line 3) to slow the initial speed down, rather than two. It ends up taking 5.82x cycles.

    So that was fun. Hopefully people won’t be too irked by my know-it-allity because they won’t be looking back at the comments to old posts anyway. But it’s good to get it out of my system.

  11. Wow.. thanks for doing all that Math, Klaas. If I’m understanding things right then, it would depend on how close together the two robots started for which one would finish faster. The way I see it, the catch up speed being faster is offset by the fact that it takes quite a bit longer to get to the parachute in the first place, and thus the “standard” correct answers would be fastest in every situation, except when the distance between them is less than 2 spaces.
    When the distance is 2, the standard answer finishes at cycle 9,
    your “in between” answer finishes at cycle 10.
    When distance is 1, standard finishes at cycle 5, while the in between finishes at cycle 4.

    But above 2, the number of extra cycles the in between answer takes to finish after the standard answer just keeps increasing.
    5 spaces: 29-32
    25 spaces: 125 – 143
    100 spaces: 500 – 580

    So as you pointed out, as the number of spaces increase, the standard answer moves closer to taking 5 * (number of spaces) cycles to complete.

    For even more fun, check this out: I coded up the 3 main robot programs
    Red : the standard / fastest answer
    Blue : Klaas’ in between answer
    Green: Klaas’ first correct answer.

    Just go to http://www.ronveenstra.com/robots.php?cycle=0andspace=25
    Here “space” = number of spaces between the two robots when they land (0 doesn’t work yet, because I got lazy with it) and “cycle” is which cycle the robots are all currently on.

Leave a Reply

Your email address will not be published. Required fields are marked *