137 lines
4.1 KiB
C
137 lines
4.1 KiB
C
#include "guf_common.h"
|
|
#include "guf_alloc_libc.h"
|
|
#include "guf_str.h"
|
|
#include "guf_math.h"
|
|
|
|
#include "libguf_impls/dict_impl.h"
|
|
|
|
/*
|
|
- Part 1: 54234399924 (Example: 1227775554)
|
|
|
|
- Part 2: 70187097315 (Example: 4174379265)
|
|
*/
|
|
|
|
guf_allocator g_allocator;
|
|
guf_libc_alloc_ctx g_allocator_ctx;
|
|
|
|
typedef struct id_range {
|
|
uint64_t start, end;
|
|
} id_range;
|
|
|
|
bool read_id_range(guf_str_view *str, id_range *result)
|
|
{
|
|
guf_str_view start_str = guf_str_view_pop_split(str, GUF_CSTR_LIT_TO_VIEW("-"));
|
|
guf_str_view end_str = guf_str_view_pop_split(str, GUF_CSTR_LIT_TO_VIEW(","));
|
|
|
|
start_str = guf_str_view_trim_left_ascii(start_str);
|
|
end_str = guf_str_view_trim_left_ascii(end_str);
|
|
|
|
if (start_str.len <= 0 || end_str.len <= 0) {
|
|
return false;
|
|
}
|
|
|
|
uint64_t start = guf_str_view_read_u64(&start_str);
|
|
uint64_t end = guf_str_view_read_u64(&end_str);
|
|
|
|
result->start = start;
|
|
result->end = end;
|
|
|
|
return true;
|
|
}
|
|
|
|
uint64_t pow_10(int exp)
|
|
{
|
|
GUF_ASSERT(exp >= 0);
|
|
uint64_t res = 1;
|
|
while (exp--) {
|
|
res *= 10u;
|
|
}
|
|
return res;
|
|
}
|
|
|
|
uint64_t solution(guf_str_view input, bool part_two)
|
|
{
|
|
uint64_t invalid_id_sum = 0;
|
|
|
|
id_range range;
|
|
guf_str start_str, end_str;
|
|
guf_str_init_empty(&start_str, &g_allocator);
|
|
guf_str_init_empty(&end_str, &g_allocator);
|
|
|
|
dict_u64_bool seen_invalid_ids;
|
|
dict_u64_bool_init(&seen_invalid_ids, &g_allocator);
|
|
|
|
|
|
while (read_id_range(&input, &range)) {
|
|
guf_str_append_u64(&start_str, range.start);
|
|
guf_str_append_u64(&end_str, range.end);
|
|
const int n_digits_start = (int)guf_str_len(&start_str);
|
|
const int n_digits_end = (int)guf_str_len(&end_str);
|
|
|
|
// Generate all pairs of one, two, three, ... digits (without leading zeroes)
|
|
for (int half_n_digits = 1; half_n_digits <= 20; ++half_n_digits) {
|
|
if (half_n_digits * 2 > n_digits_end) {
|
|
break;
|
|
}
|
|
|
|
uint64_t min_half = pow_10(half_n_digits - 1);
|
|
const uint64_t max_half = pow_10(half_n_digits) - 1;
|
|
|
|
for (uint64_t cur_half = min_half; cur_half <= max_half; ++cur_half) {
|
|
if (!part_two) { // Part 1:
|
|
uint64_t id = cur_half * pow_10(half_n_digits) + cur_half;
|
|
if (id > range.end) {
|
|
break;
|
|
} else if (id >= range.start) {
|
|
invalid_id_sum += id;
|
|
}
|
|
} else { // Part 2:
|
|
uint64_t id = cur_half;
|
|
for (int reps = 0; reps < 20; ++reps) {
|
|
id = id * pow_10(half_n_digits) + cur_half;
|
|
if (id > range.end) {
|
|
break;
|
|
} else if (id >= range.start) {
|
|
if (!dict_u64_bool_contains_val_arg(&seen_invalid_ids, id)) {
|
|
invalid_id_sum += id;
|
|
dict_u64_bool_insert_val_arg(&seen_invalid_ids, id, true, GUF_CPY_VALUE, GUF_CPY_VALUE);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
guf_str_substr(&start_str, 0, 0);
|
|
guf_str_substr(&end_str, 0, 0);
|
|
}
|
|
|
|
dict_u64_bool_free(&seen_invalid_ids, NULL);
|
|
|
|
return invalid_id_sum;
|
|
}
|
|
|
|
int main(int argc, const char **argv)
|
|
{
|
|
g_allocator_ctx.zero_init = false;
|
|
guf_alloc_tracker_init(&g_allocator_ctx.tracker, 1, "Day-2 heap allocator", NULL, stderr);
|
|
guf_libc_allocator_init(&g_allocator, &g_allocator_ctx);
|
|
|
|
if (argc < 2) {
|
|
printf("No input file given.\n");
|
|
return EXIT_FAILURE;
|
|
}
|
|
|
|
guf_str input_str = GUF_STR_UNINITIALISED;
|
|
guf_str_init_empty(&input_str, &g_allocator);
|
|
guf_str_append_file(&input_str, argv[1]);
|
|
|
|
const uint64_t p1_result = solution(guf_str_view_from_str(&input_str), false);
|
|
printf("Part 1: %" PRIu64 "\n", p1_result);
|
|
|
|
const uint64_t p2_result = solution(guf_str_view_from_str(&input_str), true);
|
|
printf("Part 2: %" PRIu64 "\n", p2_result);
|
|
|
|
guf_str_free(&input_str, NULL);
|
|
|
|
return EXIT_SUCCESS;
|
|
} |