Answers for greplin coding challenge

greplin.c

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

#define DIM(x) sizeof(x)/sizeof(x[0])
#define IS_SET(x,bit) ((x & (1 << bit)) != 0)

static char level1_data[] = "FourscoreandsevenyearsagoourfaathersbroughtforthonthiscontainentanewnationconceivedinzLibertyanddedicatedtothepropositionthatallmenarecreatedequalNowweareengagedinagreahtcivilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";

static const long level2_data = 227000;

static const long level3_data[] = {
    3,4,9,14,15,19,28,37,47,50,54,56,59,61,70,73,78,81,92,95,97,99
};

static void level1();
static void level2();
static void level3();

static inline int is_pal(const char* s, size_t sz);
static inline long is_prime(long z) ;
static long fib(long z);
static long sum(long z) ;
static void print_set(const long set[], size_t sz);
static long psets(const long set[], size_t sz);

int main() {
    level1();
    level2();
    level3();
}

static void level1() {
    assert(is_pal("a",1));
    assert(is_pal("aa", 2));
    assert(is_pal("aba", 3));
    assert(is_pal("abba", 4));
    assert(is_pal("abcba", 5));
    assert(is_pal("abccba", 6));
    size_t i,j;
    size_t sz = sizeof(level1_data);
    char* best = NULL;
    size_t bestsz = 0;
    char c;
    for (i=0; i < sz ; ++i) {
        for(j=i+1; j < sz; ++j) {
            c = level1_data[j];
            level1_data[j] = 0;
            if (is_pal(&level1_data[i], j-i)) {
                if (j-i > bestsz) {
                    bestsz = j-i;
                    free(best);
                    best = strdup(&level1_data[i]);
                }
            }
            level1_data[j] = c;
        }
    }
    printf("level1: %s\n", best);
    free(best);
}

static void level2() {
    assert(is_prime(3));
    assert(!is_prime(4));
    assert(is_prime(5));
    assert(!is_prime(6));
    assert(is_prime(7));
    assert(!is_prime(8));
    assert(is_prime(113));
    assert(is_prime(3499));
    assert(!is_prime(3498));
    assert(is_prime(30029));
    long p = fib(level2_data);
    long s = sum(p+1);
    printf("level2: X=%d S(X+1)=%d\n", p, s);
}

static void level3() {
    long ret = psets(level3_data, DIM(level3_data));
    printf("level3: %d\n", ret);
}

static inline int is_pal(const char* s, size_t sz)
{
    size_t i, j;
    for(i=0,j=sz-1; j > i; ++i,--j) {
        if (s[i] != s[j])
            return 0;
    }
    return 1;
}

static inline long is_prime(long z) {
    long p;
    for (p=2; p <= sqrt(z); ++p) {
        if (z % p == 0) {
            return 0;
        }
    }
    return 1;
}

static long fib(long z) {
    long p=0;
    long n=1;
    long q;
    while (p <= z || !is_prime(p)) {
        q = p;
        p = n;
        n += q;
    }
    return p;
}

static long sum(long z) {
    long sum = 0;
    long i;
    for(i=2; i < z; ++i) {
        if ((z % i == 0) && is_prime(i)) {
            sum += i;
        }
    }
    return sum;
}

static void print_set(const long set[], size_t sz) {
    size_t i;
    for (i=0; i < sz-1; ++i) {
        printf("%d ", set[i]);
    }
    printf("%d\n", set[sz-1]);
}

static long psets(const long set[], size_t sz) {
    size_t i,j,k;
    long ret = 0;
    long p[sz];
    assert(sz < sizeof(size_t)*8);
    const size_t lim = (2 << (sz-1));
    for (i=lim-1; i > 0 ; --i) {
        k=0;
        for (j=0; j < sz; ++j)
            p[j] = 0;
        long sum = 0;
        long max = -1;
        for (j=sz; j > 0; --j) {
            if (IS_SET(i,j-1)) {
                if (max == -1)
                    max = set[j-1];
                else
                    sum +=  set[j-1];
                p[k++] = set[j-1];
            }
        }
        if (max == sum) {
            ++ret;
            /* print_set(p,k); */
        }
    }
    return ret;
}