My solutions will have some awesome print statements to understand the flow of code, execution tracks
During my glorious conquer of codingbat.com , I did one good thing to understand my code - lots and lost of print statements!
When you encounter problem, or your code works wrong way, you should clearly see whats happening inside it.
so when i solve a problem from online judges, I will not only put hints or solutions - I will also put lots of prints in my code so you guys can copypaste and try it
And trust me, my print statements will be very helpful and informative!
Quote from stack overflow - answer to all questions "can i build smth"
When people ask me - why should i write my own os/compiler/language/cms/database?
the answer can be very simple:
don't reinvent the wheel unless you want to learn about wheels.
+100 to this great, short answer!
Now i can see why i want to write my own compiler and os!
I ultimately want to know how compiler and os work !
Great answer!
len : 13
* 4* 5* 6* 7* 11* 12* 10* 20* 30* 40* 1* 2* 3
mergesort called, parent
splitting into 2 arrays :0 to 6, 7 to 12
mergesort called, parent first
splitting into 2 arrays :0 to 3, 4 to 6
mergesort called, parent first
splitting into 2 arrays :0 to 1, 2 to 3
mergesort called, parent first
splitting into 2 arrays :0 to 0, 1 to 1
mergesort called, parent first
mergesort called, parent second
*********************
temp array created! len 2
comparing elements: 4 and 5
4 inserted
* 4* 0
still some left before end
* 4* 0
mergesort called, parent second
splitting into 2 arrays :2 to 2, 3 to 3
mergesort called, parent first
mergesort called, parent second
*********************
temp array created! len 2
comparing elements: 6 and 7
6 inserted
* 6* 0
still some left before end
* 6* 0
*********************
temp array created! len 4
comparing elements: 4 and 6
4 inserted
* 4* 0* 0* 0
comparing elements: 5 and 6
5 inserted
* 4* 5* 0* 0
still some left before end
* 4* 5* 0* 0
* 4* 5* 6* 0
mergesort called, parent second
splitting into 2 arrays :4 to 5, 6 to 6
mergesort called, parent first
splitting into 2 arrays :4 to 4, 5 to 5
mergesort called, parent first
mergesort called, parent second
*********************
temp array created! len 2
comparing elements: 11 and 12
11 inserted
* 11* 0
still some left before end
* 11* 0
mergesort called, parent second
*********************
temp array created! len 3
comparing elements: 11 and 10
10 inserted
* 10* 0* 0
still some left before middle
* 10* 0* 0
* 10* 11* 0
*********************
temp array created! len 7
comparing elements: 4 and 10
4 inserted
* 4* 0* 0* 0* 0* 0* 0
comparing elements: 5 and 10
5 inserted
* 4* 5* 0* 0* 0* 0* 0
comparing elements: 6 and 10
6 inserted
* 4* 5* 6* 0* 0* 0* 0
comparing elements: 7 and 10
7 inserted
* 4* 5* 6* 7* 0* 0* 0
still some left before end
* 4* 5* 6* 7* 0* 0* 0
* 4* 5* 6* 7* 10* 0* 0
* 4* 5* 6* 7* 10* 11* 0
mergesort called, parent second
splitting into 2 arrays :7 to 9, 10 to 12
mergesort called, parent first
splitting into 2 arrays :7 to 8, 9 to 9
mergesort called, parent first
splitting into 2 arrays :7 to 7, 8 to 8
mergesort called, parent first
mergesort called, parent second
*********************
temp array created! len 2
comparing elements: 20 and 30
20 inserted
* 20* 0
still some left before end
* 20* 0
mergesort called, parent second
*********************
temp array created! len 3
comparing elements: 20 and 40
20 inserted
* 20* 0* 0
comparing elements: 30 and 40
30 inserted
* 20* 30* 0
still some left before end
* 20* 30* 0
mergesort called, parent second
splitting into 2 arrays :10 to 11, 12 to 12
mergesort called, parent first
splitting into 2 arrays :10 to 10, 11 to 11
mergesort called, parent first
mergesort called, parent second
*********************
temp array created! len 2
comparing elements: 1 and 2
1 inserted
* 1* 0
still some left before end
* 1* 0
mergesort called, parent second
*********************
temp array created! len 3
comparing elements: 1 and 3
1 inserted
* 1* 0* 0
comparing elements: 2 and 3
2 inserted
* 1* 2* 0
still some left before end
* 1* 2* 0
*********************
temp array created! len 6
comparing elements: 20 and 1
1 inserted
* 1* 0* 0* 0* 0* 0
comparing elements: 20 and 2
2 inserted
* 1* 2* 0* 0* 0* 0
comparing elements: 20 and 3
3 inserted
* 1* 2* 3* 0* 0* 0
still some left before middle
* 1* 2* 3* 0* 0* 0
* 1* 2* 3* 20* 0* 0
* 1* 2* 3* 20* 30* 0
*********************
temp array created! len 13
comparing elements: 4 and 1
1 inserted
* 1* 0* 0* 0* 0* 0* 0* 0* 0* 0* 0* 0* 0
comparing elements: 4 and 2
2 inserted
* 1* 2* 0* 0* 0* 0* 0* 0* 0* 0* 0* 0* 0
comparing elements: 4 and 3
3 inserted
* 1* 2* 3* 0* 0* 0* 0* 0* 0* 0* 0* 0* 0
comparing elements: 4 and 20
4 inserted
* 1* 2* 3* 4* 0* 0* 0* 0* 0* 0* 0* 0* 0
comparing elements: 5 and 20
5 inserted
* 1* 2* 3* 4* 5* 0* 0* 0* 0* 0* 0* 0* 0
comparing elements: 6 and 20
6 inserted
* 1* 2* 3* 4* 5* 6* 0* 0* 0* 0* 0* 0* 0
comparing elements: 7 and 20
7 inserted
* 1* 2* 3* 4* 5* 6* 7* 0* 0* 0* 0* 0* 0
comparing elements: 10 and 20
10 inserted
* 1* 2* 3* 4* 5* 6* 7* 10* 0* 0* 0* 0* 0
comparing elements: 11 and 20
11 inserted
* 1* 2* 3* 4* 5* 6* 7* 10* 11* 0* 0* 0* 0
comparing elements: 12 and 20
12 inserted
* 1* 2* 3* 4* 5* 6* 7* 10* 11* 12* 0* 0* 0
still some left before end
* 1* 2* 3* 4* 5* 6* 7* 10* 11* 12* 0* 0* 0
* 1* 2* 3* 4* 5* 6* 7* 10* 11* 12* 20* 0* 0
* 1* 2* 3* 4* 5* 6* 7* 10* 11* 12* 20* 30* 0
* 1* 2* 3* 4* 5* 6* 7* 10* 11* 12* 20* 30* 40
After codingbat, my programming challenge is to solve 100 problems from UVA online judge.
This is more than doable! after finishing this milestone, i will solve another 100, another 100.... Up to infinity!
I follow the tip to master all major algorithms. I have problems with mergesort - i needed to understand it. So in this version i include lots of print statements to see how arrays are filled.
public class mergesort{
static void merge(int a[], int start, int pivot, int finish){
System.out.println("\n\n*********************") ;
int tmp[] = new int[finish - start +1] ;
System.out.println("temp array created! len " + tmp.length) ;
for(int i = 0 ; i < tmp.length;i++) tmp[i] = 0 ;
int I = start ;
int J = pivot +1 ;
int K = 0 ;
while((I <= pivot)&& ( J <= finish) ){
System.out.println("comparing elements: " + a[I] +" and "+ a[J]) ;
if(a[I] < a[J]){
System.out.println(a[I] + " inserted") ;
tmp[K] = a[I] ; K++ ; I++ ;
printarray(tmp, tmp.length) ;
}
else{
System.out.println(a[J] + " inserted") ;
tmp[K] = a[J] ; K++ ; J++ ;
printarray(tmp, tmp.length) ;
}
}
if(I <= pivot){
System.out.println("still some left before middle") ;
while(I <= pivot){
printarray(tmp,tmp.length) ;
tmp[K++] = a[I++] ;
}
}
if( J<= finish){
System.out.println("still some left before end") ;
while(J<= finish){
printarray(tmp,tmp.length) ;
tmp[K++] = a[J++] ;
}
}
for(K = start ; K <= finish ; K++) a[K] = tmp[K-start] ;
return ;
}
static void mergesort(int a[], int start, int finish, String parent){
System.out.println("\n mergesort called, parent " + parent) ;
if(start < finish){
int pivot = (start + finish)/2 ;
System.out.println("\n\n\n\nsplitting into 2 arrays :" + start + " to " + pivot + ", " + (pivot+1) + " to " + finish ) ;
mergesort(a,start, pivot, "first") ;
mergesort(a, pivot+1, finish, "second") ;
merge(a, start, pivot, finish) ;
}
}
public static void printarray(int a[], int len){
for(int i = 0 ; i < len; i++) System.out.print("* " + a[i]) ;
System.out.println() ;
}
public static void main(String args[]){
int test[] = {4,5,6,7,11,12,10,20,30,40,1,2,3} ;
int len = test.length ;
System.out.println("len : " + len) ;
printarray(test,len) ;
mergesort(test,0, len-1, "") ;
printarray(test,len) ;
}
}
This is more than doable! after finishing this milestone, i will solve another 100, another 100.... Up to infinity!
I follow the tip to master all major algorithms. I have problems with mergesort - i needed to understand it. So in this version i include lots of print statements to see how arrays are filled.
public class mergesort{
static void merge(int a[], int start, int pivot, int finish){
System.out.println("\n\n*********************") ;
int tmp[] = new int[finish - start +1] ;
System.out.println("temp array created! len " + tmp.length) ;
for(int i = 0 ; i < tmp.length;i++) tmp[i] = 0 ;
int I = start ;
int J = pivot +1 ;
int K = 0 ;
while((I <= pivot)&& ( J <= finish) ){
System.out.println("comparing elements: " + a[I] +" and "+ a[J]) ;
if(a[I] < a[J]){
System.out.println(a[I] + " inserted") ;
tmp[K] = a[I] ; K++ ; I++ ;
printarray(tmp, tmp.length) ;
}
else{
System.out.println(a[J] + " inserted") ;
tmp[K] = a[J] ; K++ ; J++ ;
printarray(tmp, tmp.length) ;
}
}
if(I <= pivot){
System.out.println("still some left before middle") ;
while(I <= pivot){
printarray(tmp,tmp.length) ;
tmp[K++] = a[I++] ;
}
}
if( J<= finish){
System.out.println("still some left before end") ;
while(J<= finish){
printarray(tmp,tmp.length) ;
tmp[K++] = a[J++] ;
}
}
for(K = start ; K <= finish ; K++) a[K] = tmp[K-start] ;
return ;
}
static void mergesort(int a[], int start, int finish, String parent){
System.out.println("\n mergesort called, parent " + parent) ;
if(start < finish){
int pivot = (start + finish)/2 ;
System.out.println("\n\n\n\nsplitting into 2 arrays :" + start + " to " + pivot + ", " + (pivot+1) + " to " + finish ) ;
mergesort(a,start, pivot, "first") ;
mergesort(a, pivot+1, finish, "second") ;
merge(a, start, pivot, finish) ;
}
}
public static void printarray(int a[], int len){
for(int i = 0 ; i < len; i++) System.out.print("* " + a[i]) ;
System.out.println() ;
}
public static void main(String args[]){
int test[] = {4,5,6,7,11,12,10,20,30,40,1,2,3} ;
int len = test.length ;
System.out.println("len : " + len) ;
printarray(test,len) ;
mergesort(test,0, len-1, "") ;
printarray(test,len) ;
}
}
FINALLY all coding bat problems solved!
in short, i solved about 90% of all problems MYSELF.
coding bat is certainly not a match to real competitions, but it is a good result for a newbie like me, now i have some confidence to raise the limit!
i spent about 5 months doing it : 1 june 2013 - october 22 2013
Subscribe to:
Comments (Atom)