Show HN: Parachuting robots – a programming puzzle | Hacker News Reader

Show HN: Parachuting robots – a programming puzzle

david-peter.de

60 pointssharkdp55 comments

Here's my best implementation:

  start: left
         skipNext
         goto start
  fast:  left
         goto fast

Red and Blue must take three cycles to move one space until Blue hits Red's parachute. Then, Red take three cycles to move one space while Blue takes two cycles to move one space where Blue then catches Red shortly after.

"It seems to originate from a Microsoft interview question."

Using inefficiency to solve problems, I'm not surprised.

Ha! That's what I thought. It's a duct-taping solution.

This problem was posed to me for real in a Microsoft interview in the late 90s. At first I was like "How hard could this be?" but quickly discovered that it wasn't so obvious. If I hadn't already seen the famous circular-list detection method, there's no way I would've gotten it, not during the interview at least.

Here is how I did it

    start: left
           skipNext
           goto start
           goto double

    double: left
            left
            goto double

The idea comes from the "find a loop in a singlely linked list in O(1) space" problem.

One pointer moves twice as fast the as the other one.

You don't need the 'goto double' line, execution is anyway going skip to 'double: left' making the line redundant

Also say each step takes one unit of time, so one 'start' loop requires 3 units to go one unit of distance, whereas 'double' takes 3 units to go 2 units of distance, even if you use one left statement in the 'double' loop, robot will still move faster than the other as it will require only two units of time to go one unit of distance.

I come up with the exact same with 'right' instead of 'left' :D

slow: left skipNext goto slow fast: left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left left goto fast

The best set for making it as fast as possible within the bounds of the javascript parser.

Wow, great puzzle.

Also great implementation and beautiful site.

Though, IMHO there could be a button named "parse & run", my eyes have missed a "parse" button, and I thought that something was broken.

Thank you, I'm glad you liked it!

I see, the disabled play button in the beginning is not optimal. Replacing "parse" with "parse & run" is an interesting option. I'm not sure yet, how it would affect the other buttons, though. I somehow like the debugging-style "Step" feature. Would it be better to have the example program parsed already such that "Play" is enabled on page load?

Answering your question, maybe a popover with text "Your program is not parsed" would help?

Also somehow I am used to "build" (instead of "parse") terminology, so my eyes just have not caught "parse" keyword. Though, I guess here nothing is built, only parsed. ;)

All in all some information, about parsing before running would add extra points to the UX.

Great suggestion, thanks! I added (state-dependent) mouse-over tooltips for all buttons.

Is the goal to create a short programm (less lines) or an efficient programm (fast)?

Spoiler!

  start: left
    skipNext
    goto start
  speedup: left
    goto speedup

That interview question seems related to the "how to detect loops in a potentially infinite list" question which I was asked at least once.

Did you solve it?

The interview question back then, no. But I remember the solution so I could solve this robot problem quickly :-)

I kept thinking,how would robots know when to switch directions? That is when I realized that robots do not have to crash head on but overtaking is sufficient.

This is one case where I am glad that I did not read HN comments before solving. My solution is the same as moftz and other left leaners. :) First iteration I made the speed be four times the slow robot but of course double speed is fine.

Is it possible to make them go inward to each other instead of chasing?

no, because they don't have any information about the other robot and they can not tell whether they are walking towards the other parachute or walking away from both parachutes because they are somewhere on an infinite line.

I don't think there is without a counter and an if statement. I had this question once and came up with the two robots oscillating around their parachute until they came across another parachute at which point it would stop and wait for the other to return.

My solution: http://pastebin.com/FqgCAXKA

That can be cleaned up considerably.

2 labels, and 5 statements

2 labels and 6 statments. I don't know how to get 5 statments.

http://pastebin.com/ZcLdJhzN

remove one "left" from the speed label :D

Yes. Because the left in "loop" will have already been executed by the time it gets to "speed".

Also "loop" is not a good label. They are both loops.

Fantastic puzzle.

Took me ages to realise the twist though, because I was somehow set on making them oscillate further on every iteration and couldn't understand how I was to remember how far I went without a stack.

Basically what I wanted to do was: x left, if its not there, return. Next time x * 2 left, return to base if its not there, ...

At first I thought there couldn't be a solution, since both robots always do the same thing. You can imagine the "duh!" in my head after seeing the comments here…

I'm not sure I would have gotten the puzzle without the great visualization. Very cool!

Much appreciated entertainment on a lazy friday at work :)

Took me about 2 minutes to come up with:

start: left left right skipNext goto start continue: left goto continue

And this is the right way. If you consider that left and right are mechanic robot movements taking considerable time then

  start: left skipNext goto start continue: left goto continue

might not gain any appreciable speedup.

Here is slight twist on the problem: the new robot has multiple cores with shared cache and very accurate branch prediction so branching instructions do not waste any cycles. So "left, skipNext, goto" loop performs exactly as efficiently as "left, left, goto" loop. Can you still solve this?

Timing of the left command would depend on robot mechanics, not the processor clock.

How many labels you need to solve this? I have four, but I wonder if it can be simplified.

Suggestion: Add ability to share the code.

I used two labels.

Ah, I see now. I haven't realized instructions other than left/right cost anything. My solution should work in "real time".

(and even that could be done in two as well as I see now)

Can you show your four label solution?

I already closed it, so might be a bit different, but essentially this: https://paste.fedoraproject.org/285179/62077561/

I guess my interview wouldn't go that well :)

Cool :)

I used two.

I made it through with two [0]

[0] https://gist.github.com/kanche/92c92c5e926ebc66da68

To watch them run around is so cool! Cool puzzle. Nicely created site. I am trying to give them a pendulum like swing instruction right now, make them dance :P

edit: had two unnecessary instruction in the gist (because each instruction takes same amount of time to execute), and, the robots disappointed me- they can't dance

Additional suggestion: ability to grade code. I see solutions that are a lot shorter than mine in code (2 labels, 5 instructions), but they take about 87 instruction cycles to get there whereas without labels you can do it in about 30 cycles.

... Without labels? Can you show that solution? Are you sure it works for robots placed on an infinite line?

Yeah, I was about to delete my comment (but now someone already replied) because I discovered the randomize button. My bad!

The solution with a "speeding label" is the only solution I see. I also recognize the parallel with infinite loop detection now, like sugarcube commented already: https://news.ycombinator.com/item?id=10477109

This works too, at least on the site because the robots don't get too far apart:

    left
    left
    left 
    left
    left
    left
    left
    r: right
    skipNext
    goto r

With your code they end up right where they started? I see 'random locations' in the text above but the location is always the same here. Adding a couple of 'left's works, though, and is the same as my solution.

Edit: randomize button. I see. It also makes this no solution because they could start anywhere.

I think they meant:

    left x 6 # but that should probably be 7? as maxRange in the randomize routine is 8.
    scan: skipNext
    right
    goto scan

Which works but only because the unit test is deficient!

That's as far as I got in 5 mins [but I'm not a coder].

Wondering why all the developers are left leaning! ;) Here is a right leaning solution -

  walk:right
     skipNext
     goto walk
  run:right
    goto run

I have an answer for that: The example program is left leaning and we iterated from it to the actual solution. :)

How will you code it if "goto" took zero cpu-cycle ?

Clue - You will need to use both "left" and "right" movement.

Yeah, I'm assuming the interviewers either tell you how many cycles each instruction takes, or expect you to ask them. I had to tinker a bit to figure out which instructions cost a cycle and which didn't. Would certainly be much harder under pressure and without a cycle accurate simulator.

i did this in about 30 seconds because this remedial challenge was no match for my highly superior brain. jk it took me and 2 other people about 30 minutes to complete this using efficient code. much fun 10/10 would recommend too a friend. if i had any

# Useless example program start: left skipNext goto start goto hell

hell:left left goto hell

I wonder what you need to do to make the language and the associated VM Turing Complete.

Add an instruction that drops or picks up a parachute(i. e. it flips the state).

Then you should get something that is equivalent to boolfuck (1-bit brainfuck) which is Turing complete.

Great puzzle, took me some time to get it.

Reply on news.ycombinator.com