HN Explorer

57 comments

[ 4.1 ms ] story [ 121 ms ] thread
trymas
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.

sharkdp
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?

trymas
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.

sharkdp
Great suggestion, thanks! I added (state-dependent) mouse-over tooltips for all buttons.
rplnt
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.

alexmic
I used two labels.
rplnt
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)

kanche
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

lucb1e
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.
Lewton
... Without labels? Can you show that solution? Are you sure it works for robots placed on an infinite line?
lucb1e
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

samsaga2
My solution: http://pastebin.com/FqgCAXKA
Lewton
That can be cleaned up considerably.

2 labels, and 5 statements

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

http://pastebin.com/ZcLdJhzN

Lewton
remove one "left" from the speed label :D
esolyt
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.

Lewton
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 :)

progx
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
citeguised
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…
sugarcube
That interview question seems related to the "how to detect loops in a potentially infinite list" question which I was asked at least once.
andrelaszlo
Did you solve it?
sugarcube
The interview question back then, no. But I remember the solution so I could solve this robot problem quickly :-)
zuck9
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
lucb1e
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.

pbhjpbhj
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].

moftz
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
"It seems to originate from a Microsoft interview question."

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

nothis
Ha! That's what I thought. It's a duct-taping solution.
iconjack
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
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
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
I come up with the exact same with 'right' instead of 'left' :D
jack9
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.

Geee
Great puzzle, took me some time to get it.
bvenkysubbu
Wondering why all the developers are left leaning! ;) Here is a right leaning solution -

  walk:right
     skipNext
     goto walk
  run:right
    goto run
odabaxok
I have an answer for that: The example program is left leaning and we iterated from it to the actual solution. :)
somehnreader
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, ...

sireat
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.

fouadf
Is it possible to make them go inward to each other instead of chasing?
chki
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.
typicalbender
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.
Beltiras
Took me about 2 minutes to come up with:

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

jonsen
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.
Beltiras
I wonder what you need to do to make the language and the associated VM Turing Complete.
symmetricsaurus
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.

meshko
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?
jonsen
Timing of the left command would depend on robot mechanics, not the processor clock.
vinody
# Useless example program start: left skipNext goto start goto hell

hell:left left goto hell

[deleted]
(comment deleted)
vk0
How will you code it if "goto" took zero cpu-cycle ?

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

drewm1980
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.
[deleted]
(comment deleted)
JacobTuttle
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