# 2022 Day 15: Beacon Exclusion Zone

Only 10 days left!

My solution to Part 1 was quite slow, perhaps because I used an `OrderedSet`. It might be worth retrying with a `HashedSet` at some point.

So I was really worried that Part 2 would be one of those problems whose obvious solution is to apply Part 1, but whoses complexity explodes on you, and as I first began to read it, my heart filled with dread. But then I realized that unlike Part 1, you donâ€™t have to keep track of which positions can be reached by a sensor. You can just race through the rectangle, checking if any sensor reaches your given position. It still takes a few moments, but it worked! So I will be interested in seeing if anyone manages to solve it in a fraction of a second, and if so, then how.

Iâ€™m also amazed that Part 2 can even be a problem; the fact that he pulled off such a puzzle impresses me. Maybe it wonâ€™t impress me if I think about it enough, but even after a couple of glances, Iâ€™m still impressed. Maybe I just need some

Having solution for Part 1 for `Y=2_000_000` I made Part 2 by trivial modifications, mainly running `for Y in 0 .. 4_000_000 loop Do_Part_1 (Y); end loop;`. And this worked for the example but not for my `input` file. This made me create another solution (that doesnâ€™t work for Part 1, however). It produced a correct answer. With the answer I was able to debug the first solution and found a bug (in a slice intersection test function). Now I have 2 solutions for Part 2 .

My second solution takes 0.3s to find the first result, but if I remove `return;` to check all possible results it takes about 8 seconds:

``````\$ time ./bin/day_15 < /tmp/input
3316868    2686239      13267474686239

real	0m0,348s
user	0m0,335s
sys	0m0,013s
``````

The idea is to walk along the contour of each sensor checking that each position of the contour isnâ€™t covered by any sensor. Here is the source code:

procedure Day_15 is
type Position is record
X, Y : Integer;
end record;

function Distance (A, B : Position) return Natural is
(abs (A.X - B.X) + abs (A.Y - B.Y));

type Pair is record
Sensor : Position;
Beacon : Position;
end record;

procedure Read_Pair (V : out Pair) is
Line : String (1 â€¦ 80);
Last : Natural;
Pos : Natural;
Colon : Natural;
begin
pragma Assert (Last < Lineâ€™Last);
Ada.Integer_Text_IO.Get (Line (13 â€¦ Last), V.Sensor.X, Pos);
Ada.Integer_Text_IO.Get (Line (Pos + 5 â€¦ Colon - 1), V.Sensor.Y, Pos);
Ada.Integer_Text_IO.Get (Line (Colon + 25 â€¦ Last), V.Beacon.X, Pos);
Ada.Integer_Text_IO.Get (Line (Pos + 5 â€¦ Last), V.Beacon.Y, Pos);

Pairs : Pair_Lists.List;

subtype Target is Natural range 0 â€¦ 4000000;

type Position_Array is array (Positive range <>) of Position;

function Contour (S : Pair) return Position_Array is
Dist : constant Positive := Distance (S.Sensor, S.Beacon);
Result : Position_Array (1 â€¦ 4 * (Dist + 1));
begin
for J in 0 â€¦ Dist loop
Result (4 * J + 1) := (S.Sensor.X + J, S.Sensor.Y - Dist - 1 + J);
Result (4 * J + 2) := (S.Sensor.X + Dist + 1 - J, S.Sensor.Y + J);
Result (4 * J + 3) := (S.Sensor.X - J, S.Sensor.Y + Dist + 1 - J);
Result (4 * J + 4) := (S.Sensor.X - Dist - 1 + J, S.Sensor.Y - J);
end loop;

``````  return Result;
``````

end Contour;
begin
declare
Item : Pair;
begin
Pairs.Append (Item);
end;
end loop;

for S of Pairs loop
for Pos of Contour (S) loop
if Pos.X in Target and then Pos.Y in Target then
if (for all X of Pairs =>
Distance (X.Sensor, Pos) > Distance (X.Sensor, X.Beacon))
then
(Long_Long_Integer (Pos.Y) +
Long_Long_Integer (Pos.X) * 4000000);
return;
end if;
end if;
end loop;
end loop;
end Day_15;

2 Likes

Ran into a few issues that required redoing my solution.

First, I tried using a 2d array - fine for test data, but the real data blows stack and heap.

Then, I stored all Sensors with Position and Range in a Vector. This helped a lot. Maybe Set would be better - but it works.

Optimizing for Part 2 took a while, though.

One thing I dislike is that `for X of Y` is less performant than using a cursor and also, the Code completion in Gnat Studio doesnâ€™t work for `X`.

I love this solution. Wish Iâ€™d thought of it. Is the 8 seconds for Part 2 alone?

I tried running it: `./maxs_sol < input.txt`, but got back:

``````raised STORAGE_ERROR : stack overflow or erroneous memory access
``````

Do you know what the issue might be? I have to run to work, or Iâ€™d look into it more before asking. Iâ€™m running Linux, if it matters.

I had to do one thing that I donâ€™t think I have ever done before in AoC - I edited the input file to remove the : so I could use Ada.Integer_Text_IO to read the number right before it.

For part 1, I kept a list of segments representing ranges on row 2_000_000 and would merge them together as they overlapped, so in the end there were just 2 ranges, one on either side of the beacon that was on row 2_000_000.

For part 2, I looped around the diamond shape formed by each sensor, and for each point just outside the diamond, I checked to see if it intersected any other diamonds. It takes about 5 seconds to run the whole program, almost all of that is in part 2. If I build for release instead of dev it runs in 1.5s. I think one difference between my solution and Maxâ€™s is that I am trying to compute the result without allocating additional space. I have an array for the segments, that is fixed at 50, and is just dependent on the number of sensors, and another array of 50 that is also dependent on the number of sensors. Perhaps I am also using up some time with the checks and conversions to make gnatprove happy. Maybe there are things I could do to eliminate those.

2 Likes

I got the same error

probably default stack size, try to run `ulimit -s unlimited` before launching.

1 Like

That was it; thanks.