1
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ (1) I don't understand the deal with the lamps. Are the lamps at a fixed location, or do they move with the carts? What does "if underlamp" mean? What am I allowed to do with variables? Can I have "if expression then goto line"? (2) What have you tried? We expect you to make a serious effort first and to show us what you have tried. Pasting a copy of your homework exercise is not on-topic for this site, but if you have made a serious effort and gotten stuck part-way, a specific question about a specific aspect of your solution might be more suitable. $\endgroup$ – D.W. Feb 16 '14 at 20:31
  • $\begingroup$ (1) The lamps are at a fixed location. if underlamp means if the cart is under a lamp right now I have tried making a few algorithms, which were all pretty wrong because our lecturer told us not to use algorithms that slow down one of the carts but I have come to something and I don't know if the total number of steps is a first order polynomial. I will post it right away. $\endgroup$ – HaloKiller Feb 16 '14 at 20:34
  • $\begingroup$ Hint: there is a solution in which the carts meet after 2D time units, and doesn't require the processing units to store unbounded integers. $\endgroup$ – James Youngman Feb 23 '14 at 0:20
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is my solution any good? If it isn't, can you give me a bigger hint about your sequence? $\endgroup$ – HaloKiller Feb 17 '14 at 8:27
  • $\begingroup$ Well, do you mean multipliying i by 2 instead of raising it by 1? If so, does it work with multipliying it by 3? And how do i count the number of steps? $\endgroup$ – HaloKiller Feb 17 '14 at 11:23
  • $\begingroup$ There is a solution which doesn't require us to know U, and in fact doesn't require us to be able to store U in the processing unit. $\endgroup$ – James Youngman Feb 23 '14 at 0:23
  • $\begingroup$ @JamesYoungman, yes, I know, I was hinting at a solution that doesn't require us to know U. But the original poster asked for hints, so I didn't spell out the full details of the solution. $\endgroup$ – D.W. Feb 23 '14 at 9:50

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