Thursday, July 31, 2008

The Big Idea

Friday, July 18, 2008

Google Code Jam

I took a couple of hours last night the to solve the problems of Google Code Jam preliminary(qualifying) round. Both are correct. And are "beautiful", or so I think.

The detailed problem statements are here: http://code.google.com/codejam/contest/dashboard?c=agdjb2RlamFtcg8LEghjb250ZXN0cxjqOQw

All the solutions are also downloadable. But many are solutions in C++ with Vectors and some nifty solutions in python. At least the top solutions are so. Any way, here I have what I think are good solutions in Java. Let me know if U think otherwise and why so. If you are looking for alternative Java solution, head over to this page: http://code.google.com/codejam/contest/scoreboard?c=agdjb2RlamFtcg8LEghjb250ZXN0cxjqOQw&show_type=all&start_pos=161&views_time=1&views_number=1&views_file=0&csrfmiddlewaretoken= to check out the solution of Tsubosaka, rank 168.

For executing, place the files a1.txt (b3.txt for the second program) in the same folder as the Java files are placed.

Problem 1: Search Engines

import java.io.*;
import java.util.*;
public class A2 {
    int seMax,inMax;
    String[] se,in;
    int i,count;
    boolean b[];
    
    A2(int seMax,String[] se,int inMax,String[] in){
        this.seMax=seMax;
        this.inMax=inMax;
        this.se=se;
        this.in=in;
    
        boolean bol[]= new boolean [seMax];
        Arrays.fill(bol,true);
        b=bol;
        //System.out.println("seMax="+seMax+" inMax= "+inMax);
    }
    
    int findStrPosi(String[] sa, String str, int sMax){
        int posi;
        for(posi=0;posi<sMax && !str.equals(sa[posi]);posi++);
        return posi;
    }
    
    int findCount(){
        //System.out.println(in[]);
        for(i=0;i<inMax;i++){
            //System.out.println(findStrPosi(se,in[i],seMax));
            int curSea=findStrPosi(se,in[i],seMax);
            b[curSea]=false;
            
            boolean isChange=false;
            for(int j=0;j<seMax;isChange=isChange||b[j],j++);
            isChange=!isChange;
            
            if(isChange){
                count++;
                Arrays.fill(b, true);
                b[curSea]=false;
            }
        }
        return count;
        }
 
    public static void main(String[] x)throws IOException{
        File file=new File("./a1.txt");
        String[] se=new String[100];
        String[] in=new String[1000];
        BufferedReader fileIn = new BufferedReader(new FileReader(file));
        
        String fileLine=fileIn.readLine();
        int pMax=Integer.parseInt(fileLine);
        for(int p=0;p<pMax;p++){
            int seMax=Integer.parseInt(fileIn.readLine());
            for(int q=0;q<seMax;q++){
                se[q]=fileIn.readLine().toString();
            }
            int inMax=Integer.parseInt(fileIn.readLine());
            int delcount=0;
            for(int q=0;q<inMax;q++){
                String inpStr=fileIn.readLine().toString();
                int r=0;
                for(r=0;r<seMax && !inpStr.equals(se[r]);r++);
                if(r<seMax){
                    in[q-delcount]=inpStr;
                }else delcount++;
                //System.out.println("in["+(q-delcount)+"]="+in[q-delcount]);
            }
            System.out.println("Case #"+(p+1)+": "+new A2(seMax,se,inMax-delcount,in).findCount());
        }
    }
}

Problem 2: Train Schedules

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
public class B {
    int[] aWant,aAvail,bWant,bAvail;
    int aTrains,bTrains;
    
    B(int wt, int[] aLeave, int[] bArrive, int[] bLeave, int[] aArrive){
        Arrays.sort(aLeave);
        Arrays.sort(bArrive);
        Arrays.sort(bLeave);
        Arrays.sort(aArrive);
        aWant=aLeave;
        bWant=bLeave;
        for(int i=0;i<bArrive.length;bArrive[i]+=wt,i++);
        for(int i=0;i<aArrive.length;aArrive[i]+=wt,i++);
        bAvail=bArrive;
        aAvail=aArrive;
    }
    
    String findTrains(){
        int aExists=0;
        for(int i=aExists;i<aWant.length && aAvail.length>0;i++){
            if(aAvail[0]<=aWant[i]){
                aAvail[0]=2000;
                Arrays.sort(aAvail);
                aExists++;
            }
        }
        int bExists=0;
        for(int i=bExists;i<bWant.length && bAvail.length>0;i++){
            if (bAvail[0]<=bWant[i]){
                bAvail[0]=2000;
                Arrays.sort(bAvail);
                bExists++;
            
            }
        }
        
        return (aWant.length-aExists)+" "+(bWant.length-bExists);
    }
    
    public static void main(String[] in)throws IOException{
        File file=new File("./b3.txt");
        BufferedReader fileIn = new BufferedReader(new FileReader(file));
        String fileLine=fileIn.readLine(),inputs[];
        int pMax=Integer.parseInt(fileLine);
        for(int p=0;p<pMax;p++){
            int wt=Integer.parseInt(fileIn.readLine());
            fileLine=fileIn.readLine();
            inputs=fileLine.split(" ",2);
            int a2b=Integer.parseInt(inputs[0]);
            int b2a=Integer.parseInt(inputs[1]);
            int[] aLeave=new int[a2b];
            int[] bArrive=new int[a2b];
            int[] bLeave=new int[b2a];
            int[] aArrive=new int[b2a];
            for(int i=0;i<a2b;i++){
                fileLine=fileIn.readLine();
                aLeave[i]=Integer.parseInt(fileLine.split(" ",2)[0].split(":",2)[0])*60+Integer.parseInt(fileLine.split(" ",2)[0].split(":",2)[1]);
                //System.out.println(aLeave[i]);
                bArrive[i]=Integer.parseInt(fileLine.split(" ",2)[1].split(":",2)[0])*60+Integer.parseInt(fileLine.split(" ",2)[1].split(":",2)[1]);
                //System.out.println(bArrive[i]);
            }
            for(int i=0;i<b2a;i++){
                fileLine=fileIn.readLine();
                bLeave[i]=Integer.parseInt(fileLine.split(" ",2)[0].split(":",2)[0])*60+Integer.parseInt(fileLine.split(" ",2)[0].split(":",2)[1]);
                aArrive[i]=Integer.parseInt(fileLine.split(" ",2)[1].split(":",2)[0])*60+Integer.parseInt(fileLine.split(" ",2)[1].split(":",2)[1]);
            }
            System.out.println("Case #"+(p+1)+": "+new B(wt,aLeave,bArrive,bLeave,aArrive).findTrains());
        }
    }
}

 

Yes, these solutions are also available from GCJ site in this page: http://code.google.com/codejam/contest/scoreboard?c=agdjb2RlamFtcg8LEghjb250ZXN0cxjqOQw&show_type=all&start_pos=3741&views_time=1&views_number=1&views_file=0&csrfmiddlewaretoken=, My name in rank 3755- I submitted it late in the night and rank depends on at what time one submitted it.

Now I am keen on the next rounds, the earliest one on next Sunday.

Wednesday, July 16, 2008

Google Code Jam Beta 1 triangle Java

Code:

import java.io.*;
public class Triangle {
    double s1,s2,s3,area;
    
    Triangle(int x1,int y1,int x2,int y2,int x3,int y3){
        area=x1*(y3-y2)+x2*(y1-y3)+x3*(y2-y1);
        s1=distBetween(x1,y1,x2,y2);
        s2=distBetween(x1,y1,x3,y3);
        s3=distBetween(x2,y2,x3,y3);
    }
    
    double distBetween(int x1,int y1, int x2, int y2){
        double dist=Math.sqrt(Math.pow((x2-x1),2)+Math.pow((y2-y1),2));
        return dist;
    }
    
    void triType(){
        if(area==0) {
            System.out.println("not a triangle");
            return;
        }
        
        if(s1==s2 || s2==s3 || s1==s3){
            System.out.print("isosceles ");
        }else System.out.print("scalene ");
        
        if(Math.pow(s1, 2)== (Math.pow(s2, 2)+Math.pow(s3, 2)) ||
                Math.pow(s2, 2)==Math.pow(s1, 2)+Math.pow(s3, 2) ||
                    Math.pow(s3, 2)==Math.pow(s1, 2)+Math.pow(s2, 2))
                        System.out.println("right triangle"); 
        else if(Math.pow(s1, 2)>Math.pow(s2, 2)+Math.pow(s3, 2) ||
                Math.pow(s2, 2)>Math.pow(s1, 2)+Math.pow(s3, 2) ||
                    Math.pow(s3, 2)>Math.pow(s1, 2)+Math.pow(s2, 2))
                        System.out.println("obtuse triangle"); 
        else System.out.println("acute triangle");; 
            
    }
    
    
    public static void main(String[] in)throws IOException{
        File file=new File("./a2.txt");
        BufferedReader fileIn = new BufferedReader(new FileReader(file));
        String fileLine=fileIn.readLine(),inputs[];
        int iMax=Integer.parseInt(fileLine);
        for(int i=1;i<iMax+1;i++){
            fileLine=fileIn.readLine();
            inputs=fileLine.split(" ",6);
            int x1=Integer.parseInt(inputs[0]);
            int y1=Integer.parseInt(inputs[1]);
            int x2=Integer.parseInt(inputs[2]);
            int y2=Integer.parseInt(inputs[3]);
            int x3=Integer.parseInt(inputs[4]);
            int y3=Integer.parseInt(inputs[5]);
            System.out.print("Case #"+i+": ");
            new Triangle(x1,y1,x2,y2,x3,y3).triType();
        }
    }
}

Input:

100
0 0 0 4 1 2
1 1 1 4 3 2
2 2 2 4 4 3
3 3 3 4 5 3
4 4 4 5 5 6
5 5 5 6 6 5
6 6 6 7 6 8
7 7 7 7 7 7
0 1 0 1 2 4
0 1 2 4 0 1
2 4 0 1 0 1
0 0 1 1 2 0
0 0 2 2 3 1
0 0 1 2 3 1
0 0 1 2 5 0
1 0 2 3 4 9
0 0 4 1 6 7
2 0 5 7 4 8
7 4 1 8 3 1
5 6 8 7 3 7
8 1 4 6 5 2
4 3 7 3 0 5
2 5 8 7 6 7
7 6 0 1 2 9
9 3 5 6 2 6
8 2 2 0 0 9
8 0 3 5 2 7
5 0 5 1 2 0
1 5 2 7 1 9
9 0 4 3 2 1
2 9 9 8 1 1
7 6 7 0 0 2
3 8 5 4 1 3
3 2 7 4 7 1
1 3 4 1 5 5
3 1 9 7 0 1
3 3 7 2 4 5
5 3 8 1 4 2
3 7 9 8 4 0
2 7 0 7 8 6
2 1 0 8 1 2
1 6 5 9 3 6
3 0 6 8 3 0
1 4 8 6 1 2
2 4 4 8 0 1
8 9 5 4 1 5
4 9 9 6 2 4
9 3 5 7 3 5
2 3 3 9 7 6
2 1 2 2 0 8
2 0 2 2 9 7
2 7 3 3 1 6
1 2 4 1 6 2
8 0 6 3 4 5
8 7 2 5 2 2
7 2 4 7 7 3
6 9 1 5 0 5
8 9 1 4 9 4
0 6 9 1 4 0
7 9 3 3 0 4
6 1 0 0 6 3
6 8 4 6 3 4
3 9 5 7 9 2
1 0 5 9 7 0
8 8 7 8 1 4
4 9 2 9 1 3
2 0 0 0 9 0
0 4 3 5 4 4
6 8 6 7 4 4
4 4 4 5 1 8
6 1 9 1 6 4
0 4 3 0 5 2
5 9 8 5 9 2
4 6 6 8 9 6
9 5 9 1 7 6
0 7 3 8 3 5
6 4 4 4 4 3
2 8 8 7 5 8
4 0 5 1 5 1
9 2 1 2 2 5
0 3 2 2 4 5
1 4 8 9 8 0
0 8 9 6 5 3
3 3 7 0 6 4
3 5 6 2 9 8
9 0 1 9 4 8
9 9 1 5 7 7
4 9 0 7 1 1
3 6 7 2 2 0
7 7 6 0 1 7
5 7 5 3 1 2
3 8 1 3 0 0
6 3 1 1 3 5
9 0 9 7 3 6
9 9 4 2 7 4
0 4 7 0 7 8
9 6 9 5 6 9
4 7 8 1 3 3
0 3 0 4 7 0
5 8 8 3 8 5

 

Output:

Case #1: isosceles obtuse triangle
Case #2: scalene acute triangle
Case #3: isosceles acute triangle
Case #4: scalene obtuse triangle
Case #5: scalene obtuse triangle
Case #6: isosceles obtuse triangle
Case #7: not a triangle
Case #8: not a triangle
Case #9: not a triangle
Case #10: not a triangle
Case #11: not a triangle
Case #12: isosceles acute triangle
Case #13: scalene right triangle
Case #14: isosceles right triangle
Case #15: scalene acute triangle
Case #16: not a triangle
Case #17: scalene obtuse triangle
Case #18: scalene obtuse triangle
Case #19: scalene acute triangle
Case #20: scalene obtuse triangle
Case #21: scalene obtuse triangle
Case #22: scalene obtuse triangle
Case #23: scalene obtuse triangle
Case #24: scalene acute triangle
Case #25: scalene obtuse triangle
Case #26: scalene acute triangle
Case #27: scalene obtuse triangle
Case #28: scalene obtuse triangle
Case #29: isosceles obtuse triangle
Case #30: scalene obtuse triangle
Case #31: scalene acute triangle
Case #32: scalene acute triangle
Case #33: scalene acute triangle
Case #34: scalene acute triangle
Case #35: scalene acute triangle
Case #36: scalene obtuse triangle
Case #37: scalene acute triangle
Case #38: scalene obtuse triangle
Case #39: scalene obtuse triangle
Case #40: scalene obtuse triangle
Case #41: scalene obtuse triangle
Case #42: scalene obtuse triangle
Case #43: not a triangle
Case #44: scalene obtuse triangle
Case #45: scalene obtuse triangle
Case #46: scalene obtuse triangle
Case #47: scalene acute triangle
Case #48: scalene right triangle
Case #49: scalene acute triangle
Case #50: scalene obtuse triangle
Case #51: scalene obtuse triangle
Case #52: scalene obtuse triangle
Case #53: scalene obtuse triangle
Case #54: scalene obtuse triangle
Case #55: scalene obtuse triangle
Case #56: scalene obtuse triangle
Case #57: scalene obtuse triangle
Case #58: scalene acute triangle
Case #59: scalene obtuse triangle
Case #60: scalene obtuse triangle
Case #61: scalene obtuse triangle
Case #62: scalene obtuse triangle
Case #63: scalene obtuse triangle
Case #64: scalene acute triangle
Case #65: scalene obtuse triangle
Case #66: scalene obtuse triangle
Case #67: not a triangle
Case #68: scalene obtuse triangle
Case #69: scalene obtuse triangle
Case #70: scalene obtuse triangle
Case #71: isosceles acute triangle
Case #72: scalene acute triangle
Case #73: scalene obtuse triangle
Case #74: scalene obtuse triangle
Case #75: scalene obtuse triangle
Case #76: scalene acute triangle
Case #77: scalene obtuse triangle
Case #78: scalene obtuse triangle
Case #79: not a triangle
Case #80: scalene acute triangle
Case #81: scalene obtuse triangle
Case #82: scalene acute triangle
Case #83: scalene obtuse triangle
Case #84: scalene acute triangle
Case #85: isosceles acute triangle
Case #86: scalene obtuse triangle
Case #87: scalene obtuse triangle
Case #88: scalene obtuse triangle
Case #89: scalene acute triangle
Case #90: scalene acute triangle
Case #91: scalene obtuse triangle
Case #92: scalene obtuse triangle
Case #93: scalene acute triangle
Case #94: scalene acute triangle
Case #95: scalene obtuse triangle
Case #96: isosceles acute triangle
Case #97: scalene obtuse triangle
Case #98: scalene obtuse triangle
Case #99: scalene obtuse triangle
Case #100: scalene obtuse triangle

Labels