p0015_s0.c

problem 15 · 74 lines

/* Solution to Euler Problem 15: Lattice Paths. */
#include "runner.h"

/* Big integer arithmetic using base-10^9 limbs (little-endian) */
#define BASE 1000000000ULL
#define MAXLIMBS 64

typedef struct {
    unsigned long long limbs[MAXLIMBS];
    int len;
} BigInt;

static void bi_set(BigInt *a, unsigned long long val) {
    memset(a->limbs, 0, sizeof(a->limbs));
    a->limbs[0] = val % BASE;
    a->limbs[1] = val / BASE;
    a->len = (a->limbs[1] > 0) ? 2 : 1;
}

static void bi_mul_ll(BigInt *a, unsigned long long x) {
    unsigned long long carry = 0;
    for (int i = 0; i < a->len; i++) {
        unsigned long long cur = a->limbs[i] * x + carry;
        a->limbs[i] = cur % BASE;
        carry = cur / BASE;
    }
    while (carry > 0) {
        if (a->len >= MAXLIMBS) { fprintf(stderr, "BigInt overflow in mul\n"); exit(1); }
        a->limbs[a->len] = carry % BASE;
        carry /= BASE;
        a->len++;
    }
}

static void bi_div_ll(BigInt *a, unsigned long long x) {
    unsigned long long rem = 0;
    for (int i = a->len - 1; i >= 0; i--) {
        unsigned long long cur = rem * BASE + a->limbs[i];
        a->limbs[i] = cur / x;
        rem = cur % x;
    }
    while (a->len > 1 && a->limbs[a->len - 1] == 0) a->len--;
}

static char *bi_to_str(const BigInt *a) {
    /* Upper bound: len * 9 + 1 */
    int bufsize = a->len * 9 + 2;
    char *buf = malloc((size_t)bufsize);
    if (!buf) { fprintf(stderr, "OOM\n"); exit(1); }
    int pos = 0;
    /* Print most significant limb without leading zeros */
    pos += sprintf(buf + pos, "%llu", a->limbs[a->len - 1]);
    /* Remaining limbs with leading zeros */
    for (int i = a->len - 2; i >= 0; i--) {
        pos += sprintf(buf + pos, "%09llu", a->limbs[i]);
    }
    buf[pos] = '\0';
    return buf;
}

const char *solve(int argc, char *argv[]) {
    int n = parse_int(argv[1]);
    /* Closed-form central binomial coefficient: paths through an n×n grid = C(2n, n);
       O(n) big-int mul/div via the multiplicative formula product_{i=1}^{n} (n + i) / i,
       which keeps the running value bounded (the full (2n)! would not fit). */
    BigInt result;
    bi_set(&result, 1ULL);
    for (int i = 1; i <= n; i++) {
        bi_mul_ll(&result, (unsigned long long)(n + i));
        bi_div_ll(&result, (unsigned long long)i);
    }
    return bi_to_str(&result);
}