7 ms·
Show HN: Parachuting robots – a programming puzzle
- trymas 11y agoWow, 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 11y agoThank 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 11y agoAnswering 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 11y agoGreat suggestion, thanks! I added (state-dependent) mouse-over tooltips for all buttons.
- rplnt 11y agoHow 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 11y agoI used two labels.
- jmcannon 11y agoI used two.
- kanche 11y agoI made it through with two [0] [0] https://gist.github.com/kanche/92c92c5e926ebc66da68 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
- samsaga2 11y agoMy solution: http://pastebin.com/FqgCAXKA http://pastebin.com/FqgCAXKA
- Lewton 11y agoI'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 11y agoIs 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 11y agoAt 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 11y agoThat interview question seems related to the "how to detect loops in a potentially infinite list" question which I was asked at least once.
- andrelaszlo 11y agoDid you solve it?
- sugarcube 11y agoThe interview question back then, no. But I remember the solution so I could solve this robot problem quickly :-)
- zuck9 11y agoThis 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 11y agoWith 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 11y agoI 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 11y agoHere'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 agoHa! That's what I thought. It's a duct-taping solution.
- iconjack 11y agoThis 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 agoHere 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 agoYou 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. :)
- Geee 11y agoGreat puzzle, took me some time to get it.
- bvenkysubbu 11y agoWondering why all the developers are left leaning! ;) Here is a right leaning solution - walk:right skipNext goto walk run:right goto run
- odabaxok 11y agoI have an answer for that: The example program is left leaning and we iterated from it to the actual solution. :)
- somehnreader 11y agoFantastic 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 11y agoI 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 11y agoIs it possible to make them go inward to each other instead of chasing?
- chki 11y agono, 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 11y agoI 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 11y agoTook me about 2 minutes to come up with: start: left left right skipNext goto start continue: left goto continue
- jonsen 11y agoAnd 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 11y agoI wonder what you need to do to make the language and the associated VM Turing Complete.
- symmetricsaurus 11y agoAdd 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 11y agoHere 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 11y agoTiming of the left command would depend on robot mechanics, not the processor clock.
- vinody 11y ago# Useless example program start: left skipNext goto start goto hell hell:left left goto hell
- deleted 11y ago[deleted]
- vk0 11y agoHow will you code it if "goto" took zero cpu-cycle ? Clue - You will need to use both "left" and "right" movement.
- drewm1980 11y agoYeah, 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 11y ago[deleted]
- JacobTuttle 11y agoi 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