aboutsummaryrefslogtreecommitdiff
path: root/src/day24.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/day24.cpp')
-rw-r--r--src/day24.cpp173
1 files changed, 0 insertions, 173 deletions
diff --git a/src/day24.cpp b/src/day24.cpp
deleted file mode 100644
index 76f459b..0000000
--- a/src/day24.cpp
+++ /dev/null
@@ -1,173 +0,0 @@
1#include <cstdlib>
2#include <fstream>
3#include <iostream>
4#include <limits>
5#include <map>
6#include <string>
7#include <tuple>
8#include <vector>
9#include <z3++.h>
10
11using namespace std;
12
13using line_type = tuple<double, double, double, double, double, double>;
14using point_type = tuple<double, double>;
15using puzzle_type = vector<line_type>;
16
17template<typename T>
18int
19sgn(T val)
20{
21 return (T(0) < val) - (val < T(0));
22}
23
24puzzle_type
25read_file(string_view filename)
26{
27 fstream input{ filename };
28 puzzle_type result;
29
30 for ( string line; getline(input, line); ) {
31 const auto NFIELDS = 6;
32
33 double x, y, z, dx, dy, dz; // NOLINT
34
35 if ( sscanf(line.data(), "%lf, %lf, %lf @ %lf, %lf, %lf", &x, &y, &z, &dx, &dy, &dz) != NFIELDS ) {
36 continue;
37 }
38
39 result.emplace_back(make_tuple(x, y, z, dx, dy, dz));
40 }
41
42 return result;
43}
44
45point_type
46get_direction(line_type line)
47{
48 const auto [x, y, z, dx, dy, dz] = line;
49
50 return make_tuple(sgn(dx), sgn(dy));
51}
52
53point_type
54get_direction(line_type from, point_type to)
55{
56 const auto [x, y, z, dx, dy, dz] = from;
57 const auto [to_x, to_y] = to;
58
59 return make_tuple(sgn(to_x - x), sgn(to_y - y));
60}
61
62bool
63lint(line_type stone_a, line_type stone_b, point_type& cross_point)
64{
65 const auto p_1 = make_tuple(get<0>(stone_a), get<1>(stone_a));
66 const auto p_2 = make_tuple(get<0>(stone_a) + get<3>(stone_a), get<1>(stone_a) + get<4>(stone_a));
67
68 const auto p_3 = make_tuple(get<0>(stone_b), get<1>(stone_b));
69 const auto p_4 = make_tuple(get<0>(stone_b) + get<3>(stone_b), get<1>(stone_b) + get<4>(stone_b));
70
71 const auto a_1 = get<1>(p_2) - get<1>(p_1);
72 const auto b_1 = get<0>(p_1) - get<0>(p_2);
73 const auto c_1 = a_1 * (get<0>(p_1)) + b_1 * (get<1>(p_1));
74
75 const auto a_2 = get<1>(p_4) - get<1>(p_3);
76 const auto b_2 = get<0>(p_3) - get<0>(p_4);
77 const auto c_2 = a_2 * (get<0>(p_3)) + b_2 * (get<1>(p_3));
78
79 const auto determinant = a_1 * b_2 - a_2 * b_1;
80
81 if ( determinant == 0 ) {
82 return false;
83 }
84
85 auto p_x = (b_2 * c_1 - b_1 * c_2) / determinant;
86 auto p_y = (a_1 * c_2 - a_2 * c_1) / determinant;
87
88 cross_point = make_tuple(p_x, p_y);
89
90 return true;
91}
92
93void
94part1(const puzzle_type& input)
95{
96 const auto in_range = [](point_type point) -> bool {
97 static const auto lower_limit = 200000000000000.0;
98 static const auto upper_limit = 400000000000000.0;
99
100 const auto [x, y] = point;
101
102 return x > lower_limit && x < upper_limit && y > lower_limit && y < upper_limit;
103 };
104
105 const auto in_future = [](line_type stone, point_type point) -> bool {
106 const auto sgn_stone = get_direction(stone);
107 const auto sgn_point = get_direction(stone, point);
108
109 return sgn_stone == sgn_point;
110 };
111
112 long sum = 0;
113 for ( size_t idx = 0; idx != input.size(); ++idx ) {
114 const auto& stone_a = input[idx];
115
116 for ( size_t idx2 = idx + 1; idx2 < input.size(); ++idx2 ) {
117 const auto& stone_b = input[idx2];
118
119 point_type cross_point;
120 if ( lint(stone_a, stone_b, cross_point) && in_range(cross_point) && in_future(stone_a, cross_point) && in_future(stone_b, cross_point) ) {
121 ++sum;
122 }
123 }
124 }
125 cout << sum << endl;
126}
127
128void
129part2(const puzzle_type& input)
130{
131 auto config = z3::config();
132 auto context = z3::context(config);
133 auto solver = z3::solver(context);
134
135 const auto px = context.int_const("px");
136 const auto py = context.int_const("py");
137 const auto pz = context.int_const("pz");
138 const auto vx = context.int_const("vx");
139 const auto vy = context.int_const("vy");
140 const auto vz = context.int_const("vz");
141
142 for ( size_t i = 0; i != input.size(); ++i ) {
143 const auto& stone = input[i];
144
145 const auto pxn = context.int_val(int64_t(get<0>(stone)));
146 const auto pyn = context.int_val(int64_t(get<1>(stone)));
147 const auto pzn = context.int_val(int64_t(get<2>(stone)));
148 const auto vxn = context.int_val(int64_t(get<3>(stone)));
149 const auto vyn = context.int_val(int64_t(get<4>(stone)));
150 const auto vzn = context.int_val(int64_t(get<5>(stone)));
151 const auto tn = context.int_const(to_string(i+1).c_str());
152
153 solver.add(tn >= 0);
154 solver.add(pxn + vxn * tn == px + vx * tn);
155 solver.add(pyn + vyn * tn == py + vy * tn);
156 solver.add(pzn + vzn * tn == pz + vz * tn);
157 }
158
159 solver.check();
160
161 auto model = solver.get_model();
162
163 cout << model.eval(px).as_int64() + model.eval(py).as_int64() + model.eval(pz).as_int64() << endl;
164}
165
166int
167main()
168{
169 const auto input = read_file("data/day24.txt");
170
171 part1(input);
172 part2(input);
173}