吳邦一程設練習 Project

ccu_practice_project.md

#吳邦一程設練習 Project

ex1.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <stdbool.h>

typedef struct {
    char* account;
    char* domain;
} Record;

int my_strcmp(const char* sa, const char* sb) {
    int a_len = strlen(sa);
    int b_len = strlen(sb);

    int min_len = ((a_len < b_len) ? a_len : b_len);

    for (int i = 0; i < min_len; i++) {
        char ka = toupper(sa[i]);
        char kb = toupper(sb[i]);
        if (ka < kb)
            return -1;
        if (ka > kb)
            return +1;
    }

    return a_len - b_len;
}

int record_cmp_by_name(const void* a, const void* b) {
    Record* ra = (Record*) a;
    Record* rb = (Record*) b;

    // Compare Name
    int flag = my_strcmp(ra->account, rb->account);
    if (flag != 0)
        return flag;

    // Compare Domain
    return my_strcmp(ra->domain, rb->domain);
}

int record_cmp_by_domain(const void* a, const void* b) {
    Record* ra = (Record*) a;
    Record* rb = (Record*) b;

    // Compare Domain
    int flag = my_strcmp(ra->domain, rb->domain);
    if (flag != 0)
        return flag;

    // Compare Name
    return my_strcmp(ra->account, rb->account);
}

bool is_valid_identifiers(const char* s) {
    if (s == NULL)
        return false;

    int len = strlen(s);
    if (len == 0)
        return false;

    for (int i = 0; i < len; i++)
        if (!isdigit(s[i]) && !isalpha(s[i]) && s[i] != '_')
            return false;
    return true;
}

bool parse_email(char* email, Record* r) {
    char s[2048]; /* s will be modified. */
    strncpy(s, email, strlen(email) + 1);

    char* idx = strchr(s, '@');
    if (idx == NULL)
        return false;

    *idx = '\0';
    char* account = s;
    char* domain = idx + 1;

    if (strlen(account) == 0 || strlen(domain) == 0)
        return false;

    // Check account
    if (account[0] == '.' || account[strlen(account) - 1] == '.')
        return false;
    for (idx = account; *(idx + 1); idx++)
        if (*idx == '.' && *(idx + 1) == '.')
            return false;

    char* token = strtok(account, ".");
    if (token == NULL && !is_valid_identifiers(account))
        return false;
    while (token != NULL) {
        if (strlen(token) == 0 || !is_valid_identifiers(token))
            return false;
        token = strtok(NULL, ".");
    }

    // Check domain
    if (domain[0] == '.' || domain[strlen(domain) - 1] == '.')
        return false;
    for (idx = domain; *(idx + 1); idx++)
        if (*idx == '.' && *(idx + 1) == '.')
            return false;

    token = strtok(domain, ".");
    if (token == NULL && !is_valid_identifiers(domain))
        return false;
    while (token != NULL) {
        if (strlen(token) == 0 || !is_valid_identifiers(token))
            return false;
        token = strtok(NULL, ".");
    }

    // If it haven't returned, it is a valid email.
    // Re-parse email again to obtain account and domain
    account = strtok(email, "@");
    domain = strtok(NULL, "@");
    int account_len = strlen(account);
    int domain_len = strlen(domain);
    r->account = (char*) malloc (sizeof(char) * (account_len + 1));
    r->domain = (char*) malloc (sizeof(char) * (domain_len + 1));
    strncpy(r->account, account, account_len + 1);
    strncpy(r->domain, domain, domain_len + 1);

    return true;
}

int main(int argc, char* argv[]) {
    int T;
    while (scanf("%d\n", &T) != EOF) {
        if (T == 0) break;

        Record data[2048];
        int data_idx = 0;

        char inp[2048];
        for (int i = 0; i < T; i++) {
            /* Read the entire line. */
            fgets(inp, 2048, stdin);
            int len = strlen(inp);
            if (inp[len-1] == '\n') {
                inp[len-1] = '\0';
                len--;
            }

            if (len == 0) continue;

            /* Parse email */
            printf("%-30s=> ", inp);
            if (parse_email(inp, &data[data_idx])) {
                printf("valid\n");
                data_idx++;
            }
            else
                printf("NOT valid\n");
        }

        const int N = data_idx;

        puts("--------------------------------");
        puts("Sort by Username:");
        qsort(data, N, sizeof(Record), record_cmp_by_name);
        for (int i = 0; i < N; i++)
            printf("%s@%s\n", data[i].account, data[i].domain);

        puts("");
        puts("Sort by Domain:");
        qsort(data, N, sizeof(Record), record_cmp_by_domain);
        for (int i = 0; i < N; i++)
            printf("%s@%s\n", data[i].account, data[i].domain);

        // free
        for (int i = 0; i < N; i++) {
            free(data[i].account);
            free(data[i].domain);
        }
    }

    return 0;
}

ex2.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
#include <math.h>

typedef struct {
    long long n;
    long long d;
} Fraction;

void print_fraction(Fraction f) {
    if (f.n < 0) {
        if (f.d == 1)
            printf("(%lld) ", f.n);
        else
            printf("(%lld)/%lld ", f.n, f.d);
    }
    else
        printf("%lld/%lld", f.n, f.d);
    printf("\n");
}

long long myabs(long long ll) {
    if (ll < 0)
        return -ll;
    return ll;
}

long long gcd(long long a, long long b) {
    while (b) {
        // a, b = b, a % b
        long long temp = a;
        a = b;
        b = temp % b;
    }
    return a;
}

long long atoll(const char* s) {
    long long value = 0;
    for (const char* idx = ((s[0] == '-') ? s+1 : s); *idx; idx++)
        value = value * 10 + (*idx - '0');
    if (s[0] == '-')
        value = -value;
    return value;
}

void simplify(Fraction* f) {
    if (f->d < 0) {
        f->d = -(f->d);
        f->n = -(f->n);
    }

    long long g = gcd(myabs(f->n), myabs(f->d));
    f->n = (f->n) / g;
    f->d = (f->d) / g;
}

Fraction fadd(const Fraction f1, const Fraction f2) {
    Fraction f;
    f.d = f1.d * f2.d;
    f.n = f1.n * f2.d + f2.n * f1.d;
    simplify(&f);
    return f;
}

Fraction fdiv(const Fraction f1, const Fraction f2) {
    Fraction f;
    f.n = f1.n * f2.d;
    f.d = f1.d * f2.n;
    simplify(&f);
    return f;
}

bool is_int(const char* s) {
    for (const char* i = ((s[0] == '-') ? s+1 : s); *i; i++)
        if (!isdigit(*i))
            return false;
    return true;
}

bool parse_fraction(const char* inp, Fraction* f) {
    if (inp == NULL || strlen(inp) == 0 || inp[0] == '\0')
        return false;

    //printf("parsing %s\n", inp);

    int len = strlen(inp);
    char s[len + 1];
    strncpy(s, inp, len + 1);

    // pure form
    if (is_int(s)) {
        f->n = atoll(s);
        f->d = 1;
        return true;
    }

    // enclosed by bracket
    if (s[0] == '(' && s[len - 1] == ')') {
        int flag = 1;
        for (int i = 1; i < len; i++) {
            if (s[i] == '(')
                flag++;
            if (s[i] == ')')
                flag--;

            if (flag == 0) {
                if (i == len - 1) {
                    s[len - 1] = '\0';
                    return parse_fraction(s + 1, f);
                }
                else
                    break;
            }
        }
    }

    // fraction
    char* idx = strchr(s, '/');
    if (idx != NULL) {
        *idx = '\0';
        Fraction n;
        Fraction d;
        if (parse_fraction(s, &n) && parse_fraction(idx + 1, &d)) {
            // divided by 0
            if (d.n == 0)
                return false;

            Fraction q = fdiv(n, d);
            f->n = q.n;
            f->d = q.d;
            return true;
        }
        else {
            return false;
        }
    }

    // decimal
    idx = strchr(s, '.');
    if (idx != NULL) {
        f->d = 1;
        for (char* i = idx + 1; *i; i++) {
            if (isdigit(*i))
                f->d = (f->d) * 10;
            else
                return false;
        }

        f->n = 0;
        for (char* i = ((s[0] == '-') ? s+1 : s); *i; i++) {
            if (isdigit(*i))
                f->n  = (f->n) * 10 + (*i - '0');
            else if (*i == '.')
                continue;
            else
                return false;
        }
        if (s[0] == '-')
            f->n = -(f->n);

        simplify(f);
        return true;
    }

    return false;
}

// ./main.out test 1.2 3/7 2000000 "7/(-3)" "(0.00)" "5/(-0)" 1.2/6 -1.2 "(-2)/(-3)"
int main(int argc, char* argv[]) {
    if (argc < 2) {
        puts("No arguments provided");
        return -1;
    }

    Fraction fractions[argc - 1];
    int idx = 0;
    for (int i = 1; i < argc; i++) {
        if (parse_fraction(argv[i], &fractions[idx]))
            idx++;
        else
            printf("Illegal argument: %s\n", argv[i]);
    }

    if (idx == 0) {
        puts("Nothing to add");
        return -1;
    }

    // sum up
    Fraction total;
    total.n = 0;
    total.d = 1;

    puts("-----------------");
    for (int i = 0; i < idx; i++)
        print_fraction(fractions[i]);
    puts("-----------------");

    const int N = idx;
    for (int i = 0; i < N; i++)
        total = fadd(total, fractions[i]);

    // print fraction
    print_fraction(total);

    // print decimal
    printf("= %f\n", (double)total.n / (double)total.d);

    return 0;
}

ex3.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>

typedef enum {
    MALE, FEMALE
} Gender;

typedef struct {
    char name[16];
    int age;
    Gender gender;
} Record;

int cmp_by_name(const void* a, const void* b) {
    Record* ra = (Record*) a;
    Record* rb = (Record*) b;
    int flag = strcmp(ra->name, rb->name);
    if (flag != 0)
        return flag;

    if (ra->age != rb->age)
        return ra->age - rb->age;

    return ra->gender - rb->gender;
}

typedef struct {
    int capacity;
    int size;
    Record* storage;
} Vector;

Vector* new_vector() {
    Vector* v = (Vector*) malloc (sizeof(Vector));
    v->capacity = 1;
    v->size = 0;
    v->storage = (Record*) malloc (sizeof(Record) * (v->size));
    return v;
}

bool push_back(Vector* v, const Record* record) {
    if (v->size + 1 > v->capacity) {
        Record* temp = (Record*) malloc (sizeof(Record) * (v->size));
        if (temp == NULL)
            return false;
        memcpy(temp, v->storage, sizeof(Record) * (v->size));
        free(v->storage);

        v->capacity = (v->capacity) * 2;
        v->storage = (Record*) malloc (sizeof(Record) * (v->capacity));
        if (v->storage == NULL)
            return false;
        memcpy(v->storage, temp, sizeof(Record) * (v->size));
        free(temp);

        printf("(Capacity not enough. Updated to %d), ", v->capacity);
    }

    memcpy(v->storage + (v->size), record, sizeof(Record));
    (v->size)++;

    return true;
}

void trim(char** s) {
    int len = strlen(*s);
    
    for (int i = len - 1; (*s)[i] == ' ' && i >= 0; i--)
        (*s)[i] = '\0';
    
    for (; **s && **s == ' '; (*s)++);
}

bool parse_record(const char* input, Record* record) {
    char s[1024];
    strcpy(s, input);

    char* name = strtok(s, ",");
    char* age = strtok(NULL, ",");
    char* gender = strtok(NULL, ",");

    if (name == NULL || age == NULL || gender == NULL) {
        puts("Illegal Format.");
        return false;
    }

    // trim the string
    trim(&name);
    trim(&age);
    trim(&gender);
    
    int name_len = strlen(name);
    int age_len = strlen(age);
    int gender_len = strlen(gender);

    if (name_len == 0 || age_len == 0 || gender_len == 0) {
        puts("Illegal Format.");
        return false;
    }

    // name
    if (name_len >= 2 && name[0] == '\"' && name[name_len - 1] == '\"') {
        name[name_len - 1] = '\0';
        name++;
        name_len = name_len - 2;
    }
    if (name_len == 0 || name_len > 16) {
        puts("Illegal Name. Length: 1 ~ 16.");
        return false;
    }

    // age
    bool is_valid_age = true;
    for (int i = 0; i < age_len; i++) {
        if (!isdigit(age[i])) {
            is_valid_age = false;
            return false;
        }
    }
    if (!is_valid_age || age_len >= 4) {
        puts("Illegal Age.");
        return false;
    }

    // Gender
    Gender g;
    if (strcmp(gender, "MALE") == 0)
        g = MALE;
    else if (strcmp(gender, "FEMALE") == 0)
        g = FEMALE;
    else {
        puts("Illegal Gender. <MALE/FEMALE>.");
        return false;
    }

    strcpy(record->name, name);
    record->age = atoi(age);
    record->gender = g;

    return true;
}

int main() {
    Vector* v = new_vector();

    char input[1024];
    while (fgets(input, 1024, stdin) != NULL) {
        int len = strlen(input);
        if (input[len - 1] == '\n') {
            input[len - 1] = '\0';
            len--;
        }

        Record r;
        printf("%-20s : ", input);
        if (parse_record(input, &r) == true && push_back(v, &r)) {
            puts("Success.");
        }
        else {
            continue;
        }
    }

    printf("---------------------------\n");
    printf("Storage (Sort by name): \n");

    qsort(v->storage, v->size, sizeof(Record), cmp_by_name);

    for (int i = 0; i < v->size; i++) {
        printf("%d: %s, %d, ", i+1, v->storage[i].name, v->storage[i].age);
        if (v->storage[i].gender == MALE)
            printf("MALE");
        else
            printf("FEMALE");
        printf("\n");
    }

    free(v->storage);
    free(v);

    return 0;
}

ex4.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

double integrate(double (*f) (double), double a, double b, double dx) {
    double sum = 0.0;
    for (double x = a; x <= b; x += dx) {
        sum += f(x) * dx;
    }
    return sum;
}

double g(double x) {
    return 2 * x;
}

int main(int argc, char* argv[]) {
    double a = 0.0, b = 1.0, dx = 1e-3;

    const char* name[4] = {"sin", "cos", "tan", "g"};
    double (*functions[4])(double) = {sin, cos, tan, g};
    int idx = -1;

    if (argc > 1 && argc == 5) {
        for (int i = 0; i < 4; i++) {
            if (strcmp(name[i], argv[1]) == 0) {
                idx = i;
                break;
            }
        }
        if (idx == -1) {
            puts("Function not Supported!");
            return -1;
        }

        a = atof(argv[2]);
        b = atof(argv[3]);
        dx = atof(argv[4]);
    }
    else {
        puts("Illegal Command!");
        return -1;
    }

    printf("Integrate of %s from %f to %f", name[idx],  a, b);
    printf(" with interval %f = %f\n", dx, integrate(functions[idx], a, b, dx));

    return 0;
}

ex5.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

typedef int (*pfunc) (const void*, const void*);

typedef struct {
    int x, y;
} P;

int randint(int a, int b) {
    if (b < a) {
        int temp = a;
        a = b;
        b = temp;
    }

    return (rand() % (b - a + 1) + a);
}

void swap(void* a, void* b, size_t size) {
    // int temp = *a;
    // *a = *b;
    // *b = temp;
    void* temp = malloc (size);
    memcpy(temp, a, size);
    memcpy(a, b, size);
    memcpy(b, temp, size);
    free(temp);
}

int partition(void* data, size_t N, size_t size, pfunc cmp, size_t pivot_idx) {
    //swap(&data[pivot_idx], &data[N - 1]);
    swap(data + pivot_idx*size, data + (N-1)*size, size);

    size_t store_idx = 0;
    for (size_t i = 0; i < N; i++) {
        if (cmp(data + i*size, data + (N-1)*size) < 0) {
            //swap(&data[i], &data[store_idx]);
            swap(data + i*size, data + store_idx*size, size);
            store_idx++;
        }
    }

    //swap(&data[store_idx], &data[N - 1]);
    swap(data + store_idx*size, data + (N-1)*size, size);

    return store_idx;
}

void myqsort(void* data, size_t N, size_t size, pfunc cmp) {
    if (N == 0 || N == 1) return;

    int pivot_idx = randint(0, N-1);
    int new_idx = partition(data, N, size, cmp, pivot_idx);
    myqsort(data, new_idx, size, cmp);
    //myqsort(&data[new_idx + 1], N - new_idx - 1, size, cmp);
    myqsort(data + (new_idx+1)*size, N - new_idx - 1, size, cmp);
}

int int_cmp(const void* a, const void* b) {
    int* ia = (int*) a;
    int* ib = (int*) b;
    return *ia - *ib;
}

int str_cmp(const void* a, const void* b) {
    char** sa = (char**) a;
    char** sb = (char**) b;

    return strcmp(*sa, *sb);
}

int P_cmp(const void* a, const void* b) {
    P* pa = (P*) a;
    P* pb = (P*) b;

    if (pa->x != pb->x)
        return pa->x - pb->x;
    return pa->y - pb->y;
}

int main(int argc, char* argv[]) {
    srand(time(NULL));

    int N = 5;
    if (argc == 2)
        N = atoi(argv[1]);

    printf("-----------------------\n");

    // test int
    {
        printf("Test int:\n");
        int data[N];
        for (int i = 0; i < N; i++)
            data[i] = randint(-1000, +1000);

        for (int i = 0; i < N; i++)
            printf("%d\n", data[i]);
        printf("=====\n");

        myqsort(data, N, sizeof(int), int_cmp);

        for (int i = 0; i < N; i++)
            printf("%d\n", data[i]);
        printf("-----------------------\n");
    }

    // test str
    {
        printf("Test string:\n");
        char* data[N];
        for (int i = 0; i < N; i++) {
            int len = randint(2, 8);
            data[i] = (char*) malloc (sizeof(char) * len);
            for (int j = 0; j < len - 1; j++)
                data[i][j] = (char) randint('A', 'Z');
            data[i][len - 1] = '\0';
        }

        for (int i = 0; i < N; i++)
            printf("%s\n", data[i]);
        printf("=====\n");

        myqsort(data, N, sizeof(char*), str_cmp);

        for (int i = 0; i < N; i++)
            printf("%s\n", data[i]);
        printf("-----------------------\n");

        for (int i = 0; i < N; i++)
            free(data[i]);
    }

    // test P
    {
        printf("Test P:\n");
        P data[N];
        for (int i = 0; i < N; i++) {
            data[i].x = randint(-10, +10);
            data[i].y = randint(-10, +10);
        }

        for (int i = 0; i < N; i++)
            printf("(%d, %d)\n", data[i].x, data[i].y);
        printf("=====\n");

        myqsort(data, N, sizeof(P), P_cmp);

        for (int i = 0; i < N; i++)
            printf("(%d, %d)\n", data[i].x, data[i].y);
        printf("-----------------------\n");
    }

    return 0;
}

ex6.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 15

bool map[MAX_N][MAX_N];
int cost[MAX_N][MAX_N];

bool row_flag[MAX_N];
bool md_flag[MAX_N * 2 + 1];
bool sd_flag[MAX_N * 2 + 1];

int cnt;
int max_;
int min_;
int N;

bool is_safe(const int row, const int col) {
    if (row_flag[row] || md_flag[N + (row - col)] || sd_flag[row + col])
        return false;
    return true;
}

void update_flag(const int row, int col, const bool b) {
    row_flag[row] = b;
    md_flag[N + (row - col)] = b;
    sd_flag[row + col] = b;
}

void solve(const int col, const int w) {
    if (col == N) {
        cnt++;
        if (w > max_)
            max_ = w;
        if (w < min_)
            min_ = w;
        return;
    }

    for (int row = 0; row < N; row++) {
        if (is_safe(row, col)) {
            map[row][col] = true;
            update_flag(row, col, true);
            solve(col + 1, w + cost[row][col]);
            update_flag(row, col, false);
            map[row][col] = false;
        }
    }
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &N);
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                scanf("%d", &cost[i][j]);

        memset(map, false, sizeof(map));
        memset(row_flag, false, sizeof(row_flag));
        memset(md_flag, false, sizeof(md_flag));
        memset(sd_flag, false, sizeof(sd_flag));
        cnt = 0;
        max_ = -1;
        min_ = N * N * 9 + 1;

        solve(0, 0);
        printf("cnt: %d\nmax: %d\nmin: %d\n", cnt, max_, min_);
    }
    
    return 0;
}

ex7.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE(X, T) ({ sizeof(((X))) / sizeof(T); })

#define SWAP(A, B, T)                                                          \
    do {                                                                       \
        T temp = ((A));                                                        \
        ((A)) = ((B));                                                         \
        ((B)) = temp;                                                          \
    } while (0)

#define SUM(X, T) \
    ({
        T s = ((X))[0];
        for (int i = 0; i < ((sizeof(((A))) / sizeof(T)))); i++)
            s += ((A))[i];
        s;
    })

int main() {
    int A[3] = {1, 2, 3};
    int b = 1, c = 2;
    SWAP(b, c, int);
    printf("%d, %c\n", b, c);
    printf("SIZE: %d\n", SIZE(A, int));
    printf("SUM: %d\n", SUM(A, int));
    return 0; 
}