Daily Archives: June 20, 2016

Train Routing Problem

Problem Statement: Say 4 trains start at the same time. They may travel via same stations. Only one train can be there at one station at once. How should we achieve this using multi threading.

Solution:  I consider  this as an example of multi threading. Say, there are four trains (Train 1, Train 2, Train 3 and Train 4) which run between stations A,B,C,D and E.

We assume the following points :

  1. The train routes are single line. So, only one train can be there at one station at once.
  2. All the trains are stopping for a fixed interval in all the stations (5 seconds).
  3. All the trains start at the same time.
  4. All the trains travel at the same speed.

Following are the train routes :

Train 1 Route = A –> B –> E
Train 2 Route =  B –> C –> D
Train 3 Route =  A –> C –> E
Train 4 Route = A –> B –> C –> D –> E


 

import java.util.HashMap;

public class TrainRoutingProblem implements Runnable{

private char myroute[];
 static HashMap<Character,Character> stations = new HashMap<Character,Character>();
 
 
 public void setRoute(char[] myroute)
 {
 this.myroute = myroute;
 }

public TrainRoutingProblem()
 {

}

public synchronized void atStation(char c) 
 {
 stations.put(c, 'O');

try 
 {
 Thread.sleep(100);

} 
 catch (InterruptedException e) {
 System.out.println("Station "+c+" is occupied by "+Thread.currentThread().getName()+". Please wait..");
 }

stations.put(c, 'V');
 System.out.println(Thread.currentThread().getName()+" has left station "+c);
 }


 public void trainRun()
 {

for(char c:myroute)
 {
 System.out.println(Thread.currentThread().getName()+" is approaching station "+c);
 
 atStation(c); 
 
 }
 }

public void notifyJourneyStarted()
 {
 System.out.println(Thread.currentThread().getName()+" has started its journey.");
 }

public void notifyJourneyFinished()
 {
 System.out.println(Thread.currentThread().getName()+" has completed its journey.");
 }

public static void reset()
 {
 stations.put('A', 'V');
 stations.put('B', 'V');
 stations.put('C', 'V');
 stations.put('D', 'V');
 stations.put('E', 'V');

}

public static void main(String[] args) 
 { 
 char route1[]={'A','B','E'};
 char route2[]={'B','C','D'};
 char route3[]={'A','C','E'};
 char route4[]={'A','B','C','D','E'};
 
 TrainRoutingProblem routeObj = new TrainRoutingProblem();
 routeObj.setRoute(route1);
 
 Thread t1 = new Thread(routeObj);
 t1.setName("Train 1 Route 1");
 
 routeObj.setRoute(route2);
 Thread t2 = new Thread(routeObj);
 t2.setName("Train 2 Route 2");

routeObj.setRoute(route3);
 Thread t3 = new Thread(routeObj);
 t3.setName("Train 3 Route 3");
 
 routeObj.setRoute(route4);
 Thread t4 = new Thread(routeObj);
 t4.setName("Train 4 Route 4");
 
 TrainRoutingProblem.reset();
 
 t1.start();
 t2.start();
 t3.start();
 t4.start();
 
 }

@Override
 public void run() {
 notifyJourneyStarted();
 trainRun(); 
 notifyJourneyFinished();
 }
}
Output:

Train 3 Route 3 has started its journey.
Train 4 Route 4 has started its journey.
Train 1 Route 1 has started its journey.
Train 1 Route 1 is approaching station A
Train 2 Route 2 has started its journey.
Train 4 Route 4 is approaching station A
Train 3 Route 3 is approaching station A
Train 2 Route 2 is approaching station A
Train 1 Route 1 has left station A
Train 1 Route 1 is approaching station B
Train 2 Route 2 has left station A
Train 2 Route 2 is approaching station B
Train 3 Route 3 has left station A
Train 3 Route 3 is approaching station B
Train 4 Route 4 has left station A
Train 4 Route 4 is approaching station B
Train 3 Route 3 has left station B
Train 3 Route 3 is approaching station C
Train 3 Route 3 has left station C
Train 3 Route 3 is approaching station D
Train 3 Route 3 has left station D
Train 3 Route 3 is approaching station E
Train 3 Route 3 has left station E
Train 3 Route 3 has completed its journey.
Train 2 Route 2 has left station B
Train 2 Route 2 is approaching station C
Train 1 Route 1 has left station B
Train 1 Route 1 is approaching station C
Train 1 Route 1 has left station C
Train 1 Route 1 is approaching station D
Train 2 Route 2 has left station C
Train 2 Route 2 is approaching station D
Train 4 Route 4 has left station B
Train 4 Route 4 is approaching station C
Train 4 Route 4 has left station C
Train 4 Route 4 is approaching station D
Train 2 Route 2 has left station D
Train 2 Route 2 is approaching station E
Train 2 Route 2 has left station E
Train 2 Route 2 has completed its journey.
Train 1 Route 1 has left station D
Train 1 Route 1 is approaching station E
Train 4 Route 4 has left station D
Train 4 Route 4 is approaching station E
Train 1 Route 1 has left station E
Train 1 Route 1 has completed its journey.
Train 4 Route 4 has left station E
Train 4 Route 4 has completed its journey.

Note: This is very basic solution and needs to be enhanced to meet more scenarios. Till I find out a better approach “Keep Safe and Happy Coding 🙂 “…

Advertisements