Showing newest 3 of 4 posts from July 2008. Show older posts
Showing newest 3 of 4 posts from July 2008. Show older posts
Thursday, July 31, 2008
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
Subscribe to:
Posts (Atom)
Blog Archive
Labels
Python
(3)
Programming
(2)
Project Euler
(2)
Java
(1)
Math
(1)
idea
(1)
presentation
(1)
pythonic
(1)
stackoverflow
(1)
topcoder
(1)
