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 :sleeping_bed:

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

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:

with Ada.Text_IO;
with Ada.Integer_Text_IO;
with Ada.Long_Long_Integer_Text_IO;
with Ada.Strings.Fixed;
with Ada.Containers.Doubly_Linked_Lists;

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;
Ada.Text_IO.Get_Line (Line, Last);
pragma Assert (Last < Line’Last);
Colon := Ada.Strings.Fixed.Index (Line, “:”);
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);
end Read_Pair;

package Pair_Lists is new Ada.Containers.Doubly_Linked_Lists (Pair);

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));
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;
while not Ada.Text_IO.End_Of_File loop
Item : Pair;
Read_Pair (Item);
Pairs.Append (Item);
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))
Ada.Integer_Text_IO.Put (Pos.X);
Ada.Integer_Text_IO.Put (Pos.Y);
(Long_Long_Integer (Pos.Y) +
Long_Long_Integer (Pos.X) * 4000000);
end if;
end if;
end loop;
end loop;
end Day_15;


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


I got the same error

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

1 Like

That was it; thanks.