2022 day15 part1

7 files changed, 255 insertions, 5 deletions

diff --git a/.gitignore b/.gitignore
index 10481f1..b24d193 100644
--- a/.gitignore
+++ b/.gitignore
@@ -2,3 +2,4 @@ build/
 .idea/
 cmake-build-debug/
 .ccls-cache/
+.cache/
diff --git a/src/2022/day15/README.md b/src/2022/day15/README.md
index e69de29..8ec4eb8 100644
--- a/src/2022/day15/README.md
+++ b/src/2022/day15/README.md
@@ -0,0 +1,97 @@
+--- Day 15: Beacon Exclusion Zone ---
+You feel the ground rumble again as the distress signal leads you to a large network of subterranean tunnels. You don't have time to search them all, but you don't need to: your pack contains a set of deployable sensors that you imagine were originally built to locate lost Elves.
+
+The sensors aren't very powerful, but that's okay; your handheld device indicates that you're close enough to the source of the distress signal to use them. You pull the emergency sensor system out of your pack, hit the big button on top, and the sensors zoom off down the tunnels.
+
+Once a sensor finds a spot it thinks will give it a good reading, it attaches itself to a hard surface and begins monitoring for the nearest signal source beacon. Sensors and beacons always exist at integer coordinates. Each sensor knows its own position and can determine the position of a beacon precisely; however, sensors can only lock on to the one beacon closest to the sensor as measured by the Manhattan distance. (There is never a tie where two beacons are the same distance to a sensor.)
+
+It doesn't take long for the sensors to report back their positions and closest beacons (your puzzle input). For example:
+
+Sensor at x=2, y=18: closest beacon is at x=-2, y=15
+Sensor at x=9, y=16: closest beacon is at x=10, y=16
+Sensor at x=13, y=2: closest beacon is at x=15, y=3
+Sensor at x=12, y=14: closest beacon is at x=10, y=16
+Sensor at x=10, y=20: closest beacon is at x=10, y=16
+Sensor at x=14, y=17: closest beacon is at x=10, y=16
+Sensor at x=8, y=7: closest beacon is at x=2, y=10
+Sensor at x=2, y=0: closest beacon is at x=2, y=10
+Sensor at x=0, y=11: closest beacon is at x=2, y=10
+Sensor at x=20, y=14: closest beacon is at x=25, y=17
+Sensor at x=17, y=20: closest beacon is at x=21, y=22
+Sensor at x=16, y=7: closest beacon is at x=15, y=3
+Sensor at x=14, y=3: closest beacon is at x=15, y=3
+Sensor at x=20, y=1: closest beacon is at x=15, y=3
+So, consider the sensor at 2,18; the closest beacon to it is at -2,15. For the sensor at 9,16, the closest beacon to it is at 10,16.
+
+Drawing sensors as S and beacons as B, the above arrangement of sensors and beacons looks like this:
+
+               1    1    2    2
+     0    5    0    5    0    5
+ 0 ....S.......................
+ 1 ......................S.....
+ 2 ...............S............
+ 3 ................SB..........
+ 4 ............................
+ 5 ............................
+ 6 ............................
+ 7 ..........S.......S.........
+ 8 ............................
+ 9 ............................
+10 ....B.......................
+11 ..S.........................
+12 ............................
+13 ............................
+14 ..............S.......S.....
+15 B...........................
+16 ...........SB...............
+17 ................S..........B
+18 ....S.......................
+19 ............................
+20 ............S......S........
+21 ............................
+22 .......................B....
+This isn't necessarily a comprehensive map of all beacons in the area, though. Because each sensor only identifies its closest beacon, if a sensor detects a beacon, you know there are no other beacons that close or closer to that sensor. There could still be beacons that just happen to not be the closest beacon to any sensor. Consider the sensor at 8,7:
+
+               1    1    2    2
+     0    5    0    5    0    5
+-2 ..........#.................
+-1 .........###................
+ 0 ....S...#####...............
+ 1 .......#######........S.....
+ 2 ......#########S............
+ 3 .....###########SB..........
+ 4 ....#############...........
+ 5 ...###############..........
+ 6 ..#################.........
+ 7 .#########S#######S#........
+ 8 ..#################.........
+ 9 ...###############..........
+10 ....B############...........
+11 ..S..###########............
+12 ......#########.............
+13 .......#######..............
+14 ........#####.S.......S.....
+15 B........###................
+16 ..........#SB...............
+17 ................S..........B
+18 ....S.......................
+19 ............................
+20 ............S......S........
+21 ............................
+22 .......................B....
+This sensor's closest beacon is at 2,10, and so you know there are no beacons that close or closer (in any positions marked #).
+
+None of the detected beacons seem to be producing the distress signal, so you'll need to work out where the distress beacon is by working out where it isn't. For now, keep things simple by counting the positions where a beacon cannot possibly be along just a single row.
+
+So, suppose you have an arrangement of beacons and sensors like in the example above and, just in the row where y=10, you'd like to count the number of positions a beacon cannot possibly exist. The coverage from all sensors near that row looks like this:
+
+                 1    1    2    2
+       0    5    0    5    0    5
+ 9 ...#########################...
+10 ..####B######################..
+11 .###S#############.###########.
+In this example, in the row where y=10, there are 26 positions where a beacon cannot be present.
+
+Consult the report from the sensors you just deployed. In the row where y=2000000, how many positions cannot contain a beacon?
+
+
diff --git a/src/2022/day15/aoc.cpp b/src/2022/day15/aoc.cpp
index 6e2d7a7..09a923f 100644
--- a/src/2022/day15/aoc.cpp
+++ b/src/2022/day15/aoc.cpp
@@ -1,9 +1,46 @@
 #include "aoc.h"
+#include <set>
 
 namespace aoc2022 {
+int sensor::minx;
+int sensor::maxx;
 
-std::pair<int, int> day15(line_view) {
-  return {0, 0};
+
+int no_beacon(int y, std::vector<sensor>& ss) {
+  int count{0};
+  for (int x = sensor::minx; x <= sensor::maxx; x++) {
+    sensor::pos p;
+    p.x = x;
+    p.y = y;
+    size_t n{0};
+    for (auto&s : ss) {
+      if(s.inscope(p)) {
+        n++;
+      }
+    }
+    // printf("(%d, %d) has %zu\n", x, y, n);
+    count += (bool) n > 0;
+  }
+  return count;
+}
+
+bool valid(sensor::pos p, int dx) {
+  return p.x >= 0 && p.x <= dx && p.y >= 0 && p.y <= dx;
+}
+
+int only_beacon(int dx, std::vector<sensor>& ss) {
+  return 0;
+}
+
+std::pair<int, int> day15(line_view file) {
+  std::vector<sensor> ss;
+  per_line(file, [&ss](line_view lv){
+      ss.emplace_back(lv);
+      return true;
+  });
+  int n1 = no_beacon(2000000, ss);
+  int n2 = only_beacon(4000000, ss);
+  return {n1, n2};
 }
 }
 
diff --git a/src/2022/day15/aoc.h b/src/2022/day15/aoc.h
index eac13eb..ffb4183 100644
--- a/src/2022/day15/aoc.h
+++ b/src/2022/day15/aoc.h
@@ -3,6 +3,80 @@
 
 namespace aoc2022 {
 
+struct sensor {
+  struct pos {
+    int x = 0;
+    int y = 0;
+
+    pos() {}
+    pos(int i, int j): x(i), y(j) {}
+    bool operator==(pos px) const noexcept {
+      return x == px.x && y == px.y;
+    }
+
+    bool operator<(pos px) const noexcept {
+      return x < px.x ? true : x > px.x ? false : y < px.y;
+    }
+  };
+
+  struct triangle {
+    pos as[3];
+  };
+
+  static int minx;
+  static int maxx;
+
+  pos ps[2] = {{0,0},{0,0}};
+
+  static int mdistance(pos p1, pos p2) {
+    return std::abs(p1.x - p2.x) + std::abs(p1.y - p2.y);
+  }
+
+  void get_number(const char** pp, int* d) {
+    const char *p = *pp;
+    int sign = 1;
+    if (*p == '-') {
+      sign = -1;
+      p++;
+    }
+    while (*p >= '0' && *p <= '9') {
+      *d  = *d * 10 + *p - '0';
+      p++;
+    }
+    *d *= sign;
+    *pp = p;
+  }
+
+  void print() {
+    printf("S(%d, %d) B(%d, %d)\n", ps[0].x, ps[0].y, ps[1].x, ps[1].y);
+  }
+
+  bool inscope(pos p) {
+    auto d1 = mdistance(ps[0], ps[1]);
+    auto d2 = mdistance(ps[0], p);
+    return d2 <= d1 && !(p == ps[1]);
+  }
+
+  sensor(line_view lv) {
+    const char* p = lv.line;
+    int *is[] = {&ps[0].x, &ps[0].y, &ps[1].x, &ps[1].y};
+    int n{0};
+    while (p < lv.line + lv.length) {
+      if (*p == '=') {
+        const char* p0 = p+1;
+        get_number(&p0, is[n]);
+        p = p0;
+        n++;
+      }
+      p++;
+    }
+    auto x1 = ps[0].x - mdistance(ps[0], ps[1]);
+    auto x2 = ps[0].x + mdistance(ps[0], ps[1]);
+    if (minx > x1) minx = x1;
+    if (maxx < x2) maxx = x2;
+  }
+};
+
 std::pair<int, int> day15(line_view);
 }
 
diff --git a/src/2022/day15/input b/src/2022/day15/input
index e69de29..08fb0fb 100644
--- a/src/2022/day15/input
+++ b/src/2022/day15/input
@@ -0,0 +1,27 @@
+Sensor at x=2983166, y=2813277: closest beacon is at x=3152133, y=2932891
+Sensor at x=2507490, y=122751: closest beacon is at x=1515109, y=970092
+Sensor at x=3273116, y=2510538: closest beacon is at x=3152133, y=2932891
+Sensor at x=1429671, y=995389: closest beacon is at x=1515109, y=970092
+Sensor at x=2465994, y=2260162: closest beacon is at x=2734551, y=2960647
+Sensor at x=2926899, y=3191882: closest beacon is at x=2734551, y=2960647
+Sensor at x=1022491, y=1021177: closest beacon is at x=1515109, y=970092
+Sensor at x=1353273, y=1130973: closest beacon is at x=1515109, y=970092
+Sensor at x=1565476, y=2081049: closest beacon is at x=1597979, y=2000000
+Sensor at x=1841125, y=1893566: closest beacon is at x=1597979, y=2000000
+Sensor at x=99988, y=71317: closest beacon is at x=86583, y=-1649857
+Sensor at x=3080600, y=3984582: closest beacon is at x=3175561, y=4138060
+Sensor at x=3942770, y=3002123: closest beacon is at x=3724687, y=3294321
+Sensor at x=1572920, y=2031447: closest beacon is at x=1597979, y=2000000
+Sensor at x=218329, y=1882777: closest beacon is at x=1597979, y=2000000
+Sensor at x=1401723, y=1460526: closest beacon is at x=1515109, y=970092
+Sensor at x=2114094, y=985978: closest beacon is at x=1515109, y=970092
+Sensor at x=3358586, y=3171857: closest beacon is at x=3152133, y=2932891
+Sensor at x=1226284, y=3662922: closest beacon is at x=2514367, y=3218259
+Sensor at x=3486366, y=3717867: closest beacon is at x=3724687, y=3294321
+Sensor at x=1271873, y=831354: closest beacon is at x=1515109, y=970092
+Sensor at x=3568311, y=1566400: closest beacon is at x=3152133, y=2932891
+Sensor at x=3831960, y=3146611: closest beacon is at x=3724687, y=3294321
+Sensor at x=2505534, y=3196726: closest beacon is at x=2514367, y=3218259
+Sensor at x=2736967, y=3632098: closest beacon is at x=2514367, y=3218259
+Sensor at x=3963402, y=3944423: closest beacon is at x=3724687, y=3294321
+Sensor at x=1483115, y=2119639: closest beacon is at x=1597979, y=2000000
diff --git a/src/2022/day15/input0 b/src/2022/day15/input0
index e69de29..a612424 100644
--- a/src/2022/day15/input0
+++ b/src/2022/day15/input0
@@ -0,0 +1,14 @@
+Sensor at x=2, y=18: closest beacon is at x=-2, y=15
+Sensor at x=9, y=16: closest beacon is at x=10, y=16
+Sensor at x=13, y=2: closest beacon is at x=15, y=3
+Sensor at x=12, y=14: closest beacon is at x=10, y=16
+Sensor at x=10, y=20: closest beacon is at x=10, y=16
+Sensor at x=14, y=17: closest beacon is at x=10, y=16
+Sensor at x=8, y=7: closest beacon is at x=2, y=10
+Sensor at x=2, y=0: closest beacon is at x=2, y=10
+Sensor at x=0, y=11: closest beacon is at x=2, y=10
+Sensor at x=20, y=14: closest beacon is at x=25, y=17
+Sensor at x=17, y=20: closest beacon is at x=21, y=22
+Sensor at x=16, y=7: closest beacon is at x=15, y=3
+Sensor at x=14, y=3: closest beacon is at x=15, y=3
+Sensor at x=20, y=1: closest beacon is at x=15, y=3
diff --git a/test/test_2022.cpp b/test/test_2022.cpp
index 8d80b5f..f8fb354 100644
--- a/test/test_2022.cpp
+++ b/test/test_2022.cpp
@@ -117,9 +117,9 @@ TEST_CASE("Regolith Reservoir", "[2022]") {
   REQUIRE(27566 == p.second);
 }
 
-TEST_CASE("", "[2022]") {
-  line_view lv = load_file("../src/2022/day15/input0");
+TEST_CASE("Beacon Exclusion Zone", "[2022]") {
+  line_view lv = load_file("../src/2022/day15/input");
   auto p = aoc2022::day15(lv);
-  REQUIRE(0 == p.first);
+  REQUIRE(6078701 == p.first);
   REQUIRE(0 == p.second);
 }