Hacker News Reader

Comment by praptak | Hacker News Reader

A related puzzle - a robot is on an infinite line going both directions. Somewhere on this line there is a pebble which the robot has to find, which is only visible when robot crosses over it. The problem is that the robot doesn't know which way the pebble is.

Program the robot so that it finds the pebble, optimize for the distance traveled as the function of the initial distance between the robot and the pebble. The robot can tell the direction (say east from west) and measure the distance traveled.

View on HN

What's the statistical distribution for the location of the pebble? (Without that, the answer is "it depends"/undefined.)

Note that a uniform distribution isn't possible over an infinite line.

Agreed on the impossibility of the uniform distribution. Partially disagree on undefined: a function from the initial distance to the travel distance can be defined regardless of the distribution of the initial distance.

Go with any scale invariant distribution.

Great puzzle!

My strategy would be to move to positions 1, -2, +4, -8, 16, etc, then we get there in n + 2*(2^0 + 2^1 + ... 2^r) where 2^r < n.

(We always get there having moved n distance from the origin as our last step, otherwise we travel back to the origin spending distances 2, 4, 8, 16, etc. The sum (1, 2, ... 2^r) = 2^(r+1)-1; We double that again to get ~2^(r+2)

An example of the worst case, we lie on a number of the form -(2^r + 1) we might round-trip to +16 before heading down to -9. In that case we'd travel 2,4,8,16,32 + 9 = 71 steps.

Best case, say we lie on a number of the form 2^2r, e.g. 64.

We travel 1, -2, +4, ... , -32, 64.

We've travelled 127 steps.

Overall this takes method travels approximately between 2n and 8n.

I'm not sure how this compares to 1, -1, 2, -2, 4, -4; That has a better worst case.

> Best case, say we lie on a number of the form 2^2r, e.g. 64.

> We travel 1, -2, +4, ... , -32, 64.

> We've travelled 127 steps.

I think it's 190 = 64+2*(2^0+2^1+2^2+2^3+2^4+2^5) = 64+2+4+8+16+32+64

> Overall this takes method travels approximately between 2n and 8n.

I think asymptotically the range is [3n,9n]

Reply on news.ycombinator.com