PRACTICE PROGRAMMING & MATH PROBLEMS: December 2013

Horizontal vs vertical growth - advice : use ladder - use both

Explain roughly how something works, but leave out the details so that you're still an important aspect when it comes to that, but at the same time, you're perceived as a team player and even a leader

if you don't talk how you do things - you may become guru.
if you help others and teach - you are team player.

but gurus don't get promoted - cuz they are experts, boss wants guru to stay at the same position.

My role model : Josh Bao - #1 solver on UVA!

======================================================================

==================================================================

Read a good C++ book first - or you will not know many details


2 things I derived from it:

learn details of C++ - read good book
don't copy someone functions like i copied min (macro)

Sometime little details that I don't know can cause lots of time wasted:

if you use macro definition like below : min , it causes the program to call getmin steps TWICE!

i did not know that!

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std ;
#define min(a,b) ( (a) < (b) ? (a) : (b))

int memo[10 + 1] ;



void reset_memo()
{
    cout << endl ;
    cout << "RESETTING MEMO" << endl ;
    for (int i = 0 ; i < 11 ; i++) {
        memo[i] = -1 ;
    }
}

int getMinSteps(int n)
{
    cout << "======current n : " << n <<  " ===============" << endl ;
    if (n == 1) {
        cout << "BASE CASE n = 1 and returning 0..." << endl ;
        return 0;
    }  // base case

    if (memo[n] != -1) {
        return memo[n];
    } // we have solved it already :)

    cout << "STEP 1 " << endl ;
    int r = 1 + getMinSteps(n - 1);    // '-1' step .  'r' will contain the optimal answer finally

    if (n % 2 == 0) {
        cout << " STEP 2: "  << endl ;
        int v =  getMinSteps(n / 2); // <--- so getMinSteps will be called only once!
        r = min(r , 1 + v) ;
    }  //  '/2' step

    if (n % 3 == 0) {
        cout << " STEP 3: "   << endl ;
        r =  min(r , 1 + getMinSteps(n / 3)) ;
    }  //  '/3' step

    memo[n] = r ;  // save the result. If you forget this step, then its same as plain recursion.
    return r;
}

int main(){
    reset_memo();
    getMinSteps(2);
    getchar();
    getchar();

}

Dev c++ DELAY function - very useful to trace!

!!! IMPORTANT:

to delay your function and see what it does :

#include <windows.h>

Sleep(2000) - 2 seconds

Sleep(3000) - 3 seconds

very long debugged solution - very useful for future reference

#include <iostream>
#include <string.h>
#include <unistd.h>

#include <stdio.h>
using namespace std ;
#define min(a,b) ( (a) < (b) ? (a) : (b))
void print_memo(int a[]){
cout << endl ;
cout << "and printing the whole memo table " <<endl ;
for(int i = 0 ; i < 11 ; i++){
cout << " " << a[i] ;
}
cout << endl <<endl ;

}

int memo[10+1] ;
void reset_memo(){
cout <<endl ;
cout << "RESETTING MEMO" <<endl ;
for(int i = 0 ; i < 11 ; i++){
memo[i] = -1 ;
}
}

int getMinSteps ( int n ){

cout << "======current n : "<< n << " ========================"<<endl <<endl ;
cout << "entering the function" <<endl ;

if ( n == 1 ){ cout << "HITTHING THIS CASE n = 1" <<endl ; return 0;
} // base case
if( memo[n] != -1 ){
cout << "critical : found -1" <<endl;
return memo[n];
} // we have solved it already :)

int r = 1 + getMinSteps( n - 1 ); // '-1' step . 'r' will contain the optimal answer finally
cout << "after step 1 r is " << r <<endl <<endl <<endl ;
if( n%2 == 0 ){cout << "this n: " << n<< " is div by 2 and r we checking " << r <<endl ;
cout << " STEP 2: " << "min of " << r << " and 1 + f(" <<(n/2) << ")" <<endl ;
r = min( r , 1 + getMinSteps( n / 2 ) ) ;} // '/2' step
if( n%3 == 0 ){cout << "this n: " << n<< " is div by 3 and r we checking "<< r <<endl ;
cout << " STEP 3: " << "min of " << r << " and 1 + f(" <<(n/3) << ")" <<endl ;
r = min( r , 1 + getMinSteps( n / 3 ) ) ;
} // '/3' step
cout <<endl ;
cout << "R ADDED : " <<r <<endl <<endl ;

memo[n] = r ; // save the result. If you forget this step, then its same as plain recursion.
cout << "memo cell filled: memo[ " << n << " ] with " << r <<endl ;
print_memo(memo) ;
cout << endl;
return r;

}

int main(){
int n ;
int res = 0 ;

reset_memo() ;
while(true){
cout << endl <<endl ;
cout << "enter next number" <<endl ;
cin >> n ;
if( n == -1 ) {cout << "THE END " <<endl ; break ;}

else{
cout << "******************************************"<<endl <<endl <<endl;
res = getMinSteps(n) ;
cout << "******************************************"<<endl <<endl <<endl;
reset_memo() ;
}
}

}

doing tutorial on dp from CodeChef

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std ;
#define min(a,b) ( (a) < (b) ? (a) : (b))

int memo[10+1] ;
void reset_memo(){
cout <<endl ;
cout << "RESETTING MEMO" <<endl ;
for(int i = 0 ; i < 11 ; i++){
memo[i] = -1 ;
}
}

int getMinSteps ( int n ){
cout << "=============================="<<endl ;
cout << "entering the function" <<endl ;
if ( n == 1 ){ cout << "n = 1" <<endl ; return 0;} // base case
if( memo[n] != -1 ){
cout << "critical : found -1" <<endl;
return memo[n];} // we have solved it already :)

int r = 1 + getMinSteps( n - 1 ); // '-1' step . 'r' will contain the optimal answer finally
if( n%2 == 0 ){ cout << "n is div by 2" <<endl ; r = min( r , 1 + getMinSteps( n / 2 ) ) ;} // '/2' step
if( n%3 == 0 ){cout << "n is div by 3 " <<endl ; r = min( r , 1 + getMinSteps( n / 3 ) ) ;} // '/3' step
cout << "r added is " << r <<endl ;
memo[n] = r ; // save the result. If you forget this step, then its same as plain recursion.
return r;

}

int main(){
int n ;
int res = 0 ;

reset_memo() ;
while(true){
cout << endl <<endl ;
cout << "enter next number" <<endl ;
cin >> n ;
if( n == -1 ) {cout << "THE END " <<endl ; break ;}
else{ res = getMinSteps(n) ;
cout << "result : " <<res <<endl ;
reset_memo() ;
}
}

}

jolly jumpers with some other functions

bool check_sequence(int sequence[], int len){
for(int i = 0 ; i < len-1 ; i++){
int check = abs( sequence[i] - sequence[i+1]) ;
if(check >= 1 && check < len) continue ;
else {
cout << "Not jolly" <<endl ;
return false ; }
}
cout << "Jolly " <<endl ;
return true ;
}

void printarray(int a[], int len){
//cout << "printing array " <<endl ;
for(int i = 0 ; i < len ; i++){
cout << a[i] << " " ;
}
cout <<endl ;
}

int main()
{
int n ;

while( (cin >> n ) != 0 ){
int sequence[n] ;
for(int i = 0 ; i < n ; i++){
cin >> sequence[i] ;
}
for(int i = 0 ; i < n-1 ; i++) {
int a = sequence[i] ;
int b = sequence[i+1] ;
int res = abs( a - b) ;
sequence[i] = res ;

}
sort(sequence, sequence + n -1) ;
bool isJolly = true ;
for(int i = 0 ; i < n-1 ; i++){
if(sequence[i] != (i+1)){
isJolly = false ;
break ;
}
}
if(isJolly) cout << "Jolly" <<endl ;
else cout << "Not jolly" <<endl ;
}// end WHILE

return 0 ;
}

272 tex quotes - stupid presentation error

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std ;

int main(){

char line[1000] ;

int l = 0 ;
bool second = false ;
while( gets(line) ){
l = strlen(line) ;

for(int i = 0 ; i < l; i++){
if( line[i] == '"' && second == false){
printf("``") ;

second = true ;
}
else if(line[i] == '"' && second == true){
printf("''") ;
second = false ;
}
else printf("%c", line[i]) ;

}//end of for
printf("\n") ;
}
return 0 ;
}

uva 102 - hard lesson learned

I expected this lessons !
Feedback :

when you read in your numbers - be careful what variable you store them to:

&b1, &c1 , &g1 - was the wrong order ,

I SPENT 2 HOURS FINDING THE BUG - BUT it was storing them in wrong order to wrong variables!
&b1, &g1 , &c1 - was right!
-----------------------------------------------------------------

#include <iostream>
#include <stdio.h>
#include <string.h>
#define INT_MAX 2147483647
using namespace std ;
int main(){
int b1,b2,b3 ;
int c1,c2,c3 ;
int g1,g2, g3 ;

int min_move = INT_MAX ;//cool!
int answers[6] ;
while( cin >>b1 >> g1 >>c1 >>      b2 >> g2 >> c2      >> b3 >> g3 >> c3 ){
//cout << "processing this line"<<endl ;
  //BCG
  answers[0] = ( c1 + g1) + (b2 + g2) + (b3 + c3) ;

  //BGC
  answers[1] = (g1 + c1) + (b2 + c2) + (b3 + g3) ;

  //CBG
  answers[2] = (b1 + g1) + (g2 + c2) + (b3 + c3) ;

  //CGB
  answers[3] = (b1 + g1) + (b2 + c2) + (g3 + c3) ;

  //GBC
  answers[4] = (b1 + c1) + (g2 + c2) + (b3 + g3) ;

  //GCB
  answers[5] = (b1 + c1) + (b2 + g2) + (g3 + c3) ;
//5 10 5 20 10 5 10 20 10
min_move = INT_MAX ;
  for(int i = 0 ; i < 6;i++){
   //cout << "******** finding min " << endl ;
   if( answers[i] < min_move){
   min_move = answers[i] ;
   }
  }
  //cout << "in here , min found, it is " << min_move <<endl ;
  for(int i = 0 ; i < 6 ;i++){
  // cout <<"inside loop that does printing!" <<endl ;
   if(answers[i] == min_move){
              if( i == 0 )cout << "BCG " ;
              else if(i == 1) cout<< "BGC " ;
              else if(i == 2) cout << "CBG " ;
              else if(i == 3) cout << "CGB " ;
              else if(i == 4 ) cout << "GBC " ;
              else if(i == 5) cout << "GCB " ;
              cout << min_move <<endl ;
    //          cout << "break out !" ;
              break ;
   }
  }
}//end while

return 0 ;

}

UVA ! first problem 3n + 1 (easy)

OK, this is my first problem solved on uva!

#include #include #include using namespace std ; int algo(int n){ int total = 0 ; while( n >= 1){ total++ ; if( n == 1) { return total ;} else if( n % 2 == 1) n = 3 * n + 1 ; else n = n / 2 ; } } void check_cycles(int i , int j, bool swapped){ int max_cycle_len = 0 ; int current_cycle_len = 0 ; for(int num = i ; num <= j ; num++){ current_cycle_len = algo(num) ; if(current_cycle_len > max_cycle_len) max_cycle_len = current_cycle_len ; } if(swapped) cout << j << " "<< i<< " " << max_cycle_len< j ){ swapped = true ; int temp = i ; i = j ; j = temp ; } check_cycles(i, j,swapped) ; } return 0 ; }

Blog Archive