5

Question:

There is an infinite line. You are standing at a particular point you can either move 1 step forward or 1 step backward. You have to search for an object in that infinite line. Your object can be in any direction. Give an optimal solution

My approach:

       Go 1 step forward, 2 step back ward 
       Go 2 step forward, 4 step back ward and so on

Complexity:

Lets say the required object is at point n.

Total number of steps: 

 3 + 6 + 9 + .... n
 = 3(1 + 2 + 3 ... n)
 = O(n^2)

Is there a way to improve the efficiency?

12
  • 3
    +1 step, -2 steps, +2 steps = +1 step.. kinda pointless don't you think? What about (-1)^i * 2^i steps instead ?
    – Frank
    Commented Sep 5, 2013 at 5:43
  • Got your point! I can increment it in power of 2. Whats (-1)^i?
    – Chander Shivdasani
    Commented Sep 5, 2013 at 5:54
  • 7
    clone yourself and walk in both directions at once, no backtracking required
    – Steven A. Lowe
    Commented Sep 5, 2013 at 14:49
  • 2
    This problem is not solvable without some statistical details about where the object might be. As it stands, the best solution is one that never wastes time revisiting old points, and thus counterintuitively is to go one direction only. (With a 50% chance of being wrong, and as someone else noted, having essentially no chance of finding it if the object can be anywhere on the line with equal chance.) In order to be solvable, either the line has to be finite or the position of the object must be more likely to appear on some points than others.
    – user53141
    Commented Sep 5, 2013 at 15:35
  • 1
    I think this question would be better on cs.stackexchange.com.
    – Jan Hudec
    Commented Sep 6, 2013 at 5:52

4 Answers 4

Reset to default
6

What do you mean by 'optimal solution' ?
Make as few steps as possible?
I would not increase the distance from the start point by 1 every time, because after some time you nearly always visit a position you already visited and the ratio of new visited points converges to 0. I would use a pattern that guarantees that we always visit a fixed ratio of new points.
E.g
r: right step
l: left step 

                x
                 r              new: 1   old: 0
               ll               new: 2   old: 1
                rrrr            new: 4   old: 3 
           llllllll             new: 8   old: 7
            rrrrrrrrrrrrrrrr    new:16   old:15

This way the ratio of already visited positions to new visited positions id always about 1:1.

1
  • Can you elaborate a bit on the complexity?. Looking at the series, total number of steps are: 2^0 + 2^1 + 2^2 .... n, where n is the point where the required element is located. Whats the big-oh complexity?
    – Chander Shivdasani
    Commented Sep 5, 2013 at 17:59
5

An exponential growth strategy runs O(n) time, average and worst case. This is optimal if you disregard constant factors. If you want to optimize the constant factor as well, you need to make some assumption about the probability distribution.

For example if you use a doubling strategy, the maximal cost is 7*n

dist = 1
loop
    MoveTo(dist)
    MoveTo(-dist)
    dist = dist * 2
9
  • Correct, but with one proviso. The question does not say whether integral variable is available and on Turing Machines it usually isn't.
    – Jan Hudec
    Commented Sep 6, 2013 at 5:57
  • Can you explain how the run time of exponential growth is O(n)?
    – Chander Shivdasani
    Commented Sep 7, 2013 at 8:01
  • This expands nice and fast. But how does bracketing the object help when other steps are empty? How do you even know when you've bracketed it? If there is a way I don't see it in the question. Isn't that an assumption?
    – candied_orange
    Commented Nov 30, 2016 at 0:05
  • @CandiedOrange My assumption is that the walker will know when they find the object.
    – CodesInChaos
    Commented Nov 30, 2016 at 8:05
  • @CodesInChaos is it correct then that your moveto() moves one step at a time until it reaches dist?
    – candied_orange
    Commented Nov 30, 2016 at 8:08
0

Assuming:

  • Each step costs time
  • There is no predicting where this object is on the infinite "line" of steps
  • That you can't fork or clone your self
  • That you only gain more information once you're on the object (no hints as you go)

Then pick a direction at random and just start walking. No expensive backtracking. Sure it might be one step behind you but that's just the end of infinity right there.

O(n)

14
  • This algorithm has a chance of never terminating so it's not O(anything). The exponential reversing solution is O(n) - why is this method better?
    – Reinstate Monica
    Commented Nov 29, 2016 at 22:21
  • Any algorithm searching for an object on an infinite line has a chance of never terminating. Exponential is exponentially expensive if each step costs time. Even if it isn't all you're doing is scrambling infinity before you check each step 1 at a time. If there were information to gain from misses exponential would be a good start to a binary search. We weren't offered any hints as we go. A miss is just a miss.
    – candied_orange
    Commented Nov 29, 2016 at 22:25
  • I think you aren't taking the time to think through this problem or understand the exponential algorithm. The exponential algorithm does terminate always, and its running time is proportional to the magnitude of the position of the object.
    – Reinstate Monica
    Commented Nov 29, 2016 at 23:24
  • @Solomonoff'sSecret I think you're making assumptions about the problem that it never states. Chief among them is random access. As for stopping, my sin is the same as the exponential. I miss the object behind me. Exponential misses the object when it's not on the powers of 2. Even if you cover everything in both directions you miss the object that's halfway to infinity because the sun burned out.
    – candied_orange
    Commented Nov 29, 2016 at 23:54
  • 1
    @Solomonoff'sSecret so long as n>i nothing can guarantee to terminate. You're randomly obsessing on the area where you started when you've been given no reason to. Before the first move there is an equal chance of finding the object to the left and to the right. It's just as efficient to go either way. As soon as you make that first move there is zero chance of finding it by moving back one step. That move is wasteful. Do that even once and you're forever behind the "just start walking" approach.
    – candied_orange
    Commented Nov 30, 2016 at 3:59
-2

On an infinite line you will never find the object. Infinity is a weird thing. i.e. pick a point on a finite line, as the length of the line approaches infinity the probability that the point you picked is the object approaches zero.

Some things that might make this problem meaningful

  1. The line is finite (some number N)
  2. The object can only be at discrete points.

I would image that in these cases the optimal (fewest number of steps) solution would be to walk in one direction until you find the object or reach the end. If you reach the end you would turn around.

3
  • 1
    the object has to be a finite distance from your start position the line itself can still be infinite though
    – jk.
    Commented Sep 5, 2013 at 15:23
  • 1
    -1: Turing machines always feature (countable) infinite tape. Anything that lies on such tape lies in finite distance, because every distance between concrete elements on an infinite tape is finite. The infinite tape is important, because on a finite tape you can run to one end, than to the other, but on an infinite one you can't, because you'll never reach the end.
    – Jan Hudec
    Commented Sep 6, 2013 at 5:45
  • 1: Having a finite line would not matter if we consider the reals. [0, 1] is just as impossible to enumerate as (-inf, +inf). 2: Really all you need is a line that is a subset of a countable set (for example, the rationals).
    – Thomas Eding
    Commented Sep 8, 2013 at 2:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.