0

I know this has asked before but I couldn't make anything out of the answers so I hope someone will be able to explain this to me in a really easy way....

The Problem:

A man is standing in front of a wall with an infinite length. On the other side of the wall is a town he's trying to get to. Somewhere in the wall is a gate and the guy can either go left or right to find it.

I need to write an algorithm with a linear runtime and I am just not able to figure this out... Any help is greatly appreciated!

Kara
  • 6,115
  • 16
  • 50
  • 57
Chris
  • 391
  • 2
  • 6
  • 17
  • Is this homework? (Please tag it as such if it is). What did you try so far? And there are some pretty good answers to this on SO already. What did you not understand? – Bart May 04 '11 at 12:15
  • 1
    What is considered a unit of time for this problem? One step? Or an arbitrary number of steps in the same direction? – Himadri Choudhury May 04 '11 at 12:22
  • Yea I created the homework tag. I understand that you have to alternate left and right because if you just go in one direction there's a could chance that you'll be searching forever. So I would go one step to the left two to the right and so on... But then you get an exponential runtime. Someone wrote that you have to use and exponential spiral but i have little or no idea what that means. – Chris May 04 '11 at 12:23
  • is the minimum size of the hole known ? Are the positions the man can take discrete or continuous ? – Andre Holzner May 04 '11 at 12:23
  • I'm sure you have already seen this, but I think it gives a pretty decent explanation: http://stackoverflow.com/questions/3633110/algorithm-to-find-hole-in-an-infinite-one-dimensional-graph – Bart May 04 '11 at 12:25

5 Answers5

3

He has to try both sides. However, if he just goes a constant new length in each direction, it will become a "Schlemiel the painter" problem. He needs to increase the new length he walks in each direction in an exponential fashion, so that the amortized time of searching becomes linear. You will have to work out the details and how they translate to the complexity formulae.

Svante
  • 50,694
  • 11
  • 78
  • 122
1

Not sure how to hint the answer without just giving it away.

You know you can't go "infinitely left", then if that fails go right until you find the door. That's out.

So to find the door at all, you're going to have to go left for a bit, then turn and go back to the start, go right a bit, repeat with larger and larger bits.

The question then is, can you think of a way to increase the size of the "bits" such that the overall runtime, i.e. the total of all the "bits" up to the one that's big enough to find the door, is linear?

You've already said in a comment that if you increase by 1 each time, then the complexity is too high (O(n^2) actually, not exponential, but still too big). So look for a better progression, one that will result in less total to-ing and fro-ing.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
0

As posed, it's not possible, because if he goes the wrong way, he'll spend an infinite amount of time searching. If he can teleport, it's easy - every N metres, he can teleport to the other side of his start point, search for N metres, then teleport back and repeat. This becomes a linear search.

regularfry
  • 3,248
  • 2
  • 21
  • 27
  • I'm assuming the OP means that moves can go either left or right. Not that after a step left it is no longer possible to step right. – Bart May 04 '11 at 12:23
0

If the man is going alternatively left and right, in increasing intervals, he will eventually hit the gate. But I don't know if this complies to the "linear runtime".

Here is an example of what I mean:

1. he goes 1 km left
2. he goes 2 km right, being 1 km right of where he started
3. he goes 3 km left, being 2 km left of where he started
4. he goes 4 km right, being 2 km right of where he started
5. he goes 6 km left, being 4 km left of where he started
6. he goes 8 km right, being 4 km right of where he started

This is my idea for the algorithm, but I'm sure there are many optimizations possible.

Enduriel
  • 111
  • 3
0

My first idea is: the man moves along a Archimedean spiral centered in its original position. Assuming that the hole is larger than the distance between two successive turns of the spiral, the man will eventually find it.

Also look at answers to this question

Community
  • 1
  • 1
MarcoS
  • 13,386
  • 7
  • 42
  • 63
  • The length of the spiral is still quadratic in the radius, though, and I don't think this will change much if you flatten the spiral to one-dimensional. – Paŭlo Ebermann May 04 '11 at 12:41
  • @Paŭlo Ebermann: true. However, a wall is bidimensional, and I can't think of a way of exploring it in a less-than-quadratic way. The spiral is actually a trick to ensure that I explore each wall location (in terms of cartesian or polar coordinates) only once. – MarcoS May 04 '11 at 12:55
  • The OP did specify a one-dimensional graph. I think the idea is that the wall is streching vertically out of the ground, and the man walks left or right, looking for a door at ground level. – Cephron May 04 '11 at 15:10
  • @Cephron: in that case I think the answer has already been given: I edited my answer adding a link – MarcoS May 04 '11 at 15:40