Here is the solution to question no 1 of MGPT 2007....

MGPT 2007 question no 1 :

smaller code (75 lines):
This code I developed after the MGPT............
I subitted the second question in MGPT....
There is another post containing that code......

import ncst.pgdst.*;
class Router{
String rule[][]=new String[20][7];
int row;
static SimpleInput in=new SimpleInput();
void input()throws IOException{
row=in.readInt();
for(int i=0;i rule[i][0]=in.readWord();
for(int j=1;j<6;j++)
rule[i][j]=in.readWord();
if( ! rule[i][0].equals("FORWARD"))
rule[i][6]="XXXXXXXXXXXXXXXXXXXXXXX";
else
rule[i][6]=in.readWord()+" "+in.readWord();
}
sort();
}
void sort(){
int index=-1;
String rule1[][]=new String[20][7];
for(int i=0;i if(rule[i][0].equals("REJECT"))
rule1[++index]=rule[i];
for(int i=0;i if(rule[i][0].equals("ACCEPT"))
rule1[++index]=rule[i];
for(int i=0;i if(rule[i][0].equals("FORWARD"))
rule1[++index]=rule[i];
rule=rule1;
}
String respond(String ip){
int octet[]=new int[6];
int index=ip.indexOf(".");
octet[0]=Integer.parseInt(ip.substring(0,ip.indexOf(".")));
ip=ip.substring(index+1);
octet[1]=Integer.parseInt(ip.substring(0,ip.indexOf(".")));
ip=ip.substring(index+1);
octet[2]=Integer.parseInt(ip.substring(0,ip.indexOf(".")));
ip=ip.substring(index+1);
octet[3]=Integer.parseInt(ip.substring(0,ip.indexOf(" ")));
octet[4]=Integer.parseInt(ip.substring(ip.indexOf(" ")+1));
int pos=-1;
boolean acpt,reje,fwd;
for(int i=0;i boolean go[]=new boolean[5];
for(int j=0;j<5;j++)
if(rule[i][j+1].equals("*"))
go[j]=true;
else if(rule[i][j+1].indexOf("-") != -1){
int f=Integer.parseInt(rule[i][j+1].substring(0,rule[i][j+1].indexOf("-")));
int s=Integer.parseInt(rule[i][j+1].substring(rule[i][j+1].indexOf("-")+1));
if(octet[j]>=f && octet[j]<=s)
go[j]=true;
}else if(octet[j]==Integer.parseInt(rule[i][j+1]))
go[j]=true;
if(go[0]==true && go[1]==true && go[2]==true && go[3]==true && go[4]==true){
if(rule[i][0].equals("REJECT")) return "REJECT";
else if(rule[i][0].equals("ACCEPT")) return "ACCEPT";
else if(rule[i][0].equals("FORWARD")) return rule[i][6];
}
}
return "REJECT";
}
public static void main(String[]args)throws IOException{
Router router=new Router();
router.input();
int n=in.readInt();
for(int i=0;i String ip=in.readWord()+" "+in.readWord();
System.out.println(router.respond(ip));
}
}
}



If you are unable to see the program in a proper format, please click this link
http://chandra-shekhar.spaces.live.com/default.aspx

This is another solution to MGPT 2007 question no 1.....

MGPT 2007 question no 1 ...
This is the first version that I made (232 lines)

import ncst.pgdst.*;
class IP{
int octet[],port;
IP(){
octet=new int[4];
}
void input(SimpleInput in)throws IOException{
String str=in.readWord();
int kk=-1;
do{
int k=str.indexOf(".");
if(k==-1){
octet[++kk]=Integer.parseInt(str);
break;
}
octet[++kk]=Integer.parseInt(str.substring(0,k));
str=str.substring(k+1);
}while(str.length() != 0);
port=Integer.parseInt(in.readWord());
}
public String print(){
String str="";
for(int i=0;i<4;i++){
str += octet[i] + ".";
}
str += " "+port;
return str;
}
}
class IPRange{
String octetRange[],portRange;
IPRange(){
octetRange=new String[4];
}
void input(SimpleInput in)throws IOException{
for(int i=0;i octetRange[i]=in.readWord();
}
portRange=in.readWord();
}
}
class Rule{
IPRange ipRange;
Rule(){
ipRange=new IPRange();
}
void input(SimpleInput in)throws IOException{
ipRange.input(in);
}
}
class RejectRule extends Rule{
}
class AcceptRule extends Rule{
}
class ForwardRule extends Rule{
IP forwardTo;
void input(SimpleInput in)throws IOException{
super.input(in);
forwardTo=new IP();
forwardTo.input(in);
}
}
class Router{
RejectRule[] rejectRule;
AcceptRule[] acceptRule;
ForwardRule[] forwardRule;
int rejectRuleCount,acceptRuleCount,forwardRuleCount;
Router(){
rejectRule=new RejectRule[10];
rejectRuleCount=-1;
acceptRule=new AcceptRule[10];
acceptRuleCount=-1;
forwardRule=new ForwardRule[10];
forwardRuleCount=-1;
}
void inputRules(SimpleInput in)throws IOException{
int n=Integer.parseInt(in.readWord());
for(int i=0;i String cmd=in.readWord();
if(cmd.equals("REJECT")){
rejectRule[++rejectRuleCount]=new RejectRule();
rejectRule[rejectRuleCount].input(in);
}else if(cmd.equals("ACCEPT")){
acceptRule[++acceptRuleCount]=new AcceptRule();
acceptRule[acceptRuleCount].input(in);
}else if(cmd.equals("FORWARD")){
forwardRule[++forwardRuleCount]=new ForwardRule();
forwardRule[forwardRuleCount].input(in);
}
}
}
void perform(SimpleInput in)throws IOException{
int n=Integer.parseInt(in.readWord());
for(int i=0;i String ipStr=in.readWord();
IP ip=new IP();
int k=-1,kk=-1;
do{
k=ipStr.indexOf(".");
if(k==-1){
ip.octet[++kk]=Integer.parseInt(ipStr);
break;
}
ip.octet[++kk]=Integer.parseInt(ipStr.substring(0,k));
ipStr=ipStr.substring(k+1);
}while(ipStr.length() != 0);
ip.port=Integer.parseInt(in.readWord());

System.out.println(respond(ip));
}
}
String respond(IP ip){
for(int i=0;i<=rejectRuleCount;i++){
boolean go[]={false,false,false,false,false,true};
for(int j=0;j<4;j++){
String octetRange=rejectRule[i].ipRange.octetRange[j];
if(octetRange.equals("*")){
go[j]=true;
}else if(octetRange.indexOf("-")==-1){
if(Integer.parseInt(octetRange)==ip.octet[j])
go[j]=true;
}else{
int first=Integer.parseInt(octetRange.substring(0,octetRange.indexOf("-")));
int second=Integer.parseInt(octetRange.substring(octetRange.indexOf("-")+1));
if(ip.octet[j]>=first && ip.octet[j]<=second)
go[j]=true;
}
}
String portRange=rejectRule[i].ipRange.portRange;
if(portRange.equals("*")){
go[4]=true;
}else if(portRange.indexOf("-")==-1){
if(Integer.parseInt(portRange)==ip.port)
go[4]=true;
}else{
int first=Integer.parseInt(portRange.substring(0,portRange.indexOf("-")));
int second=Integer.parseInt(portRange.substring(portRange.indexOf("-")+1));
if(ip.port>=first && ip.port<=second)
go[4]=true;
}
for(int j=0;j<5;j++){
if(go[j]==false)
go[5]=false;
}
if(go[5])
return "REJECT";
}



for(int i=0;i<=acceptRuleCount;i++){
boolean go[]={false,false,false,false,false,true};
for(int j=0;j<4;j++){
String octetRange=acceptRule[i].ipRange.octetRange[j];
if(octetRange.equals("*")){
go[j]=true;
}else if(octetRange.indexOf("-")==-1){
if(Integer.parseInt(octetRange)==ip.octet[j])
go[j]=true;
}else{
int first=Integer.parseInt(octetRange.substring(0,octetRange.indexOf("-")));
int second=Integer.parseInt(octetRange.substring(octetRange.indexOf("-")+1));
if(ip.octet[j]>=first && ip.octet[j]<=second)
go[j]=true;
}
}
String portRange=acceptRule[i].ipRange.portRange;
if(portRange.equals("*")){
go[4]=true;
}else if(portRange.indexOf("-")==-1){
if(Integer.parseInt(portRange)==ip.port)
go[4]=true;
}else{
int first=Integer.parseInt(portRange.substring(0,portRange.indexOf("-")));
int second=Integer.parseInt(portRange.substring(portRange.indexOf("-")+1));
if(ip.port>=first && ip.port<=second)
go[4]=true;
}
for(int j=0;j<5;j++){
if(go[j]==false)
go[5]=false;
}
if(go[5])
return "ACCEPT";
}


for(int i=0;i<=forwardRuleCount;i++){
boolean go[]={false,false,false,false,false,true};
for(int j=0;j<4;j++){
String octetRange=forwardRule[i].ipRange.octetRange[j];
if(octetRange.equals("*")){
go[j]=true;
}else if(octetRange.indexOf("-")==-1){
if(Integer.parseInt(octetRange)==ip.octet[j])
go[j]=true;
}else{
int first=Integer.parseInt(octetRange.substring(0,octetRange.indexOf("-")));
int second=Integer.parseInt(octetRange.substring(octetRange.indexOf("-")+1));
if(ip.octet[j]>=first && ip.octet[j]<=second)
go[j]=true;
}
}
String portRange=forwardRule[i].ipRange.portRange;
if(portRange.equals("*")){
go[4]=true;
}else if(portRange.indexOf("-")==-1){
if(Integer.parseInt(portRange)==ip.port)
go[4]=true;
}else{
int first=Integer.parseInt(portRange.substring(0,portRange.indexOf("-")));
int second=Integer.parseInt(portRange.substring(portRange.indexOf("-")+1));
if(ip.port>=first && ip.port<=second)
go[4]=true;
}
for(int j=0;j<5;j++){
if(go[j]==false)
go[5]=false;
}
if(go[5])
return forwardRule[i].forwardTo.print();
}

return "REJECT";
}
public static void main(String[]args)throws IOException{
SimpleInput in=new SimpleInput();
Router router=new Router();
router.inputRules(in);
router.perform(in);
}
}

If you are unable to see the program in a proper format, please click this link
http://chandra-shekhar.spaces.live.com/default.aspx

Solution to MGPT 2007 question no 2.....

This is the solution to MGPT 2007 question no 2.... (85 lines)
I could clear only this question in the MGPT....
The rest I did after the MGPT...


import ncst.pgdst.*;
class Vertex{
char data;
int edgeCount;
Vertex[]edge;
boolean visited;
Vertex(char n){
data=n;
edge=new Vertex[50];
edgeCount=-1;
visited=false;
}
}
class Graph{
Vertex[]vertex;
int vertexCount;
int hops=0;
int min=999999;
Graph(){
vertex=new Vertex[50];
vertexCount=-1;
}
void addVertex(char n){
vertex[++vertexCount]=new Vertex(n);
}
void addEdge(char v1,char v2){
int posv1=findIndex(v1);
int posv2=findIndex(v2);
if(posv1==-1 posv2==-1) return;
int p=++(vertex[posv1].edgeCount);
vertex[posv1].edge[p]=vertex[posv2];
}
int findIndex(char v){
for(int i=0;i<=vertexCount;i++)
if(vertex[i].data==v) return i;
return -1;
}
void dfs(char v1,char v2){
int p1=findIndex(v1);
Stack stack=new Stack();
stack.push(vertex[p1].data);
while(!stack.isEmpty()){
boolean found=false;
int n=findIndex(stack.peek());
for(int i=0;i<=vertex[n].edgeCount;i++){
if(vertex[n].edge[i].visited==true) continue;
stack.push(vertex[n].edge[i].data);
vertex[n].edge[i].visited=true;
++hops;
found=true;
if(vertex[n].edge[i].data==v2){
if(hops//{
//System.out.println("hops = "+hops);
min=hops;
//}
}
break;
}
if(!found){
unvisitChildren(stack.peek());
stack.pop();
--hops;
}
}
if(min==999999)
System.out.println("UNREACHABLE");
else
System.out.println(min);
}
public static void main(String[]args)throws IOException{
SimpleInput in=new SimpleInput();
Graph g=new Graph();
in.skipWhite();
int n=in.readInt();
for(int i=0;iin.skipWhite();
char v1=in.readChar();
in.skipWhite();
char v2=in.readChar();
if(g.findIndex(v1)==-1) g.addVertex(v1);
if(g.findIndex(v2)==-1) g.addVertex(v2);
g.addEdge(v1,v2);
}
in.skipWhite();
char v1=in.readChar();
in.skipWhite();
char v2=in.readChar();
g.dfs(v1,v2);
}
void unvisitChildren(char n){
int p=findIndex(n);
for(int i=0;i<=vertex[p].edgeCount;i++)
vertex[p].edge[i].visited=false;
}
}
class Stack{
char[]a=new char[100];
int top=-1;
void push(char n){ a[++top]=n; }
char peek() { return a[top]; }
void pop() { --top; }
boolean isEmpty(){ return top==-1; }
}


If you are unable to see the program in a proper format, please click this link
http://chandra-shekhar.spaces.live.com/default.aspx

The First MGPT was a blessing in disguise for me..........

Oh, it's true...... I had no idea of clearing the first MGPT at all....... I was no preparation... in fact... I had solved not a single question out of the previous year's MGPT papers.... neither did I have any idea of the kind of questions that might come.......

O' ...... ! Please don't take it other wise. I didn't do that deliberately.. The situations that came up one by one; left me with no options....... You might know.. at first there was a big - big issue out of nothing...... simply a silly complaint against me killed more than two complete days and nights from my routine....... And even after that I remained so affected that I virtually lost interest in doing any study at all......

Still, I coaxed myself and tried to devote myself to studies...... I was still not over with the implementation 'graph' .... I was still very much unconfident on this chapter..... hence, instead of solving the previous year's MGPT questions, I simply relied on enhancing my understanding of the implementation of graphs....... and dropped the hope of clearing the first MGPT at all.... Might be I could work next time for the second MGPT.....

I was frustrated and was having mild headache for several days. I tried to relax myself by watching a movie 'Johny Gaddar', and glimpses of several others. It was very surprising for myself to spend time like that because I had been preparing before every MGPA. I was worried on my inside as to how could I face others by not clearing the MGPT....... But nothing could have been done now.......

The next morning...... as usual I woke up by quarter past nine...... I went for a fresh-up and could manage to get to the test-hall by the right time.....

I was not hoping any good.... I got the paper.... it had two questions.... as was already known to all...... the first question was so long..... to read; it was three pages long.... it took me more than half an hour to read and understand the question itself.........

It was to design an algorithm for a router which has three activities in the listed order:
1) REJECT
2) ACCEPT
3) FORWARD

The question required me to accept IP-ranges for each of these and predict the router action for more inputted IP addresses. The ranges could be defined as each of the octets of each input IP having one of the following forms:
1) integer i.e; single fixed octet
2) start-end i.e; fixed octet range from start to end octets both inclusive
3) * i.e; any possible octet

I knew it could have taken much more time than available..... I decided to have a look on the second question.... it was less than a page long......
It required me to find length of the shortest possible path between given start and end vertices of a given graph......

I felt I could possibly deal with this question in the prescribed time limit i.e; 90 minutes..... I still wished that I could solve the first one also.... but I decided to try that if I could have some time left after being over with the second on........... By the time 90 minutes were over I found that could only develop code for the second question and review it several times...... I felt better for having at least done some work at all...... I was still not sure whether it would have worked in the PARIKSHAK environment.....
We were then asked to go to the lab..... I started typing my code and it took more than half an hour...... I compiled the program and submitted.... still fearing about the X's..... and lo..... the very first result came up as an X............ my heart sank back....but then there appeared a Y to my delight.... Now I was sure that my logic was correct.... and the program was working fine..... there must had been some very small error..... I inserted commands in the program to display the hop-count each time..... and this time a created the input file.... Now the program was printing the hops exactly as expected..... but the minimum path length was being printed as -1..... Then it striked in my mind that instead of printing the minimum path length I was actually printing the hop length. I corrected it, removed the assertions..... and submitted............

Then came the first Y......., I murmured.... what's the next... it was another Y...... then the third Y...... it was so heart-throbbing...... then the fourth Y...... now I was sure the fifth must be Y..... and yes...... it was a Y again..... Wow...............!It was so exciting a moment..... as if I had won the World Cup..... I can't explain that experience...... It was simply exhilarating....

I called upon Anubhav Sir.... and submitted my work.... Sir asked me to try the other question also.... I did..... but it took long..... and before I could start typing in my code, the time was already over.....

Well........, that was the MGPT experience.....

In all.... there were six successes this time....... three from the current batch.... and three form previous batches.....

End of the First term.....

The first term here in NCST is now reaching its end. We all the students of FPGDST course have had sweet and bitter experiences throught this term. Let's take a recount of some of them... as observed by me.....

In the beginning...., it was a very nice experience being at this place..... The content of study was not harassing at all..... it was all the very basics and very easy - going..... In fact, I felt it uncomfortable spending my time on easy topics like them.......

That was truely called 'our honeymoon period'.............. It was simply relax...... relax..... and relax....... But yet, there were others who found those topics difficult because they were new to them.... and they had rarely studied them.......

Till the 9th MGPA all was so... so... but then it seems there was a storm....... so many new topics...... heavy topics....... rapidly dumped on us...... Nobody, in fact, has been able to handle that pressure efficiently.......... The schedules now seemingly went more tight than ever... and all the three modules started dancing above our heads like ghosts.......

It was simply a nightmare....... By luck we could have a comfortable teacher in MFCS... but that too we didn't have many classes........

Now......, tomorrow there's going to be the first MGPT...... let's hope for the better.... but.... truely speaking...... I'm not having a good preparation for the MGPT and I'm not at all ready for it....

Yet..... let's see....

Why do I lack on the part of confidence.....?

There's going to be the 5th and the last MFCS test tomorrow morning... and I know most of the stuff I should to clear the test.... But still, I don't know why..... I've been fearing the test like anything... might be because this was the only subject that brushed me for 2 years during the time when I was doing BCA from IGNOU..... or might be because of something I do not really know about.....

And see the contrast.... I've been performing so well in the class of Theory of Computation (TOC).............. I think I'm Jiji ma'm's favourite..... (Jiji Ma'm is our TOC faculty). I think I must improve myself on the part of confidence......

I had, in fact, an exhaustive talk with Jiji Ma'm .... and she was so surprised over me talking like that...... She said that I was one among a few students in the class that she expected could clear the test..... apart from the fact that she has been asked to set a tough paper for the test by Balaji Sir..... I was greatly comforted by her saying these words...... She is no less than an ANGEL to me...........

Truely..........., she makes upto her name - 'JIJI ANGEL'. If ever I were asked as to who is the best teacher in the world................ I would surely name her............... because nobody can be like her...... she is simply much more than what one could expect at all....

Could you imagine...... talking with her for 10 minutes or so...... how changed I felt myself...... all the fear in me is gone .......

I wish she be there with me always ........ good souls are so rare..... I can hardly afford to lose her presence................

A terrible experience.........

One day, I had been to a nearby mall named 'Total' for shopping. I required to buy a pair of slippers or sandals for casual use; among several other items to buy. Unluckily, I could not find satisfactory ons and then I decided to look for them in another nearby mall named 'Vishal Megamart'. Since, it is not very far away, I decided to walk through the distance. I was casually moving on when I noticed something very painful........... There was a little girl whipping herself on and on and begging for coins from the passersby....... It was such a pity..... I really felt like doing everything I could do for the poor guy... and the very next sight instigated more of it inside me.............. I noticed her parents sitting some distance away and directing her to catch the profitable passersby..... And they were, not at least, in their rugs....... they were averagely dressed and had average health......and I could not doubt them being her parents.............because of the affection which was evidently visible between them and the poor child....... Then how could a couple let their child beat up herself and beg like that............. Well........, what comes to scene is 'boundness' or say 'helplessness'............ One could say that jthe parent could earn themselves and feed their family.... it's easy to say.........but what if you don't get a job......the meanest job even.....after much hard search............ After all, you need to get the mouths fed.............. I could clearly see that the parents were not selfish, but they had no other choice....they were a prey to 'UNEMPLOYMENT'...............one of the most burning problems all over the world....... There's nothing more unbearable than the fire of hunger.... So please, if you are someone who can eleviate this problem to even a trace percentage, then go do it.... Please kindle lights of hope in as many minds as you can......... Come..........., let's together kill the daemon of 'UNEMPLOYMENT'...............!!!!