96 lines
2.9 KiB
C
96 lines
2.9 KiB
C
#include "aoc.h"
|
|
|
|
static u64
|
|
get_power_of_ten(u64 x) {
|
|
if (x < 10ull) return 10ull;
|
|
if (x < 100ull) return 100ull;
|
|
if (x < 1000ull) return 1000ull;
|
|
if (x < 10000ull) return 10000ull;
|
|
if (x < 100000ull) return 100000ull;
|
|
if (x < 1000000ull) return 1000000ull;
|
|
if (x < 10000000ull) return 10000000ull;
|
|
if (x < 100000000ull) return 100000000ull;
|
|
if (x < 1000000000ull) return 1000000000ull;
|
|
if (x < 10000000000ull) return 10000000000ull;
|
|
if (x < 100000000000ull) return 100000000000ull;
|
|
if (x < 1000000000000ull) return 1000000000000ull;
|
|
if (x < 10000000000000ull) return 10000000000000ull;
|
|
if (x < 100000000000000ull) return 100000000000000ull;
|
|
if (x < 1000000000000000ull) return 1000000000000000ull;
|
|
if (x < 10000000000000000ull) return 10000000000000000ull;
|
|
if (x < 100000000000000000ull) return 100000000000000000ull;
|
|
if (x < 1000000000000000000ull) return 1000000000000000000ull;
|
|
return 10000000000000000000ull;
|
|
}
|
|
|
|
static i64
|
|
concat(i64 a, i64 b) {
|
|
i64 result = a * get_power_of_ten(b) + b;
|
|
return result;
|
|
}
|
|
|
|
static bool
|
|
solve(i64 test, i64 *numbers, isize len, u64 acc) {
|
|
if (len == 0) {
|
|
return acc == test;
|
|
}
|
|
else if (acc > test) {
|
|
return false;
|
|
}
|
|
else {
|
|
if (solve(test, numbers + 1, len - 1, acc + numbers[0])) return true;
|
|
if (solve(test, numbers + 1, len - 1, acc * numbers[0])) return true;
|
|
return false;
|
|
}
|
|
}
|
|
|
|
|
|
static bool
|
|
solve_concat(i64 test, i64 *numbers, isize len, u64 acc) {
|
|
if (len == 0) {
|
|
return acc == test;
|
|
}
|
|
else if (acc > test) {
|
|
return false;
|
|
}
|
|
else {
|
|
if (solve_concat(test, numbers + 1, len - 1, acc + numbers[0])) return true;
|
|
if (solve_concat(test, numbers + 1, len - 1, acc * numbers[0])) return true;
|
|
if (solve_concat(test, numbers + 1, len - 1, concat(acc, numbers[0]))) return true;
|
|
return false;
|
|
}
|
|
}
|
|
|
|
int main(int argc, char **argv) {
|
|
Arena *arena = make_arena(Megabytes(4));
|
|
|
|
Tokens lines = read_lines(arena, argv[1]);
|
|
struct {
|
|
i64 *data;
|
|
isize len, cap;
|
|
} values = {0};
|
|
|
|
i64 part_1 = 0, part_2 = 0;
|
|
for (isize i = 0; i < lines.len; i++) {
|
|
str line = lines.tokens[i];
|
|
values.len = 0;
|
|
|
|
str lhs, rhs;
|
|
str_split(line, STR(":"), &lhs, &rhs);
|
|
i64 test_value = parse_i64(lhs, *arena);
|
|
|
|
str current;
|
|
rhs = str_trim(rhs);
|
|
while ((current = str_next_token(&rhs, STR(" "))).len > 0) {
|
|
*push(&values, arena) = parse_i64(current, *arena);
|
|
}
|
|
bool solvable_1 = solve(test_value, values.data, values.len, 0);
|
|
part_1 += solvable_1 ? test_value : 0;
|
|
bool solvable_2 = solve_concat(test_value, values.data, values.len, 0);
|
|
part_2 += solvable_2 ? test_value : 0;
|
|
}
|
|
printf("%ld\n", part_1);
|
|
printf("%ld\n", part_2);
|
|
|
|
}
|