From 0d06788586cda1b1ba01524f4ba3cad147052203 Mon Sep 17 00:00:00 2001 From: Thomas Schmucker Date: Fri, 29 Dec 2023 12:16:59 +0100 Subject: Lösungen für Tag 24, Teil 1 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- makefile | 3 +- src/day24.cpp | 131 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/day24.py | 33 +++++++++++++++ 3 files changed, 166 insertions(+), 1 deletion(-) create mode 100644 src/day24.cpp create mode 100644 src/day24.py diff --git a/makefile b/makefile index e14c204..07e42b8 100644 --- a/makefile +++ b/makefile @@ -22,7 +22,8 @@ all: bin/day01 \ bin/day20 \ bin/day21 \ bin/day22 \ - bin/day23 + bin/day23 \ + bin/day24 bin: mkdir $@ diff --git a/src/day24.cpp b/src/day24.cpp new file mode 100644 index 0000000..296d38a --- /dev/null +++ b/src/day24.cpp @@ -0,0 +1,131 @@ +#include +#include +#include +#include +#include +#include +#include +using namespace std; + +using line_type = tuple; +using point_type = tuple; +using puzzle_type = vector; + +template +int +sgn(T val) +{ + return (T(0) < val) - (val < T(0)); +} + +puzzle_type +read_file(string_view filename) +{ + fstream input{ filename }; + puzzle_type result; + + for ( string line; getline(input, line); ) { + const auto NFIELDS = 6; + + double x, y, z, dx, dy, dz; // NOLINT + + if ( sscanf(line.data(), "%lf, %lf, %lf @ %lf, %lf, %lf", &x, &y, &z, &dx, &dy, &dz) != NFIELDS ) { + continue; + } + + result.emplace_back(make_tuple(x, y, z, dx, dy, dz)); + } + + return result; +} + +point_type +get_direction(line_type line) +{ + const auto [x, y, z, dx, dy, dz] = line; + + return make_tuple(sgn(dx), sgn(dy)); +} + +point_type +get_direction(line_type from, point_type to) +{ + const auto [x, y, z, dx, dy, dz] = from; + const auto [to_x, to_y] = to; + + return make_tuple(sgn(to_x - x), sgn(to_y - y)); +} + +bool +lint(line_type stone_a, line_type stone_b, point_type& cross_point) +{ + const auto p_1 = make_tuple(get<0>(stone_a), get<1>(stone_a)); + const auto p_2 = make_tuple(get<0>(stone_a) + get<3>(stone_a), get<1>(stone_a) + get<4>(stone_a)); + + const auto p_3 = make_tuple(get<0>(stone_b), get<1>(stone_b)); + const auto p_4 = make_tuple(get<0>(stone_b) + get<3>(stone_b), get<1>(stone_b) + get<4>(stone_b)); + + const auto a_1 = get<1>(p_2) - get<1>(p_1); + const auto b_1 = get<0>(p_1) - get<0>(p_2); + const auto c_1 = a_1 * (get<0>(p_1)) + b_1 * (get<1>(p_1)); + + const auto a_2 = get<1>(p_4) - get<1>(p_3); + const auto b_2 = get<0>(p_3) - get<0>(p_4); + const auto c_2 = a_2 * (get<0>(p_3)) + b_2 * (get<1>(p_3)); + + const auto determinant = a_1 * b_2 - a_2 * b_1; + + if ( determinant == 0 ) { + return false; + } + + auto p_x = (b_2 * c_1 - b_1 * c_2) / determinant; + auto p_y = (a_1 * c_2 - a_2 * c_1) / determinant; + + cross_point = make_tuple(p_x, p_y); + + return true; +} + +void +part1(const puzzle_type& input) +{ + const auto in_range = [](point_type point) -> bool { + static const auto lower_limit = 200000000000000.0; + static const auto upper_limit = 400000000000000.0; + + const auto [x, y] = point; + + return x > lower_limit && x < upper_limit && y > lower_limit && y < upper_limit; + }; + + const auto in_future = [](line_type stone, point_type point) -> bool { + const auto sgn_stone = get_direction(stone); + const auto sgn_point = get_direction(stone, point); + + return sgn_stone == sgn_point; + }; + + long sum = 0; + for ( size_t idx = 0; idx != input.size(); ++idx ) { + const auto& stone_a = input[idx]; + + for ( size_t idx2 = idx + 1; idx2 < input.size(); ++idx2 ) { + const auto& stone_b = input[idx2]; + + point_type cross_point; + if ( lint(stone_a, stone_b, cross_point) && in_range(cross_point) && in_future(stone_a, cross_point) && in_future(stone_b, cross_point) ) { + ++sum; + } + } + } + cout << sum << endl; +} + +int +main() +{ + const auto input = read_file("data/day24.txt"); + + part1(input); +} diff --git a/src/day24.py b/src/day24.py new file mode 100644 index 0000000..809f2d0 --- /dev/null +++ b/src/day24.py @@ -0,0 +1,33 @@ +class Hailstone: + def __init__(self, sx, sy, sz, vx, vy, vz): + self.sx = sx + self.sy = sy + self.sz = sz + self.vx = vx + self.vy = vy + self.vz = vz + + self.a = vy + self.b = -vx + self.c = vy * sx - vx * sy + + def __repr__(self): + return "Hailstone{" + f"a={self.a}, b={self.b}, c={self.c}" + "}" + +hailstones = [Hailstone(*map(int, line.replace("@", ",").split(","))) for line in open("data/day24.txt")] + +total = 0 + +for i, hs1 in enumerate(hailstones): + for hs2 in hailstones[:i]: + a1, b1, c1 = hs1.a, hs1.b, hs1.c + a2, b2, c2 = hs2.a, hs2.b, hs2.c + if a1 * b2 == b1 * a2: + continue + x = (c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1) + y = (c2 * a1 - c1 * a2) / (a1 * b2 - a2 * b1) + if 200000000000000 <= x <= 400000000000000 and 200000000000000 <= y <= 400000000000000: + if all((x - hs.sx) * hs.vx >= 0 and (y - hs.sy) * hs.vy >= 0 for hs in (hs1, hs2)): + total += 1 + +print(total) -- cgit v1.3