readme.md

Advent Of Code 2022, Day 15.

Puzzle description

The full description of the puzzle can be found here: https://adventofcode.com/2022/day/15.

Skipping the details, the goal is to find an empty spot in the area covered by rhombuses, or rotated 45 degrees squares.

You are given pairs of centers (Sensors) and points on a side (Beacon), which fully describe such rhombus or square. Let's call it the sensor area.

               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...............

Part 1

In this part, the goal is to find the number of points covered by sensor areas on just one line.

I create a structure similar to the one found in the sweep and prune algorithm. It is a vector of points, where each point is a Start or an End of the occupied area. These points are sorted by coordinate. Then we can iterate over this vector and find points at which occupied areas start or end.

One more thing to take into account is to not include beacons and sensors in the count.

Part 2

At first, to solve this part I just iterated over each line and for each line iterated over this sweep-and-prune structure to find the gap. This algorithm found the solution, but it took 10 or 20 seconds on my machine, which is just too much.

So, I came up with another idea: the point we are looking for should be adjacent to one of the sensor areas. So I just iterate over adjacent points of every sensor area and check if this point lies outside of the other sensor areas. That works much faster.

Part 2 improvement

I believe it can be solved even more effectively because iterating over all adjacent points sounds like brute force.

We still can use the fact that the desired point is adjacent to at least two sensor areas. So we can view every sensor area as 4 adjacent lines, find overlaps of these lines and then check every found point.

Every such line can be described as y = y0 + sign * x, where the sign can be 1 or -1, and a range x0..x1.

• Lines can potentially have overlapping pixels only if their x-ranges overlap.
• In case signs are the same they overlap if their y0's are the same.
• In case signs are different, they can potentially intersect at x = (a.y0 - b.y0) / (b.sign - a.sign) if x is inside of the x-range overlap. The overlapping pixel will be there if this value is an integer.

This is not implemented (yet?).