Two Robots, who cannot communicate with each other, are present on an infinite long railway track. Can you suggest a way of how they can meet each other? (Provided they cannot move in opposite directions!). How can they judge whether they are moving in the right direction.


HINT: They can use a Marker/Paint. Can you think about the solution now?


Annotations

The situation is similar to a problem of two linked lists having a common node between them. Our goal is to find the common node. So, what we do is very simple. Instead of using a linked list with data and a pointer to next node, we add a third element to it. When we traverse first linked list, we paint this element (Suppose Assign it 1). Therefore when we traverse the second list, wherever 1 is found we find the common node of the two linked lists and hence the intersection point (meeting point) of the two robots whose linear motions along a railway track is similar. Both the robots will mark the track with the marker, and the robot who finds the other marker will now justify that he was moving in the same direction.

Solution

Code tested on TC++ 3.0 Compiler

#include 
#include 
#include  // Contains malloc.h used for allocating memory to a pointer.
void display(struct node*);
void add(struct node**,int);
void copy(struct node**, struct node**, int);
void detect(struct node**, struct node*);
struct node
{
   int data,paint;
   struct node* link;
};
void main()
{
   struct node *p,*p1;int i;
   clrscr();
   p = NULL;p1 =NULL;

add(&p1,1); add(&p1,2);add(&p1,3); add(&p,11); add(&p,21); add(&p,31); add(&p,41); add(&p,51); add(&p,61); display(p);display(p1); // p contains 11,21,31,41,51,61 and p1 contains 1,2,3

printf("\nNow Enter the location w.r.t to 1st list \nat which both lists should have a common node\n"); scanf("%d",&i); copy(&p1,&p,i); // We have entered 2 in dummy run of this code means p1's last node links to p's second node. printf("\nThe Linked Lists after a common node is established are\n"); display(p);display(p1); detect(&p,p1);// The common mode is detected and its value is printed. getch(); }

void add(struct node** p,int n) { struct node* temp; struct node* r;

if(*p == NULL) { temp = malloc(sizeof(struct node)); temp->data = n; temp->link = NULL; temp->paint = 0; *p = temp; return; } else { temp = *p; while(temp->link!=NULL) temp = temp->link; r = malloc(sizeof(struct node)); r->data = n; r->link = NULL; r->paint = 0; temp->link = r; return; } } void display(struct node* p) { struct node* temp; temp = p; printf("\n The Linked List is..(path)\n"); while(temp->link!=NULL) { printf(" %d ",temp->data); temp = temp->link; } printf(" %d\n",temp->data); }

void copy(struct node** t1, struct node** t, int n) { struct node *temp,*temp1;int i; temp = *t;temp1 = *t1; for(i=1;i<=n-1;i++) { temp = temp -> link; } while(temp1->link!=NULL) temp1 = temp1->link; temp1 ->link = temp; }

void detect(struct node**t, struct node *t1) { struct node *temp; temp = *t; while(temp!=NULL) { temp->paint =1; temp = temp->link; } while(t1->paint!=1) t1 = t1->link; printf("\n\t\t\t\tThey meet at %d\n",t1->data); }


Sample Output

The Linked List is..(path)
11   21   31   41   51

The Linked List is..(path)

2 3

Now Enter the location w.r.t. to the 1st list at which both lists should have a common node 2

The Linked Lists after a common node is established are

The Linked List is..(path) 11 21 31 41 51

The Linked List is..(path)

2 3 21 31 41 51

They meet at 21

Non-profit Tax ID # 203478467