The Tomb of the Unknown cnile

Previously referred to as 'cnilespammer', it turns out the code author wasn't the spammer at all! To stop him from suing me for slander, I've dedicated a page to his venerable, malloc-addled brain.

unknown-cnile/ucnile-day01.c
unknown-cnile/ucnile-day01.c
#include <stdlib.h>
    #include <stdio.h>
    
    typedef __int128 num_t;
    
    void die(char *str) {
        fprintf(stderr, "[ERROR] %s\n", str);
        exit(-1);
    }
    
    void swap(num_t *a, num_t *b) {
        num_t tmp = *a;
        *a = *b;
        *b = tmp;
    }
    
    // accending order
    void my_qsort(num_t *a, size_t len) {
        switch (len) {
            case 2:
                if (a[0] > a[1]) swap(a, a+1);
            case 0:
            case 1:
                return;
            default:;
                num_t mid = a[0];
                size_t nxt = 1;
                for (size_t i = 1; i < len; i++) {
                    if (a[i] <= mid) {
                        swap(a+nxt, a+i);
                        nxt++;
                    }
                }
                swap(a, a+nxt-1);
                my_qsort(a, nxt-1);
                my_qsort(a+nxt, len-nxt);
        }
    }
    
    int check_for(num_t *a, size_t len, num_t val) {
        if (len == 0) return 0;
        else if (a[len/2] == val) return 1;
        else if (a[len/2] < val) return check_for(a + len/2 + 1, (len-1)/2, val);
        else return check_for(a, len/2, val);
    }
    
    #define TARGET 99920044L
    
    #define MAX_DATA 1024L * 1024L
    
    num_t data_store[MAX_DATA];
    size_t data_pos = 0;
    
    void part_one() {
        my_qsort(data_store, data_pos);
        for (size_t i = 0; i < data_pos; i++) {
            num_t r = TARGET - data_store[i];
            if (check_for(data_store+i, data_pos-i, r)) {
                printf("P1: %lld\n", (long long) (data_store[i] * r));
            }
        }
    }
    
    void print_num(num_t n) {
        if (n == 0) {
            putchar('0');
            return;
        }
        char bank[512];
        bank[511] = '\0';
        char *ptr = bank + 511;
        while (n != 0) {
            *(--ptr) = (n % 10) + '0';
            n /= 10;
        }
        printf("%s", ptr);
    }
    
    void part_two() {
        my_qsort(data_store, data_pos);
        for (size_t i = 0; (i < data_pos) && (data_store[i] <= (TARGET/3)); i++) {
            num_t r = TARGET - data_store[i];
            for (size_t j = i + 1; (j < data_pos) && (data_store[j] <= (r/2)); j++) {
                num_t rr = r - data_store[j];
                if (check_for(data_store+j+1, data_pos-j-1, rr)) {
                    printf("P2: ");
                    print_num(data_store[i] * data_store[j] * rr);
                    printf("\n");
                }
            }
        }
    }
    
    int main(int argc, char **argv) {
        // read input
        FILE *fd = fopen("bb.txt", "r");
        if (fd == NULL) die("failed to read");
        while (1) {
            if (data_pos == MAX_DATA) die("too many numbers");
            long long n;
            switch (fscanf(fd, "%lld", &n)) {
                case EOF:
                    if (ferror(fd)) die("failed to read");
                    goto done;
                case 0:
                    die("failed to match");
            }
            data_store[data_pos] = (num_t) n;
            data_pos++;
        }
        done:
        // part 2
        part_two();
        return 0;
    }
    
unknown-cnile/ucnile-day05.c
unknown-cnile/ucnile-day05.c
#include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <sys/mman.h>
    #include <unistd.h>
    #include <limits.h>
    
    void die(char *str) {
        fprintf(stderr, "[ERROR] %s\n", str);
        exit(-1);
    }
    
    FILE *map_file(const char *filename) {
        int fd;
        if ((fd = open(filename, O_RDONLY)) == -1) die("failed to open file");
        struct stat fd_stat;
        if (fstat(fd, &fd_stat) == -1) die("failed to stat file");
        void *data;
        // never unmapped, probably fine
        if ((data = mmap(NULL,
                         fd_stat.st_size,
                         PROT_READ,
                         MAP_PRIVATE,
                         fd, 0)) == MAP_FAILED) die("failed to map file");
        close(fd);
        return fmemopen(data, fd_stat.st_size, "r");
    }
    
    unsigned int xor_z(unsigned int x) {
        switch (x % 4) {
            case 0: return x;
            case 1: return 1;
            case 2: return x + 1;
            case 3: return 0;
        }
    }
    
    unsigned int xor_range(unsigned int min, unsigned int max) {
        // should underflow on min == 0, resulting in xor_z(min - 1) == xor_z(3) == 0
        return xor_z(min - 1) ^ xor_z(max);
    }
    
    #define SEAT_CNT 1024
    
    int main(int argc, char **argv) {
        // read input
        FILE *fd = map_file("test.txt");
        char data[16];
        unsigned int min = UINT_MAX;
        unsigned int max = 0;
        unsigned int acc = 0;
        while (fgets(data, 16, fd) != NULL) {
            unsigned int sid = 0;
            for (int i = 0; i < 10; i++) {
                sid <<= 1;
                sid |= ((data[i] >> 2) & 1);
            }
            sid ^= SEAT_CNT - 1;
            if (sid > max) max = sid;
            if (sid < min) min = sid;
            acc ^= sid;
        }
        printf("P1: %u\n", max);
        printf("P2: %u\n", acc ^ xor_range(min, max));
        return 0;
    }
    
unknown-cnile/ucnile-day06.c
unknown-cnile/ucnile-day06.c
#include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <sys/mman.h>
    #include <unistd.h>
    
    void die(char *str) {
        fprintf(stderr, "[ERROR] %s\n", str);
        exit(-1);
    }
    
    FILE *map_file(const char *filename) {
        int fd;
        if ((fd = open(filename, O_RDONLY)) == -1) die("failed to open file");
        struct stat fd_stat;
        if (fstat(fd, &fd_stat) == -1) die("failed to stat file");
        void *data;
        // never unmapped, probably fine
        if ((data = mmap(NULL,
                         fd_stat.st_size,
                         PROT_READ,
                         MAP_PRIVATE,
                         fd, 0)) == MAP_FAILED) die("failed to map file");
        close(fd);
        return fmemopen(data, fd_stat.st_size, "r");
    }
    
    int main(int argc, char **argv) {
        // read input
        FILE *fd = map_file("test.txt");
        char data[64];
        int any_acc = 0;
        int all_acc = 0;
        unsigned int cur_any = 0;
        unsigned int cur_all = ~0;
        while (fgets(data, 64, fd) != NULL) {
            if (data[0] < 'a') {
                any_acc += __builtin_popcount(cur_any);
                all_acc += __builtin_popcount(cur_all);
                cur_any = 0;
                cur_all = ~0;
            } else {
                unsigned int row = 0;
                for (int i = 0; data[i] >= 'a'; i++) {
                    row |= 1 << (data[i] - 'a');
                }
                cur_any |= row;
                cur_all &= row;
            }
        }
        any_acc += __builtin_popcount(cur_any);
        all_acc += __builtin_popcount(cur_all);
        printf("P1: %d\n", any_acc);
        printf("P2: %d\n", all_acc);
        return 0;
    }
    
unknown-cnile/ucnile-day07.c
unknown-cnile/ucnile-day07.c
#include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <sys/mman.h>
    #include <unistd.h>
    #include <stdint.h>
    
    void die(char *str) {
        fprintf(stderr, "[ERROR] %s\n", str);
        exit(-1);
    }
    
    FILE *map_file(const char *filename) {
        int fd;
        if ((fd = open(filename, O_RDONLY)) == -1) die("failed to open file");
        struct stat fd_stat;
        if (fstat(fd, &fd_stat) == -1) die("failed to stat file");
        void *data;
        // never unmapped, probably fine
        if ((data = mmap(NULL,
                         fd_stat.st_size,
                         PROT_READ,
                         MAP_PRIVATE,
                         fd, 0)) == MAP_FAILED) die("failed to map file");
        close(fd);
        return fmemopen(data, fd_stat.st_size, "r");
    }
    
    #define MAX_DATA 4096
    
    struct item_entry {
        uint32_t bag_id;
        uint32_t bag_cnt;
    };
    
    struct bag {
        uint32_t bag_id;
        int32_t p1_state;
        uint32_t contain_cnt;
        struct item_entry contain[16];
    };
    
    struct bag data[MAX_DATA];
    int data_len = 0;
    
    #define MAX_LINE 256
    
    #define MOD_HASH(acc, c) acc = (((acc) << 5) - (acc)) ^ (c)
    
    int compare_bag(const void *a, const void *b) {
        uint32_t an = ((struct bag *) a)->bag_id;
        uint32_t bn = ((struct bag *) b)->bag_id;
        // assume no collisions
        if (an < bn) return -1;
        if (an > bn) return 1;
        __builtin_trap();
    }
    
    uint32_t scan_color(char **s) {
        uint32_t acc = 0;
        while (**s != ' ') {
            acc = ((acc << 5) - acc) ^ *((*s)++);
        }
        acc = ((acc << 5) - acc) ^ ' ';
        (*s)++;
        while (**s > ' ') {
            acc = ((acc << 5) - acc) ^ *((*s)++);
        }
        return acc;
    }
    
    int find_bag_idx(uint32_t bag_id) {
        int min = 0;
        int max = data_len - 1;
        while (1) {
            int pick = (min + max) / 2;
            if (data[pick].bag_id == bag_id) return pick;
            else if (min == max) __builtin_trap();
            else if (data[pick].bag_id < bag_id) min = pick + 1;
            else if (data[pick].bag_id > bag_id) max = pick - 1;
        }
    }
    
    static uint32_t shiny_gold_hash;
    
    int is_p1_mark_idx(int idx);
    
    int is_p1_mark(int id) {
        if (id == shiny_gold_hash) return 1;
        return is_p1_mark_idx(find_bag_idx(id));
    }
    
    int is_p1_mark_idx(int idx) {
        if (data[idx].p1_state == -1) {
            for (int i = 0; i < data[idx].contain_cnt; i++) {
                if (is_p1_mark(data[idx].contain[i].bag_id)) {
                    return data[idx].p1_state = 1;
                }
            }
            return data[idx].p1_state = 0;
        } else return data[idx].p1_state;
    }
    
    int count_bag(uint32_t id) {
        int idx = find_bag_idx(id);
        int acc = 1;
        for (int i = 0; i < data[idx].contain_cnt; i++) {
            acc += count_bag(data[idx].contain[i].bag_id) * data[idx].contain[i].bag_cnt;
        }
        return acc;
    }
    
    void calc_sgh() {
        char *ptr = "shiny gold";
        shiny_gold_hash = scan_color(&ptr);
    }
    
    int main(int argc, char **argv) {
        calc_sgh();
        // read input
        FILE *fd = map_file("test.txt");
        char line[MAX_LINE];
        while (fgets(line, MAX_LINE, fd) != NULL) {
            if (line[0] <= '\n') continue;
            char *ptr = line;
            uint32_t head_id = scan_color(&ptr);
            ptr += 14;
            if (!strcmp(ptr, "no other bags.\n")) {
                data[data_len++] = (struct bag) {.bag_id = head_id, .p1_state = 0, .contain_cnt = 0};
            } else {
                struct bag *cur_bag = data + data_len;
                *cur_bag = (struct bag) {.bag_id = head_id, .p1_state = -1, .contain_cnt = 0};
                do {
                    while (*ptr < '0') ptr++;
                    struct item_entry *cur_ent = cur_bag->contain + (cur_bag->contain_cnt++);
                    cur_ent->bag_cnt = 0;
                    while (*ptr != ' ') {
                        cur_ent->bag_cnt *= 10;
                        cur_ent->bag_cnt += *ptr - '0';
                        ptr++;
                    }
                    ptr++;
                    cur_ent->bag_id = scan_color(&ptr);
                    ptr += 4;
                    if (*ptr == 's') ptr++;
                } while (*ptr != '.');
                data_len++;
            }
        }
        int p1_acc = 0;
        qsort(data, data_len, sizeof(struct bag), &compare_bag);
        for (int i = 0; i < data_len; i++) {
            p1_acc += is_p1_mark_idx(i);
        }
        printf("P1: %d\n", (int) p1_acc);
        printf("P2: %d\n", count_bag(shiny_gold_hash) - 1);
        return 0;
    }
    
unknown-cnile/ucnile-day08.c
unknown-cnile/ucnile-day08.c
#include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <sys/mman.h>
    #include <unistd.h>
    #include <stdint.h>
    
    void die(char *str) {
        fprintf(stderr, "[ERROR] %s\n", str);
        exit(-1);
    }
    
    FILE *map_file(const char *filename) {
        int fd;
        if ((fd = open(filename, O_RDONLY)) == -1) die("failed to open file");
        struct stat fd_stat;
        if (fstat(fd, &fd_stat) == -1) die("failed to stat file");
        void *data;
        // never unmapped, probably fine
        if ((data = mmap(NULL,
                         fd_stat.st_size,
                         PROT_READ,
                         MAP_PRIVATE,
                         fd, 0)) == MAP_FAILED) die("failed to map file");
        close(fd);
        return fmemopen(data, fd_stat.st_size, "r");
    }
    
    #define MAX_DATA 4096
    
    #define INS_ACC 0
    #define INS_JMP 1
    #define INS_NOP 2
    
    struct ins {
        uint32_t op;
        uint32_t val;
    };
    
    struct ins asm_data[MAX_DATA];
    int asm_mark[MAX_DATA];
    int asm_len = 0;
    
    #define MAX_LINE 256
    
    int exec_asm() {
        int pos = 0, acc = 0;
        while (1) {
            if ((pos > asm_len) || (pos < 0)) return 0;
            if (pos == asm_len) {
                printf("P2: %d\n", acc);
                exit(0);
            } else if (asm_mark[pos]) {
                memset(asm_mark, 0, sizeof(asm_mark));
                return acc;
            }
            asm_mark[pos] = 1;
            switch (asm_data[pos].op) {
                case INS_ACC: acc += asm_data[pos].val; pos++; break;
                case INS_JMP: pos += asm_data[pos].val; break;
                case INS_NOP: pos++; break;
            }
        }
    }
    
    int main(int argc, char **argv) {
        // read input
        FILE *fd = map_file("test.txt");
        char line[MAX_LINE];
        while (fgets(line, MAX_LINE, fd) != NULL) {
            char optxt[8];
            int arg;
            if (sscanf(line, "%s %d", optxt, &arg) != 2) break;
            asm_data[asm_len].val = arg;
            switch (*optxt) {
                case '\n':
                case '\0': break;
                case 'a': asm_data[asm_len++].op = INS_ACC; break;
                case 'j': asm_data[asm_len++].op = INS_JMP; break;
                case 'n': asm_data[asm_len++].op = INS_NOP; break;
            }
        }
        printf("P1: %d\n", exec_asm());
        for (int i = 0; i < asm_len; i++) {
            if (asm_data[i].op == INS_ACC) continue;
            asm_data[i].op ^= 3;
            exec_asm();
            asm_data[i].op ^= 3;
        }
        return 0;
    }
    
unknown-cnile/ucnile-day11.c
unknown-cnile/ucnile-day11.c
#include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <sys/mman.h>
    #include <unistd.h>
    #include <stdint.h>
    #include <limits.h>
    
    void die(char *str) {
        fprintf(stderr, "[ERROR] %s\n", str);
        exit(-1);
    }
    
    FILE *map_file(const char *filename) {
        int fd;
        if ((fd = open(filename, O_RDONLY)) == -1) die("failed to open file");
        struct stat fd_stat;
        if (fstat(fd, &fd_stat) == -1) die("failed to stat file");
        void *data;
        // never unmapped, probably fine
        if ((data = mmap(NULL,
                         fd_stat.st_size,
                         PROT_READ,
                         MAP_PRIVATE,
                         fd, 0)) == MAP_FAILED) die("failed to map file");
        close(fd);
        return fmemopen(data, fd_stat.st_size, "r");
    }
    
    #define MAX_X 128
    #define MAX_Y 4096
    
    uint8_t data_orig[MAX_X*MAX_Y];
    uint8_t data_1[MAX_X*MAX_Y];
    uint8_t data_2[MAX_X*MAX_Y];
    uint8_t *data_cur = data_orig;
    uint8_t *data_nxt = data_1;
    int row_cnt = 0;
    
    #define MAX_LINE 512
    
    #define FLOOR 0
    #define EMPTY 1
    #define FULL 2
    
    void restore() {
        data_cur = data_orig;
        data_nxt = data_1;
    }
    
    void swap() {
        data_cur = (data_cur == data_1) ? data_2 : data_1;
        data_nxt = (data_nxt == data_1) ? data_2 : data_1;
    }
    
    uint8_t *next_seat(int x, int y, int dx, int dy, int is_p1) {
        while (1) {
            x += dx;
            y += dy;
            if ((x < 0) || (x >= MAX_X) || (y < 0) || (y >= row_cnt)) return NULL;
            uint8_t *r = data_cur + (y*MAX_X+x);
            if (*r != FLOOR) return r;
            if (is_p1) return NULL;
        }
    }
    
    int find_adj(int is_p1, int x, int y) {
        int acc = 0;
        for (int dx = -1; dx < 2; dx++) {
            for (int dy = -1; dy < 2; dy++) {
                if (dx | dy) {
                    uint8_t *ptr = next_seat(x, y, dx, dy, is_p1);
                    if (ptr && (*ptr == FULL)) acc++;
                }
            }
        }
        return acc;
    }
    
    int tick(int is_p1) {
        for (int y = 0; y < row_cnt; y++) {
            for (int x = 0; x < MAX_X; x++) {
                switch (data_cur[y*MAX_X+x]) {
                    case FLOOR: data_nxt[y*MAX_X+x] = FLOOR; break;
                    case EMPTY: data_nxt[y*MAX_X+x] = find_adj(is_p1, x, y) ? EMPTY : FULL; break;
                    case FULL: data_nxt[y*MAX_X+x] = ((find_adj(is_p1, x, y) + is_p1) >= 5) ? EMPTY : FULL; break;
                    default: __builtin_trap();
                }
            }
        }
        uint8_t *old_nxt = data_nxt;
        int r = !!memcmp(data_cur, data_nxt, row_cnt*MAX_X);
        swap();
        return r;
    }
    
    void prt() {
        for (int y = 0; y < row_cnt; y++) {
            for (int x = 0; x < MAX_X; x++)
            switch (data_cur[y*MAX_X+x]) {
                case FLOOR: putchar('.'); break;
                case EMPTY: putchar('L'); break;
                case FULL: putchar('@'); break;
            }
            putchar('\n');
        }
    }
    
    int cnt_occ() {
        int acc = 0;
        for (int i = 0; i < MAX_X*row_cnt; i++) {
            acc += data_cur[i] == FULL;
        }
        return acc;
    }
    
    int main(int argc, char **argv) {
        // read input
        FILE *fd = map_file("test.txt");
        char line[MAX_LINE];
        while (fgets(line, MAX_LINE, fd) != NULL) {
            for (int i = 0; line[i] > '\n'; i++) {
                if (i == MAX_X) die("overflow");
                uint8_t v;
                switch (line[i]) {
                    case 'L': v = EMPTY; break;
                    case '#': v = FULL; break;
                    default: v = FLOOR; break;
                }
                data_orig[MAX_X*row_cnt+i] = v;
            }
            row_cnt++;
        }
        // part one
        while (tick(1)) {}
        printf("P1: %d\n", cnt_occ());
        restore();
        // part two
        while (tick(0)) {}
        printf("P2: %d\n", cnt_occ());
        return 0;
    }
    
unknown-cnile/ucnile-day13.c
unknown-cnile/ucnile-day13.c
#include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <sys/stat.h>
    #include <fcntl.h>
    #include <sys/mman.h>
    #include <unistd.h>
    #include <complex.h>
    
    void die(char *str) {
        fprintf(stderr, "[ERROR] %s\n", str);
        exit(-1);
    }
    
    FILE *map_file(const char *filename) {
        int fd;
        if ((fd = open(filename, O_RDONLY)) == -1) die("failed to open file");
        struct stat fd_stat;
        if (fstat(fd, &fd_stat) == -1) die("failed to stat file");
        void *data;
        // never unmapped, probably fine
        if ((data = mmap(NULL,
                         fd_stat.st_size,
                         PROT_READ,
                         MAP_PRIVATE,
                         fd, 0)) == MAP_FAILED) die("failed to map file");
        close(fd);
        return fmemopen(data, fd_stat.st_size, "r");
    }
    
    #define MAX_LINE 32
    
    int main(int argc, char **argv) {
        // read input
        FILE *fd = map_file("test.txt");
        char line[MAX_LINE];
        _Complex int p1_s = 0;
        _Complex int p1_v = 1;
        _Complex int p2_s = 0;
        _Complex int p2_v = 10+1i;
        while (fgets(line, MAX_LINE, fd) != NULL) {
            char c;
            unsigned int n;
            if (sscanf(line, "%c%u", &c, &n) != 2) break;
    // generates case for cardinal direction
    #define PMSK(c, v) case c: p1_s += n * v; p2_v += n * v; break;
    // generates case for ccw angle change
    #define RMSK(a, v) case a: p1_v *= v; p2_v *= v; break;
    // generates switch statements with trap on default
    #define SW_SAFE_END default: __builtin_trap(); }
    #define SW_SAFE(sw, body) switch (sw) { body SW_SAFE_END
            switch (c) {
                PMSK('N', 1i) PMSK('S', -1i) PMSK('E', 1) PMSK('W', -1)
                case 'R': n = 360 - n;
                case 'L':
                    SW_SAFE(n, RMSK(90, 1i) RMSK(180, -1) RMSK(270, -1i))
                    break;
                case 'F':
                    p1_s += n * p1_v;
                    p2_s += n * p2_v;
                    break;
            SW_SAFE_END
        }
        // part one
        printf("P1: %d\n", abs(__real__ p1_s) + abs(__imag__ p1_s));
        // part two
        printf("P2: %d\n", abs(__real__ p2_s) + abs(__imag__ p2_s));
        return 0;
    }
    

Tags: