An algorithm for making 2 carts meet Say I have 2 carts on an infinite railroad, each cart is initially under a lamp.
There are only 2 lamps, and they are at a fixed location, hence they don't change their location. The distance between them is D, but its not known.
Each cart has a processing unit, both will execute a copy of the same program once the whole system is "initiated".

The task: to write a code in pseudo-code, which will make the 2 carts collide.

Restrictions:
The following commands can be used:


  
  move left/right *insert_number_here* steps //each movement takes 1 clock cycle, meaning that "move left C steps takes C clock cycles
  if underlamp *put_instruction_here* //if the cart is under a lamp
  goto *number_of_line_here*
  stop
  


Variables, loops and not (!) are usable.

the given solution is:


  for i=1 to infinity:
  
  
  go left i steps.
  if underlamp stop.
  go right i steps.
  


Now, I need a hint to help me make a simple improvement to the algorithm that is given in the trivial solution, so when the distance between the lamps is D, the total number of steps of both carts will be a first order polynomial function of D.

My lecturer gave the following solution, and told me to improve the given code using a different idea.
This is his solution:


  
  go right.
  go right.
  go left.
  if underlamp goto 6.
  goto 1.
  go right.
  goto 6.
  


My improvement of the given code, but I'm not sure that in this one, the total number of steps is a first order polynomial function of D.


  for i=1 to infinity:
  
  
  go right i steps.
  if underlamp goto 4.
  go left.
  
  
  4.for j=1 to infinity:
  
  
  go right j steps.
You asked for a hint.  OK, here goes:

Obviously, we don't know $D$ (otherwise the problem is too easy).  But suppose we do know an upper bound $U$ on $D$.  In other words, suppose we know an integer $U$ and are promised that $D \le U$.  Then it is possible to build a solution whose running time is a low-order polynomial of $U$.  In fact, it is possible to build a solution whose running time is $O(U^2)$.  Take a close look at your professor's algorithm (the one labelled "the given algorithm"), and think for a bit, and maybe you'll see how to accomplish this.

But what about the fact that we don't know the value of $U$?  Well, you might ponder the sequence $1,2,4,8,16,32,\dots$.  I'm being deliberately terse here since you asked for a hint, but if you ponder on this, I think you'll be able to find an algorithm that it meets all your criteria.