Google code jam 2009

This is the first time I enter the code jam qualification. It was interesting to solve problems which put to test your imagination. Although I contemplated the possibility of coding in python, I coded in C.

Problem C:

This was my solution to problem C (my favorite):

#include 
#include 
int L[20][502];
void init(){
  int i, j;
  for (i = 0; i<20; i++){
    for( j = 0; j < 501; j++){
      L[i][j] = -1;
    }
  }
}
int m(char *word, char *paragraph, int w_i,int p_i){
  if (( paragraph[p_i] == 0 ) && ( word[w_i] != 0) ) {
    L[w_i][p_i] = 0;
  } else if (L[w_i][p_i] != -1){
  } else if (word[w_i] == 0){
    L[w_i][p_i] = 1;
  } else if (word[w_i] == paragraph[p_i]){
    L[w_i][p_i] = (m(word, paragraph, w_i + 1, p_i + 1) + \
        m(word, paragraph, w_i, p_i + 1))%10000;
  } else{
    L[w_i][p_i] = m(word, paragraph, w_i, p_i + 1);
  }
  return L[w_i][p_i];
}
int main(void){
  int i, N;
  char str[502];
  char word[20] = "welcome to code jam";
  scanf("%d\n", &N);
  for (i = 0; i < N ; i++){
    fgets(str, 502, stdin);
    init();
    printf ("Case #%d: %.4d\n", i+1, m(word, str,0,0));
  }
  return 0;
}

This was my solution to problem B (My second favorite):

char diffuse(int r, int c, int height, int width){
  int n, s, e, w, m;
  if (solution[r][c] == '.') {
    n = get_terr(r-1, c, height, width);
    s = get_terr(r+1, c, height, width);
    e = get_terr(r, c+1, height, width);
    w = get_terr(r, c-1, height, width);
    m = min( min(n,s) , min(e,w) );
    if ( terrain[r][c] <= m ){
       last_sink ++;
       solution[r][c] = last_sink;
       return solution[r][c];
    }else{
      if  (m == n){
        solution[r][c] = diffuse(r-1, c, height, width);
      }else if ( m == w){
        solution[r][c] = diffuse(r, c-1, height, width);
      }else if ( m == e){
        solution[r][c] = diffuse(r, c+1, height, width);
      }else if ( m == s){
        solution[r][c] = diffuse(r+1, c, height, width);
      }
    }
  }
  return solution[r][c];
}

This was my solution to problem A:

#include 
#include 

#define MAX 502

char words[5000][17];
char patterns[500][MAX];


int L,D,N;

void read_input(int d, int n){
  int i;
  for ( i = 0; i < d; i++){
    fgets(words[i],17,stdin);
    words[i][strlen(words[i])-1] = 0;
  }
  for (i = 0; i < n; i++){
    fgets(patterns[i], MAX, stdin);
    patterns[i][strlen(patterns[i])-1] = 0;
  }
}

void convert( char *pattern, char *pat[], int l){
  int i = 0;
  int inside = 0;
  *pat = 0;
  while (*pattern){
    if(*pattern == '('){
      pat[i] = pattern + 1;
      i++;
      inside = 1;
    } else if (!inside ){
      pat[i] = pattern;
      i++;
    } else if ( inside ){
      if ( *pattern == ')'){
        inside = 0;
        pattern[0]  = 0;
      }
    }
    pattern++;
  }
  pat[i] = 0;
}

int matches( char *wrd, char *pat[], int l){
  int i;
  for( i = 0; i < l; i++){
    if(!strchr(pat[i], wrd[i])){
      return 0;
    }
  }
  return 1;
}


int main(void){
  int i, j;
  int counter ;
  char *ptn[500];
  if (3 != scanf ("%d%d%d\n", &L,&D,&N)){
    printf ("Could not read sizes \n");
    return 1;
  }
  read_input(D, N);
  for (i = 0; i < N; i++){
    convert( patterns[i], ptn, L);
    counter = 0;
    for( j = 0; j < D; j++){
      if (matches( words[j], ptn, L )){
        counter ++;
      }
    }
    printf ("Case #%d: %d\n", i+1, counter);
  }
  return 0;
}

It was really funny to participate. I used bad sizes for the buffers of fgets (i.e. 501 instead of 502) in A and C. I have to be more careful with that.