CareerCup

Can the robots communicate with each other?

One important point is same program will be running in both robots. So two possibilities are there...
a) Robots should be able to send the message between each other any number of times....
In this case, each robot will randomly chose a direction to go and send the chosen direction to other robot. If robots detect that they have same direction, then they will again choose the direction randomly. They will keep doing it until they don't have opposite directions. After this they can move until they don't find the point.

b) Each robot knows the distance between two ends of line.
Lets say distance between robots is d. In this case, each robot will again select random direction and will move in that direction until it doesn't find the point or distance moved is less than d. if it couldn't find the point then reverse the direction and start moving in other direction until couldn't find the point.

How about this:
{{
void robotAction()
{
int left = 0;
int right = 0;

while(! amIonPoint())
{
right = 0;
while(! amIonPoint() && left >= right)
{
moveRight();
right++;
}

left = 0;
while(! amIonPoint() && left <= right)
{
moveLeft();
left++;
}
}
}
}}

both will go in one direction, say left or right. When one is on point, it will move with twice speed.
for e.g. the piece of code could be,
function meet() {
do {
move right;
}
while (! onThePoint);
for(;;) {
move right;
move right;
}
}

y has'nt nybody explaind the answer to the puzzle correctly

initially robot can aligned their direction as explained by tito then move left, move right, move right, move left and continue in the same fashion..this way robot will be able to move forward. because if they are facing then the left will take him 90 degree from line and right from their parallel to the line one step ahead and so on...
plz comment

Lets take case of one robot. Here is the algorithm
1. Check whether current point is the desired point by using AmIPoint()
2. If yes, program ends, Robot found the point, Exit. Else, go to step 3.
3. MoveLeft()
4. MoveRight()
5. MoveRight(). Robot is now on the next point on the line. Go to step1.

Repeat the above steps for Robot 2.

My friend came up with a better solution. Its by defining intial condition. Both robots will start from each end of the line facing away from each other and in a perpendicular direction to the line. EX: Suppose line is drawn from north to south. Robot1 will be in north end of the line facing towards east whereas Robot2 is at the other end facing West. With this simple algorithm will be...

while(!AmIpoint())
moveright();

The algo needs to be same for both robots. So i'll give one instance.

/*
** check current position.
** move left once, check.
** move right twice, check
** move left thrice, check
** move right four times, check
** and so on....
*/

void MoveRobot2Point()//function to move the robot to the point on the line
{
	unsigned int i=0;//used for storing how may times the robot shud move to the left/right
	unsigned int backup_i;//backup of i, as i will be manipulated in the loops

	while(1)//keep looping until the robot reaches the point
	{
		backup_i = i;

		while(i)//move left, i# of times 
		{
			MoveLeft();
			--i;
		}

		if(AmIOnPoint())//check if robot on point and return if true
			return;

		i = ++backup_i;
		while(i)//if point not reached then increment i, and this time move right i# of times
		{
			MoveRight();
			--i;
		}

		if(AmIOnPoint())//check if u are on point and return
			return;

		i = ++backup_i;
	}

}

Make one robot face to you, another's back towards you. Now they can use same program perfectly.

Lets Take line is in North and south, if robos are placed 45 degress (i.e. North side robo will be faced to West side and south side robo will be placed in East side). Then Make a move of Right and then left until it reaches to the point

if they can communicate then after one reaches one point the other can simply ask for directions

If the line is from North to south .The following 3 scenarios are possible.
1.the point can be in between the two robots.
2.north to the end of first robot
3.south to the end of 2nd robot.
Initially the first robot towards the north will face towards east and the other towards west.both the robots will move right until amion point is true.or else they will meet at one point in between.then both will turn to one direction and move right or left till they reach the point

A more logical solution. Assuming available instructions :
MOVE F ( move forward)
MOVE B ( move backward)
IF(P) (condition satisfied if any of the two starting points reached there is no THEN to this)

code:

A:MOVE F
  IF(P)
   GOTO B
  GOTO A

.
.
. 
B: MOVE F
   GOTO B

both robots run the same code concurrently. First MOVE F moves both the robots in forward direction(same) i.e. get them off their starting points. Thus both of these robots are stuck in the A loop until one of the robot reaches the starting point of the robot moving in front of it. Only this robots' IF(P) condition gets satisfied and it moves into the B loop which is again making it move forward.
Now both the robots are moving in forward direction but one is in loop A and one is in loop B and we see that it takes a lil more time to execute loop A iteration coz of executing the extra condition in A than it is the case in B. Thus they will meet eventually due to some time difference in executing each of the two loops' iterations.

A variation of this problem is given in How to Ace the Brainteaser Interview Question book.

the algorithm is correct to move left 1 then right 2 then left 3, ...but not optimal.
say the robots are 100 apart then it requires 1+2+3+...50 = order(n**2) moves.
instead of increasing by 1 each itteration increase by a factor of 2.

left 1
right 2
left 4
right 8
...

{{
int moveAmount=1;
while !met(){
left(moveAmount);
moveAmount*=2;
right(moveAmount);
mooveAmount*=2;
}//while
}}

<-A
      |
      |
      |
       B->

Command: Move left until 'I am on the point'

Fabergas solution is elegent but I don't think you can use anything other than a sequence of LLLLRRRRLLLRRR etc.
Here's my solution with a an assumption: I can turn off the robots if I choose.
Let robots A and B be n steps apart and my position be x steps from the rightmost robot (B):
A____________X_____B
Now feed this program into both those robots:
MOVE L (x times)
MOVE R (n times)
As B moves x steps, it reaches me and I turn it off. While A starts to backtrack n steps and reaches me.
Without this tweak (switching off) I don't think it is possible to answer this question.

I had a very similar question asked during my fourth interview with a company today.

Two robots land on an infinitely long line on top of their parachutes.
You have a total of 6 possible commands
left //move left 1 position
right //move right 1 position
check //which will return true if the bot is on top of a parachute or false otherwise
while // loop
! // not
if //
The bots move at the same exact speed
no variables may be used
there is no communication between the bots
both bots will run the same program
neither will have any knowledge of the others position

This is the solution that I eventually came up with

// get the bots off of their own parachutes
left
// find the other parachute moving slowly two forward one back
while( !check)
    left
    left
    right
// parachute found while loop exits
left // get off the other bots parachute
while(!check) // infinite loop moving quickly to left eventually resulting in the two bots meeting
	left

The question was asked in the last 20 minutes of an hour long interview and I failed to come up with a solution until 15 minutes after the interview ended.

This seems like the type of question that will take a few minutes to complete if you've seen the question at some point in the past few years and if you haven't you will fail.