Skip to content

Instantly share code, notes, and snippets.

@ksmigrod
Created December 11, 2024 11:29
Show Gist options
  • Save ksmigrod/1c693bf1eea53999ff229799404cfbf9 to your computer and use it in GitHub Desktop.
Save ksmigrod/1c693bf1eea53999ff229799404cfbf9 to your computer and use it in GitHub Desktop.
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct node_t {
uint64_t number;
uint64_t count;
} node_t;
int node_cmp(const void *a, const void *b) {
node_t *n1 = (node_t *)a;
node_t *n2 = (node_t *)b;
if (n1->number < n2->number) return -1;
if (n1->number > n2->number) return 1;
return 0;
}
const uint64_t HIGHEST_SAFE = 9'114'003'988'986'932ULL;
uint64_t is_even_digits(uint64_t number) {
if (10ULL <= number && number < 100ULL) {
return 10ULL;
}
if (1'000ULL <= number && number < 10'000ULL) {
return 100ULL;
}
if (100'000ULL <= number && number < 1'000'000ULL) {
return 1'000UL;
}
if (10'000'000ULL <= number && number < 100'000'000ULL) {
return 10'000ULL;
}
if (1'000'000'000ULL <= number && number < 10'000'000'000ULL) {
return 100'000ULL;
}
if (100'000'000'000ULL <= number && number < 1'000'000'000'000ULL) {
return 1'000'000ULL;
}
if (10'000'000'000'000ULL <= number && number < 100'000'000'000'000ULL) {
return 10'000'000ULL;
}
if (1'000'000'000'000'000ULL <= number && number < 10'000'000'000'000'000ULL) {
return 100'000'000ULL;
}
if (100'000'000'000'000'000ULL <= number && number < 1'000'000'000'000'000'000ULL) {
return 1'000'000'000ULL;
}
if (10'000'000'000'000'000'000ULL <= number) {
return 10'000'000'000ULL;
}
return 0;
}
size_t next_length(node_t *numbers, size_t length) {
size_t count = 0;
for (size_t i = 0; i < length; i++) {
count += is_even_digits(numbers[i].number) ? 2 : 1;
}
return count;
}
size_t blink(node_t *dest, node_t *src, size_t length) {
size_t idx = 0;
for (size_t i = 0; i < length; i++) {
if (src[i].number == 0) {
dest[idx++] = (node_t){1, src[i].count};
} else {
uint64_t divider = is_even_digits(src[i].number);
if (divider == 0 && src[i].number > HIGHEST_SAFE) {
fputs("Overflow", stderr);
} else if (divider == 0) {
dest[idx++] = (node_t){src[i].number * 2024ULL, src[i].count};
} else {
dest[idx++] = (node_t){src[i].number / divider, src[i].count};
dest[idx++] = (node_t){src[i].number % divider, src[i].count};
}
}
}
qsort(dest, idx, sizeof(node_t), node_cmp);
size_t uq_count = 0;
for (size_t i = 1; i < idx; i++) {
if (dest[uq_count].number == dest[i].number) {
dest[uq_count].count += dest[i].count;
} else {
dest[++uq_count] = dest[i];
}
}
return uq_count + 1;
}
int main(void) {
node_t *numbers = calloc(20, sizeof(node_t));
size_t old_length = 0;
uint64_t number;
while (scanf("%lu", &number) != EOF) {
numbers[old_length] = (node_t){number, 1};
old_length++;
}
size_t new_length = 0;
for (size_t i = 0; i < 75; i++) {
new_length = next_length(numbers, old_length);
node_t *next_numbers = (uint64_t *)calloc(new_length, sizeof(node_t));
new_length = blink(next_numbers, numbers, old_length);
free(numbers);
printf("%lu: %lu\n", i, new_length);
numbers = next_numbers;
old_length = new_length;
}
uint64_t result;
for (size_t i = 0; i < old_length; i++) {
result += numbers[i].count;
}
printf("%lu\n", result);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment