/*ECE 264 Lecture Wed Apr18 Peachanok Lertkajornkitti Professor Elmqvst (Section 1)
IPA2-5
need to use: ipa2-1 AND 2-3,2-4
Steps: 1.IPA2-1 2.IPA2-2 3.IPA2-4 4.Print list
- /
- include<stdio.h>
- include<stdlib.h>
- include<string.h>
- include"Blokus.h"
void print_partition(int size,int *partition) { printf("["); int i; for(i=0;i<size;i++) { printf(" %d",partition[i]); } printf("]\n");
Blokus *gen_partition(int budget,int pos,int *partition,int dim) { //Base case: no more budget if(budget==0) { print_partition(pos,partition); Blokus *list = gen_shifts(partition,pos,dim); return list; }
//Recursive case: have budget Blokus *head = NULL; int spending; int (spending = 1;spending<=budget;spending++) { partition(pos) = spending; Blokus *list = gen_partition(budget-spending,pos+1,partition,dim); head = BlokusL_append(head, list); //takes the head and add a new list to the end }
} Blokus *make_unique(Blokus *head) //takes in the head n make sure it's unique { //IPA2-4 return head; } Blokus *generate_pieces(int n) { int *partition = malloc(sizeof(int)*n); //Step 1+2 Blokus *head = gen_partition(n,0,partition,n); free(partition); //Step 3 head = make_unique(head); 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_printf(head); BlokusL_destroy(head);
return EXIT_SUCCESS; }
//Blokus.h
- ifndef BLOKUS_H
- define BLOKUS_H
typedef struct Blokus_t{ char *data; int dim; struct Blokus_t *next; }Blokus;
Blokus *Blokus_create(char *data,int dim); void Blokus_destroy(Blokus *blokus); void Blokus_print(Blokus *blokus);
Blokus BlokusL_insert(char *data,int dim,Blokus *head); void BlokusL_print(Blokus *head); void BlokusL_destroy(Blokus *head); Blokus *BlokusL_append(head, list);
- endif /*Blokus.h */
//Blokus.c
- include<stdio.h>
- include<stdlib.h>
- include<string.h>
- include"Blokus.h"
Blokus *Blokus_create(char *data,int dim) { Blokus *blokus = malloc(sizeof(Blokus)); blokus->data = malloc(sizeof(char) * dim * dim); memcpy(blokus->data,data,sizeof(char)*dim*dim); blokus->dim = dim; blokus->next = NULL;
return blokus; } void Blokus_destroy(Blokus *blokus) { free(blokus->data); free(blokus); }
void Blokus_print(Blokus *blokus); { int i; for(i=0;i<blokus->dim*blokus->dim;i++) { printf("%c",blokus->data[i]); } printf("\n");
}
Blokus BlokusL_insert(char *data,int dim,Blokus *head) { Blokus *blokus = Blokus_create(data,dim); blokus->next = head; return head; }
void BlokusL_print(Blokus *head)
{
while(head != NULL)
{
Blokus_piece(head);
head = head->next;
}
}
void BlokusL_destroy(Blokus *head)
{
while(head != NULL)
{
Blokus *tmp = head;
head = head->next;
Blokus_destroy(tmp);
}
}
Blokus *BlokusL_append(Blokus *head, Blokus *head2) //COULD COME OUT IN AN EXAM { if(head == NULL) return head2; Blokus *curr = head; while(curr->next != NULL) { curr = curr->next; }
curr->next = head2; return head; }
===================
Hanye Xu April 19th
Binary search tree v
/ \ left right
everything at left <v right >v integer partition generate piece by shift eliminate duplicates invalid piece 8 squares
how many ways can you shift: a squares & b squares b-1 distance to shift or a-1 distance to shift
for(shift = 1-b; shift<=a-1; shift++) { next two rows;
n= a new piece
p=head;
while('p' != NULL)&&checkDuplicate(P,n) == 0){
p=p->next;
}
if (p==NULL){insert(nth list);
}
binary tree
for any real number x you can find a real number y such that x = 2^y or x = -2^y
n steps to log n steps
suppose have n numbers array of n elements log n
===============================
Wudi Zhou, April 19th, Prof. Lu's section
Hints for last assignment: Steps: 1,Integer partition
2,Generate pieces by shifting
3,Eliminate duplicates
use for loop to shift two rows:
ie for(shift = 1 - b; shift <= a - b; shift ++)
p = head; while((p != NULL) && (checkDuplicate == 0)) { p = p -> next; } if(p == NULL) { insert(n); }
For binary tree: n step can be done by log(n) steps
===================
Kevin Tan(0023987592), section#2 notes 04/17
2-5:
1.integer patition
2.generate piece by shift
3.eliminate duplicates
4.invalid piece
for (shift = 1-b;shift<= a-1; shift++)
for(i=1;i<=n;i++) {
f(n-i);
}
n = a new piece; p=head;
while(('p' != NULL)&&(checkduplicate(p,n)==0)
{
p=p->next;
} if(p==NULL) {
insert(nth list);
}
for any real number x, you can find a real number y, such that x=2^y or x=-2^y
n step can be done by log(n) steps
Lecture Wed Apr18
Huayi Guo
Professor Elmqvst (Section 1)
/* Lecture 0418
Announcement;
Exam 3 - 8-10pm
(-need to take if not passed all outcomes)
ipa2-5 - Monday, Apr23 6pm
(extended!)
ex6 - sat, apr28 12pm(noon)
(no extensions)
Final exam - Sat, May5 8-10pm
(EE206/207,POTR360,MSEE189)
course survey - 0.5pt(email)
- /
//ipa2-5 /* N -> generate all valid and unique pieces of size N(# of cells used)
Need: ipa2-1: partition
ipa2-3: validity
ipa2-4: uniquness
Step 1: Step 2: Step 3:
- /
- include<stdio.h>
- include<stdlib.h>
- include<string.h>
void PartitionPrint(int, size, int *partition) {
printf("[");
int i;
for(i = 0;i<size ;i++){
printf("%d", partition[1]);
}
printf("]\n");
}
Blokus *GenPartition(int budget, int pos, int *partition, int dim) {
//Base case: no more budget
it(budget = 0){
PartitionPrint(pos, partition);
return GenShifts(partition,pos,dim);
}
//REcursive case: we have budget
Blokus *head = NULL;
int spending;
for(spending =1; spending <=budget; spending++){
partition[pos] = spending;
Blokus *list = GenPartition(budget-spending, pos+1,partition, dim);
Blokus *head = BlokusListappend(head, list);
}
return head;
}
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
if(row == size){
if(emptyFirstColumn(data,dim)) return NULL;
return BlokusCreate(data, dim);
}
//Recursive case
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;co++){
memset(data + row *dim,'0',sizeof(char)*dim);
memset(dat+row*dim+col, '1',sizeof(char)*partition[row]);
Blokus *list = gen_row(row +1, col,size,partition,data,dim);
head = Blokus
}
}
Blokus * GenShift(int *partition, int size, int dim) {
char * data = malloc(sizeof(char)*dim*dim); memset(dat, '0', sizeof(char)*dim*dim); Blokus * list = gen_row(0,0,size,partition,data,dim); free(data); return list;
}
Blokus *BlokusListappend(Blokus *head, Blokus*list); {
if(head =NULL)return list;
Blokus * curr = head;
while(curr->next != NULL){
curr = curr->next;
}
curr->next = list;
return head;
}
Blokus *MakeUnique(Blokus * head)
{
}
Blokus * GeneratePiece(int n)
{
int *partition = malloc(sizeof(int)*n); //step 1and2 partition+shift valid Blokus * head = GenPartition(n,0, partition,n) free(partition); //step 3: uniqueness; head = MakeUnique(head); return head;
}
int main(int argc, char * argv[]) {
int n = strtol(argv[1], NULL, 10); Blokus * head = GeneratePiece(n); BlokusPrint(head); BlokusDestroy(head); return EXIT_SUCCESS;
}
_________________________________________________________
Shiyu Wang Lec26 April 22nd
