Cheap and Secure Web Hosting Provider : See Now

[Answers] An algorithm for making 2 carts meet

, , No Comments
Problem Detail: 

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:

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

Variables, loops and not (!) are usable.

the given solution is:

for i=1 to infinity:

  1. go left i steps.

  2. if underlamp stop.

  3. 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:

  1. go right.
  2. go right.
  3. go left.
  4. if underlamp goto 6.
  5. goto 1.
  6. go right.
  7. 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:

  1. go right i steps.

  2. if underlamp goto 4.

  3. go left.

4.for j=1 to infinity:

  1. go right j steps.
Asked By : Trinarics

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/21705

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback