challenge-245-hard.c

    /*
        [2015-12-18] Challenge #245 [Hard] Guess Who(is)? https://redd.it/3xdmtw

        XXX --> STILL HAS BUGS

        lookup ip ranges, hopefully quickly. queries go to tightest fit or unknown.
        i didn't try to optimize really so this might be slow.

        my counts aren't comming up right on the provided test case
        i get 6 (instead of 8) for max and 0 (instead of 1) <unknown>
        post it anyways...
    */

    #include <stdio.h>  // fopen(), fclose(), fgetc(), ungetc(), scanf(), printf()
    #include <stdlib.h> // qsort(), exit()
    #include <stdint.h> // uint32_t, uint64_t
    #include <string.h> // strcmp()
    #include <ctype.h>  // isdigit()

    #define DEBUG 1

    typedef struct { uint32_t start; uint32_t end; int cnt; char *name; } rec_t;

    rec_t unknown = { 0, 0, 0, "<unknown>\n" };

    char STRBUFFER[50000000];
    char *str_buff = STRBUFFER;

    rec_t records[50000000];
    int N = 0;

    uint32_t ADDR;

    int read_addr(FILE *f) {
        int sf, d, ch, ok;

        /* rewrite, the old read_addr() turned out to be buggy */

        sf = fscanf(f, "%d", &d); ch = fgetc(f); if(sf != 1 || d < 0 || 255 < d || ch != '.') return 0;
        ADDR = d; ADDR <<= 8;
        sf = fscanf(f, "%d", &d); ch = fgetc(f); if(sf != 1 || d < 0 || 255 < d || ch != '.') return 0;
        ADDR |= d; ADDR <<= 8;
        sf = fscanf(f, "%d", &d); ch = fgetc(f); if(sf != 1 || d < 0 || 255 < d || ch != '.') return 0;
        ADDR |= d; ADDR <<= 8;
        sf = fscanf(f, "%d", &d); ch = fgetc(f); if(sf != 1 || d < 0 || 255 < d || ch != ' ') return 0;
        ADDR |= d;

        return 1;
    }

    int read_record(FILE *f) {
        rec_t tmp;
        int len, ok;

        ok = read_addr(f); if(!ok) return 0; tmp.start = ADDR;
        ok = read_addr(f); if(!ok) return 0; tmp.end = ADDR;

        tmp.name = str_buff;

        fgets(str_buff, 123, f);
        while(*str_buff && *str_buff != '\n') str_buff++; *str_buff = '\0'; str_buff++;
        records[N++] = tmp;
        return 1;
    }

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

    int cmp_rec(void *A, void *B) {
        rec_t *AA = A, *BB = B;
        uint64_t arange, brange;

        arange = AA->start; arange <<= 32; arange += AA->end;
        brange = BB->start; brange <<= 32; brange += BB->end;

        if(arange < brange) return -1;
        if(arange > brange) return  1;
        return 0;
    }

    int cmp_cnt(void *A, void *B) {
        rec_t *AA = A, *BB = B;

        if(AA->cnt < BB->cnt) return -1;
        if(AA->cnt > BB->cnt) return  1;
        return strcmp(AA->name, BB->name);
    }


    int search(uint32_t ip) {
        int lo, hi, mid, i, n, ret;
        uint32_t range, tight;

        if(ip < records[0].start || records[N-1].end < ip) return -1;
        if(records[0].start <= ip && ip <= records[0].end) return 0;

        // find a record PRECEDING our range, followed by linear scan after in the ballpark

        lo = 0; hi = N-1;
        while(lo < hi) {
            mid = (lo + hi) / 2;
            if(records[mid].start < ip) lo = mid;
            if(records[mid].start >=ip) hi = mid;
        }

        n = lo;
        if(n >= N-1) return -1;
        if(records[n+1].start > ip) return -1;
        if(records[n+1].end < ip) return -1;
        n++;

        tight = 0xffffffff;
        for(i = n; i < N; i++) {
            if(ip < records[i].start || records[i].end < ip) break;
            range = records[i].end - records[i].start;
            if(range < tight) { ret = i; tight = range; }
        }

        return ret;
    }

    typedef struct { int cnt; char *name; } report_t;

    report_t reports[100000];
    int R = 0;

    int cmp_report(report_t *A, report_t *B) {
        int x = ( B->cnt - A->cnt );
        if(x == 0) return strcmp(A->name, B->name);
        else return x;
    }

    int main(int argc, char *argv[]) {
        int i, n, ok, done;
        FILE *f;

        char *prev = "<jrjfjfkkfk-nonsense-unique-identifier-NULL-jdjjfjmfjjfjfmjfmmf>";
        int tally = 0;

        if(argc-1 != 2) {
            printf("usage: ./challenge-245 <range-file> <query-file>\n\n");
            exit(1);
        }

        f = fopen(argv[1], "r");
        do { ok = read_record(f); } while(ok);
        fclose(f);

        qsort(records, N, sizeof(rec_t), (cmp_t)cmp_rec);

        f = fopen(argv[2], "r");
        while(1) {
            done = !read_addr(f); if(done) break;
            n = search(ADDR);

            if(n < 0) unknown.cnt++;
            else records[n].cnt++;
        }
        fclose(f);

        qsort(records, N, sizeof(rec_t), (cmp_t)cmp_cnt);

        for(i = 0; 0 < records[i].cnt; i++) {
            if(strcmp(prev, records[i].name) != 0) {
                if(0 < tally) { reports[R].cnt = tally; reports[R++].name = prev; }

                tally = records[i].cnt;
                prev = records[i].name;
            }
            else tally += records[i].cnt;
        }

        qsort(reports, R, sizeof(report_t), (cmp_t)cmp_report);

        for(i = 0; 0 < reports[i].cnt; i++) { printf("%d - %s\n", reports[i].cnt, reports[i].name); }
        printf("%d - %s\n", unknown.cnt, unknown.name);
        return 0;
    }