Difference between revisions of "Lecture for IPA2-5" - Rhea

Latest revision as of 04:08, 25 April 2012

void print_partition(int size,int *partition) {

 printf("[");
 int i;
 for (i=0;i<size;i++)
   {
     printf("%d",partition[i]);
   }
 printf("]\n");

}

int emptyFirstColumn(char *data,int dim) {

 int empty=1;
 int i;
 for (i=0;i<dim;i++)
   {

     if (data[i*dim]!='0')empty=0;
   }
 return empty;

}

Blokus *gen_row(int row,int prevCol, int size,int *partition, char *data,int dim) {

 //base case:gone through all rows
 if(row==size)
   {if(emptyFirstColumn(data,dim))return NULL;
     return Blokus_create(data,dim);
   }
 // recursive case: we stil have not assigned all blocks in 
 // this partition
 int col;
 int start=0;
 int stop =dim-partition[row]+1;

 if(row!=0)
   {
     start=prevCol - partition[row]+1;
     if(start<0)start=0;

     stop=prevCol+partition[row-1];
     if (stop + partition[row]>dim) 
        stop=dim-partition[row]+1;

   }

 Blokus *head =NULL;
 for (col=start;col<stop;col++)
   {
     memset(data+row*dim,'0',sizeof(char)* dim);
     memset(data+row*dim+col,'1',sizeof(char)*partition[row]);
     Blokus *list= gen_row(row+1,col,size,partition,data,dim);
    head=BlokusL_append(head,list);

   }
 return head;

}

Blokus *gen_shifts(int *partition,int size, int dim) {

 char *data=malloc(sizeof(char)*dim*dim);
 memset(data,'0',sizeof(char)*dim*dim);
 Blokus *list= gen_row(0,0,size,partition,data,dim);

 free(data);
 return list;

}

Blokus *gen_partition(int budget, int pos, int *partition,int dim) {

 //base case:no more budget spin spin everything
 if(budget==0)
   {print_partition(pos,partition);
     Blokus *list=gen_shifts(partition,pos,dim);
     return list;

   }
 //recursive case:we have budget
 Blokus *head =NULL;
 int spending;
 for (spending=1;spending<=budget;spending++)
   {
     partition[pos]=spending;
  Blokus *list=   gen_partition(budget-spending,pos+1,partition,dim);
  head =BlokusL_append(head,list);
   }
 return head;

} Blokus *make_unique(Blokus*head) {

 return head;

}

Blokus *generate_pieces(int n) {

 int *partition=malloc(sizeof(int)*n);
 // step 1+2:partition+shift valid
 Blokus *head =gen_partition(n,0,partition,n);
 // step 3:uniqueness

head =make_unique(head);

 free(partition);

return head;

} int main(int argc, char *argv[]) {

 if(argc !=2)
   {
     return EXIT_FAILURE;
   }

 int n=strtol(argv[1],NULL,10);
 Blokus *head = generate_pieces(n);
 BlokusL_print(head);
 BlokusL_destroy(head);

 return EXIT_SUCCESS;

}