Data-Centric Computing

#include <stdio.h>

struct line {
    // Fill in the members to represent a line.
    // Can you represent horizontal, vertical, and slanted lines?
    // SOLUTION:
    // We will use values of a, b, c from ax + by + c = 0.
    double a, b, c;
};

int main()
{
    // Fill these so that these become valid lines.
    // Notice that both a and b should not be 0.
    struct line L1 = { .a = 0, .b = 1, .c = 3 };
    struct line L2 = { .a = 0, .b = 2, .c = 6 };

    // Write code here to check whether L1 and L2 intersect.
    // Change L1 and L2 and test various cases.
    // And, print whether or not they do.
    double det = L1.a * L2.b - L2.a * L1.b;
    if (det != 0) {
        printf("The lines intersect at a unique point.\n");
    } else {
        if (L1.a * L2.c == L2.a * L1.c && L1.b * L2.c == L2.b * L1.c) {
            printf("The lines are coincident.\n");
        } else {
            printf("The lines are parallel.\n");
        }
    }

    return 0;
}

#include <stdio.h>

struct point {
    double x;
    double y;
};

struct rectangle {
    // Fill here.
};

struct circle {
    // Fill here.
};

int main()
{

    // Fill in members so that you get valid rectangles and circles.
    struct rectangle R1 = {};
    struct rectangle R2 = {};

    struct circle C1 = {};
    struct circle C2 = {};

    // Write code here to check whether R1 and R2 intersect and print
    // the result.

    // Write code here to check whether C1 and C2 intersect and print
    // the result.

    return 0;
}

#include <stdio.h>

struct point {
    double x;
    double y;
};

int main()
{
    // Fill the array so that you have at least five points.
    struct point ps[] = {
        { .x = 0, .y = 0 },
        { .x = 0, .y = 1 },
        { .x = 1, .y = 0 },
        { .x = 2, .y = 0 },
        { .x = 1, .y = 1 },
    };
    struct point farthest;

    // Write code here to compute the farthest point from origin in the
    // array ps into the variable farthest.
    farthest = ps[0];
    for (size_t i = 1; i < sizeof(ps)/sizeof(ps[0]); ++i) {
        if (ps[i].x*ps[i].x + ps[i].y*ps[i].y
            > farthest.x*farthest.x + farthest.y*farthest.y)
            farthest = ps[i];
    }

    printf("The farthest point is (%.2lf, %.2lf).\n", farthest.x, farthest.y);

    return 0;
}

#include <stdio.h>

int main()
{
    int a = 14, b = 25;
    int *min;
    int *max;

    // Write code here so that the following printf works as
    // expected. Do not change the values of a and b.
    if (a < b) {
        min = &a;
        max = &b;
    } else {
        min = &b;
        max = &a;
    }
    printf("min = %d, max = %d\n", *min, *max);

    return 0;
}

#include <stdio.h>

int main()
{
    // Fill the array with some elements.
    int xs[] = { 3, 9, -5, 6, 4, -1, 0, 4, 0, 2 };

    // Write code here so that the elements in xs are reversed.
    for (
         size_t i = 0, j = sizeof(xs)/sizeof(xs[0]) - 1;
         i < j;
         ++i, --j
         ) {
        int t = xs[j];
        xs[j] = xs[i];
        xs[i] = t;
    }

    // Use size_t for indexing into arrays.
    for (size_t i = 0; i < sizeof(xs)/sizeof(xs[0]); ++i) {
        printf("%d ", xs[i]);
    }

    return 0;
}

#include <stdio.h>

int main()
{
    // Fill the array with some elements.
    int xs[] = { 3, 9, -5, 6, 4, -1, 0, 4, 0, 2 };
    int positive = 0, negative = 0, zero = 0;

    // Modift the code below so that everything works as expected.
    for (size_t i = 0; i < sizeof(xs)/sizeof(xs[0]); ++i) {
        if (xs[i] > 0) ++positive;
        else if (xs[i] < 0) ++negative;
        else ++zero;
    }

    printf("The array has %d positive elements, %d negative elements, and %d zeroes.\n", positive, negative, zero);

    return 0;
}

void drop_to_x_axis(struct point p)
{
    p.x = 0;
}

void drop_to_x_axis(struct point *p)
{
    p->y = 0;
}

int average_age(struct person *ps, int n)
{
    double a = 0.0;

    for (size_t i = 0; i < n; ++i) {
        a += ps[i].age;
    }

    return a/n;
}

struct point midpoint(struct point p1, struct point p2);
void midpoint(struct point p1, struct point p2, struct point *p3);

struct point midpoint(struct point p1, struct point p2)
{
    return (struct point) {
        .x = (p1.x + p2.x) / 2,
        .y = (p1.y + p2.y) / 2
    };
}

void midpoint(struct point p1, struct point p2, struct point *p3)
{
    *p3 = (struct point) {
        .x = (p1.x + p2.x) / 2,
        .y = (p1.y + p2.y) / 2
    };
}

struct point intersection(struct line l1, struct line l2);
void intersection(struct line l1, struct line l2, struct point *p);

bool intersection(struct line l1, struct line l2, struct point *p);

int i = 0;
int *p = &i;
int **q = &p;

**q = 1;
printf("%d\n", i);

#include <stdio.h>

void swap(int *x, int *y)
{
    int t = *y;
    *y = *x;
    *x = t;
}

int main()
{
    int i = 10, j = 5;
    swap(&i, &j);
    printf("%d %d\n", i, j);
    return 0;
}

#include <stdio.h>

int sum(int *xs, int n)
{
    int s = 0;
    for (size_t i = 0; i < n; ++i) s += xs[i];
    return s;
}

int main()
{
    int xs[] = { 2, 3, 5, 7, 11, 13 };
    printf("%d %d\n", sum(xs, 6), sum(xs + 2, 3));
    return 0;
}

#include <stdio.h>
#include <assert.h>

void minmax(int xs[], int n, int *min, int *max)
{
    assert(min && max);

    if (n <= 0) return;

    /* initialize */ *min = *max = xs[0];

    size_t i;
    for (i = 1; i < n-1; i += 2) {
        int m, M;

        if (xs[i] < xs[i+1]) {
            m = xs[i];
            M = xs[i+1];
        } else {
            m = xs[i+1];
            M = xs[i];
        }

        if (m < *min) *min = m;
        if (M > *max) *max = M;
    }

    if (i < n) {
      if (xs[i] < *min) *min = xs[i];
      if (xs[i] > *max) *max = xs[i];
    }
}

int main()
{
    int xs[] = { 0, 5, 20, 8, -5, 3, 9, -14, 7 };
    int m, M;

    minmax(xs, 9, &m, &M);
    printf("%d %d\n", m, M);

    minmax(xs, 7, &m, &M);
    printf("%d %d\n", m, M);

    return 0;

}

int *range(int start, int stop, int step);

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

struct Range
{
    int *array;
    size_t size;
};

struct Range range(int start, int stop, int step)
{
    if (step == 0) {
        return (struct Range) { NULL, 0 };
    }

    size_t length = 0;

    if (step > 0) {
        length = (stop > start) ? (stop - start + step - 1) / step : 0;
    } else {
        length = (start > stop) ? (start - stop - step - 1) / -step : 0;
    }

    int *arr = malloc(length * sizeof(int));
    if (arr == NULL) {
        return (struct Range) { NULL, 0 };
    }

    for (size_t i = 0; i < length; ++i) {
        arr[i] = start + i * step;
    }

    return (struct Range) { arr, length };
}

void free_range(struct Range r) {
    free(r.array);
}

void print_range(struct Range r) {
    printf("(");
    for (size_t i = 0; i < r.size; ++i) {
        printf("%d, ", r.array[i]);
    }
    printf(")\n");
}

int main() {
    struct Range r = range(0, 10, 1);
    if (r.array) print_range(r);
    free_range(r);

    r = range(5, -10, -3);
    if (r.array) print_range(r);
    free_range(r);

    return 0;
}

int *prime_factors(int n);

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

int* prime_factors(int n)
{
    if (n <= 1)
        return NULL;

    int *factors = malloc(8 * sizeof(int) * sizeof(int));
    int index = 0;

    while (n % 2 == 0) {
        factors[index++] = 2;
        n /= 2;
    }

    for (int i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
            factors[index++] = i;
            n /= i;
        }
    }

    if (n > 2)
        factors[index++] = n;

    factors[index] = 0;

    return factors;
}

void print_prime_factors(int *factors)
{
    int i;
    for (i = 0; factors[i+1] != 0; i++)
        printf("%d * ", factors[i]);
    printf("%d\n", factors[i]);
}

int main()
{
    int xs[] = { 13, 39, 56, 1000007, 1000000007, 0 };

    for (size_t i = 0; xs[i]; ++i) {
      int *factors = prime_factors(xs[i]);

      if (factors != NULL) {
        printf("%12d = ", xs[i]);
        print_prime_factors(factors);
      }

      free(factors);
    }

    return 0;
}

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

int main()
{
    int n = 30;

    bool *elts = malloc(n * sizeof(bool));

    for (size_t i = 0; i < n; ++i) elts[i] = true;

    for (size_t d = 2; d < n; ++d) {
        if (!elts[d]) continue;

        for (size_t m = 2 * d; m < n; m += d) {
            elts[m] = false;
        }
    }

    printf("primes under %d: (", n);
    for (size_t i = 2; i < n; ++i) {
        if (elts[i]) printf("%d, ", i);
    }
    printf(")\n");
}

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

size_t next_alive(bool *persons, size_t n, size_t cur)
{
    cur = (cur + 1) % n;
    while (!persons[cur]) cur = (cur + 1) % n;
    return cur;
}

size_t josephus(size_t n, size_t k)
{
    bool *persons = malloc(n * sizeof(bool));
    for (size_t i = 0; i < n; ++i) persons[i] = true;

    size_t ndead = 0;
    size_t cur = 0;
    while (ndead < n-1) {
        size_t i = 1;
        while (i < k) {
            ++i;
            cur = next_alive(persons, n, cur);
        }
        persons[cur] = false;
        ++ndead;
        cur = next_alive(persons, n, cur);
    }
    return cur+1;
}

int main()
{
    struct { size_t n, k; } xs[] = {
        { .n = 41, .k = 3 },
        { .n = 10, .k = 2 },
        { .n = 15, .k = 2 },
    };
    for (size_t i = 0; i < sizeof(xs)/sizeof(xs[0]); ++i)
        printf (
                "josephus(%zu, %zu) = %zu.\n",
                xs[i].n, xs[i].k,
                josephus(xs[i].n, xs[i].k));
    return 0;
}

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

int *e(int ndigits)
{
    int n = ndigits + 2; // See Lemma 3.

    // We use A[1],...A[n] as in the algorithm.
    // A[0] will store the generated digit.
    int *A = malloc((n + 1) * sizeof(int));
    assert(A);

    int *digits = malloc(n * sizeof(int));
    assert(digits);

    for (size_t i = 1; i <= n; ++i) {
        A[i] = 1;
    }

    for (size_t i = 0; i < n; ++i) {
        A[0] = 0;

        // Multiply by 10.
        for (size_t j = 1; j <= n; ++j) {
            A[j] *= 10;
        }

        // Take the fractional part.
        for (size_t j = n; j >= 1; --j) {
            int q = A[j] / (j + 1);
            A[j] %= j + 1;
            A[j-1] += q;
        }

        // Output the next digit.
        digits[i] = A[0];
    }

    free(A);
    return digits;
}

void show_e(int ndigits)
{
    int *xs = e(ndigits);
    printf("e is approximately 2.");
    for (size_t i = 0; i < ndigits; ++i) {
        printf("%d", xs[i]);
    }
    free(xs);
}

int main()
{
    show_e(10);
    return 0;
}

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

struct bignum {
    int *digits;
    size_t ndigits;
};

struct bignum make(const char *s)
{
    size_t n = strlen(s);
    int *digits = malloc(n * sizeof(int));
    size_t i = n-1;
    size_t j = 0;
    while (j < n) {
        digits[j] = s[i] - '0';
        --i;
        ++j;
    }
    return (struct bignum) {
        .digits = digits,
        .ndigits = n
    };
}

size_t max(size_t a, size_t b)
{
    return a >= b ? a : b;
}

struct bignum add(struct bignum a, struct bignum b)
{
    size_t an = a.ndigits;
    size_t bn = b.ndigits;
    size_t cn = max(an, bn) + 1;

    int *c = malloc(cn * sizeof(int));

    size_t i = 0, j = 0, k = 0;
    int carry = 0;
    while (i < an && j < bn) {
        int d = a.digits[i++] + b.digits[j++] + carry;
        if (d > 9) {
            c[k++] = d - 10;
            carry = 1;
        } else {
            c[k++] = d;
            carry = 0;
        }
    }
    while (i < an) {
        c[k++] = a.digits[i++] + carry;
        carry = 0;
    }
    while (j < bn) {
        c[k++] = b.digits[j++] + carry;
        carry = 0;
    }
    if (carry)
        c[k++] = carry;
    return (struct bignum) {
        .digits = c,
        .ndigits = k
    };
}

bool bignum_eq(struct bignum a, struct bignum b)
{
    if (a.ndigits != b.ndigits) return false;
    for (size_t i = 0; i < a.ndigits; ++i)
        if (a.digits[i] != b.digits[i]) return false;
    return true;
}

bool bignum_le(struct bignum a, struct bignum b)
{
    if (a.ndigits < b.ndigits) return true;
    if (b.ndigits < a.ndigits) return false;
    for (size_t i = 1; i <= a.ndigits; ++i)
            if (a.digits[a.ndigits-i] < b.digits[a.ndigits-i])
                    return true;
            else if (b.digits[a.ndigits-i] < a.digits[a.ndigits-i])
                    return false;
    return true;
}

int bignum_cmp(struct bignum a, struct bignum b)
{
    if (bignum_eq(a, b)) return 0;
    if (bignum_le(a, b)) return -1;
    return 1;
}

void print_bignum(struct bignum a)
{
    for (size_t i = 1; i <= a.ndigits; ++i)
        printf("%d", a.digits[a.ndigits-i]);
}

int main()
{
    struct bignum a = make("9999999999");
    struct bignum b = make("9999999999");
    print_bignum(a); printf(" + "); print_bignum(b);
    printf(" = "); print_bignum(add(a, b)); printf(".\n");

    struct bignum n1 = make("1000"), n2 = make("999");
    printf("1000 cmp  999 = %d.\n", bignum_cmp(n1, n2));
    printf(" 999 cmp 1000 = %d.\n", bignum_cmp(n2, n1));
    printf("1000 cmp 1000 = %d.\n", bignum_cmp(n1, n1));
    return 0;
}

int a = 9999999999;
int b = 9999999999;
printf("%d + %d = %d.\n", a, b, a+b);