aoc2025/day2.c

#include "lib.h"

#define DBG 0

static
unsigned char input[] = {
#embed "day2_input.txt"
};

static
unsigned char test[] = {
#embed "day2_test.txt"
};


struct id {
    size_t len;
    bcdint v;
};

static
struct id next_palindrome_part1(struct id s) {
    if (s.len % 2 == 1) {
        size_t len = s.len + 1;
        unsigned high_shift = (len / 2) * 4;

        bcdint high = 1 << (high_shift - 4);

        return (struct id) {
            .len = len,
            .v = (high << high_shift) | high
        };
    }

    unsigned high_shift = (s.len / 2) * 4;
    bcdint   low_mask = (1 << high_shift) - 1;

    bcdint high = s.v >> high_shift;
    bcdint low =  s.v & low_mask;

    if (low > high)
        high = bcdadd(high, 1);

    return (struct id) {
        .len = s.len,
        .v = (high << high_shift) | high
    };
}

static
bcdint do_part1(size_t file_len, unsigned char file[file_len]) {
    unsigned char *src = file, *tmp;
    bcdint result = 0;

#if DBG
    print("\n");
#endif

do {
#if DBG
    print_watch_ptr(src);
    print("\t");
    print(str(src) ":");
    for (size_t i = 0; i < 2; i++) {
        print(" ");
        print_hex_char(src[i]);
    }
    print("\n");
#endif

    tmp = src;
    bcdint rs = grabbcd(src, &src);
    struct id first = {
        .len = src - tmp,
        .v = rs
    };

    src++;

    tmp = src;
    bcdint re = grabbcd(src, &src);

    src++;

#if DBG
    printh(rs);
    print(" to ");
    printh(re);
    print("\n");
#endif

struct id next = first;
do {
    next = next_palindrome_part1(next);
    if (next.v <= re) {
        result = bcdadd(result, next.v);
#if DBG
        print_watch_hex(next.v);
        print("\t");
        print_watch_hex(next.len);
        print("\t");
        print_watch_hex(result);
        print("\n");
#endif
    }
    bcdint tmp = bcdadd(next.v, 1);
    for (bcdint chk = next.v; chk > 0; chk >>= 4) {
        if ((chk & 0xF) != 9) goto no_len_change;
    }
    next.len++;
no_len_change:
    next.v = tmp;
} while (next.v <= re);

#if DBG
    print("reached ");
    printh(re);
    print("\n");
#endif

} while (src != &file[file_len]);

    return result;
}

static
struct id next_palindrome_part2(struct id s) {
    bcdint best = -1;

    for (unsigned i = 2; i <= s.len; i++) {
        if (s.len % i == 0) {
            unsigned high_shift = (s.len / i) * 4;

            bcdint high = s.v >> (high_shift * (i - 1));

            for (int j = i - 2; j >= 0; j--) {
                bcdint low = (s.v >> (high_shift * (j))) & ((1 << high_shift) - 1);

                if (low < high) {
                    break;
                } else if (low > high) {
                    high = bcdadd(high, 1);
                    break;
                }
            }

            bcdint next = 0;
            for (unsigned j = 0; j < i; j++) {
                next |= high << (high_shift * j);
            }

            if (next < best) {
                best = next;
            }
        }
    }

    if (best != -1) {
        return (struct id) {
            .len = s.len,
            .v = best
        };
    }

    size_t len = s.len + 1;
    unsigned high_shift = (len / 2) * 4;

    bcdint high = 1 << (high_shift - 4);

    return (struct id) {
        .len = len,
        .v = (high << high_shift) | high
    };
}

static
bcdint do_part2(size_t file_len, unsigned char file[file_len]) {
    unsigned char *src = file, *tmp;
    bcdint result = 0;

#if DBG
    print("\n");
#endif

do {
#if DBG
    print_watch_ptr(src);
    print("\t");
    print(str(src) ":");
    for (size_t i = 0; i < 2; i++) {
        print(" ");
        print_hex_char(src[i]);
    }
    print("\n");
#endif

    tmp = src;
    bcdint rs = grabbcd(src, &src);
    struct id first = {
        .len = src - tmp,
        .v = rs
    };

    src++;

    tmp = src;
    bcdint re = grabbcd(src, &src);

    src++;

#if DBG
    printh(rs);
    print(" to ");
    printh(re);
    print("\n");
#endif

struct id next = first;
do {
    next = next_palindrome_part2(next);
    if (next.v <= re) {
        result = bcdadd(result, next.v);
#if DBG
        print_watch_hex(next.v);
        print("\t");
        print_watch_hex(next.len);
        print("\t");
        print_watch_hex(result);
        print("\n");
#endif
    }
    bcdint tmp = bcdadd(next.v, 1);
    for (bcdint chk = next.v; chk > 0; chk >>= 4) {
        if ((chk & 0xF) != 9) goto no_len_change;
    }
    next.len++;
no_len_change:
    next.v = tmp;
} while (next.v <= re);

#if DBG
    print("reached ");
    printh(re);
    print("\n");
#endif

} while (src != &file[file_len]);

    return result;
}

#define RUN_TEST1 1
#define RUN_PART1 1
#define RUN_TEST2 1
#define RUN_PART2 1

#define TEST1_EXPECT 0x1227775554l
#define TEST2_EXPECT 0x4174379265l

void _start() {
#if RUN_TEST1
    print("PART 1 TEST: ");
    if (bcdint v = do_part1(countof(test), test); v != TEST1_EXPECT) {
        print("FAILED (got ");
        printh(v);
        print(", expected " xstr(TEST1_EXPECT) ")\n");
    } else {
        print("PASSED\n");
    }
#endif

#if RUN_PART1
    print("PART 1 RESULT: ");
    printh(do_part1(countof(input), input));
    print("\n");
#endif

#if RUN_TEST2
    print("PART 2 TEST: ");
    if (bcdint v = do_part2(countof(test), test); v != TEST2_EXPECT) {
        print("FAILED (got ");
        printh(v);
        print(", expected " xstr(TEST2_EXPECT) ")\n");
    } else {
        print("PASSED\n");
    }
#endif

#if RUN_PART2
    print("PART 2 RESULT: ");
    printh(do_part2(countof(input), input));
    print("\n");
#endif

    syscall(SYS_exit_group, 0);
}