-
-
Save ksmigrod/1c693bf1eea53999ff229799404cfbf9 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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