Hackety Hacking Problem Making robots meet

Problem Statement

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.

Sample Output

The linked list is..(path)
11 21 31 41 51

The linked list is..(path)
1 2 3

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

The linked list after the common node is established are
The Linked list is..(path)
11 21 31 41 51

The Linked list is..(path)
1 2 3 11 21 31 41 51

They meet at 21

Curriculum Connections

This problem gives student help in understanding things mentioned below:

• How to make use of the concept of Linked List

Solution in C++

Solution: Code tested on TC++ 3.0 Compiler
#include <stdio.h>
 #include <conio.h>
 #include <stdlib.h>// 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);

}