3 ms·

Here's my best implementation: start: left skipNext goto start fast: left goto fast Red and Blue must take three cycles to mov

by moftz 11y ago

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.

nyan4 11y ago
"It seems to originate from a Microsoft interview question." Using inefficiency to solve problems, I'm not surprised.
- nothis 11y ago
  Ha! That's what I thought. It's a duct-taping solution.
- iconjack 11y ago
  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.
verroq 11y ago
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.
- kanche 11y ago
  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. :)
Fiahil 11y ago
I come up with the exact same with 'right' instead of 'left' :D
jack9 11y ago
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.

by moftz 11y ago

nyan4 11y ago

"It seems to originate from a Microsoft interview question." Using inefficiency to solve problems, I'm not surprised.

nothis 11y ago
Ha! That's what I thought. It's a duct-taping solution.
iconjack 11y ago
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.

verroq 11y ago

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.

kanche 11y ago
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. :)

Fiahil 11y ago

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

jack9 11y ago

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.