1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114 | with Ada.Containers.Ordered_Sets;
with Ada.Strings.Fixed;
with Ada.Text_IO;
procedure Day15_1 is
subtype X_Value is Integer range -2_000_000 .. 5_000_000;
subtype Y_Value is Integer range 0 .. 5_000_000;
type Point_Value is record
X : X_Value;
Y : Y_Value;
end record;
function "<" (Left : in Point_Value; Right : in Point_Value) return Boolean is
(if Left.X = Right.X then Left.Y < Right.Y else Left.X < Right.X);
package Point_Sets is new Ada.Containers.Ordered_Sets (Element_Type => Point_Value);
type Sensor_Info is record
Point : Point_Value;
Dist : Natural;
end record;
function "<" (Left : in Sensor_Info; Right : in Sensor_Info) return Boolean is
(if Left.Point = Right.Point then Left.Dist < Right.Dist else Left.Point < Right.Point);
package Sensor_Sets is new Ada.Containers.Ordered_Sets (Element_Type => Sensor_Info);
function Distance (From : in Point_Value; To : in Point_Value) return Natural is
(abs (From.X - To.X) + abs (From.Y - To.Y) );
-- Returns the Manhattan distance between From and To
procedure Check_One (Position : in Sensor_Sets.Cursor);
-- Determines points in Row that cannot have a beacon based on the sensor referenced by Position & adds them to Known_Not
Row : constant := 2_000_000;
Known : Point_Sets.Set;
Known_Not : Point_Sets.Set;
procedure Check_One (Position : in Sensor_Sets.Cursor) is
Sensor : constant Sensor_Info := Sensor_Sets.Element (Position);
Point : Point_Value := (X => 0, Y => Row);
begin -- Check_One
if Distance ( (X => Sensor.Point.X, Y => Row), Sensor.Point) > Sensor.Dist then -- Sensor's exclusion zone can't include Row
return;
end if;
-- Avoid iterating over all of X_Value
Check_Left : for X in reverse X_Value'First .. Sensor.Point.X loop
Point.X := X;
exit Check_Left when Distance (Point, Sensor.Point) > Sensor.Dist;
if not Known.Contains (Item => Point) then -- This is not the location of a known beacon
Known_Not.Include (New_Item => Point); -- This is a location known not to be a beac0n
end if;
end loop Check_Left;
Check_Right : for X in Sensor.Point.X + 1 .. X_Value'Last loop
Point.X := X;
exit Check_Right when Distance (Point, Sensor.Point) > Sensor.Dist;
if not Known.Contains (Item => Point) then -- This is not the location of a known beacon
Known_Not.Include (New_Item => Point); -- This is a location known not to be a beac0n
end if;
end loop Check_Right;
end Check_One;
Input : Ada.Text_IO.File_Type;
Sensors : Sensor_Sets.Set;
begin -- Day15_1
Ada.Text_IO.Open (File => Input, Mode => Ada.Text_IO.In_File, Name => "input_15");
All_PairS : loop
exit All_Pairs when Ada.Text_IO.End_Of_File (Input);
One_Pair : declare
Line : constant String := Ada.Text_IO.Get_Line (Input);
Start : Positive := Ada.Strings.Fixed.Index (Line, "=") + 1;
Stop : Positive := Ada.Strings.Fixed.Index (Line (Start .. Line'Last), ",") - 1;
Sensor : Point_Value;
Beacon : Point_Value;
Dist : Natural;
begin -- One_Pair
Sensor.X := Integer'Value (Line (Start .. Stop) );
Start := Ada.Strings.Fixed.Index (Line (Stop + 1 .. Line'Last), "=") + 1;
Stop := Ada.Strings.Fixed.Index (Line (Start .. Line'Last), ":") - 1;
Sensor.Y := Integer'Value (Line (Start .. Stop) );
Start := Ada.Strings.Fixed.Index (Line (Stop + 1 .. Line'Last), "=") + 1;
Stop := Ada.Strings.Fixed.Index (Line (Start .. Line'Last), ",") - 1;
Beacon.X := Integer'Value (Line (Start .. Stop) );
Start := Ada.Strings.Fixed.Index (Line (Stop + 1 .. Line'Last), "=") + 1;
Beacon.Y := Integer'Value (Line (Start .. Line'Last) );
Dist := Distance (Sensor, Beacon);
Sensors.Include (New_Item => (Point => Sensor, Dist => Dist) );
if Sensor.Y = Row then -- Sensor is a point in Row that we know is not a beacon
Known_Not.Include (New_Item => Sensor);
end if;
if Beacon.Y = Row then -- Beacon is a point in Row that we know is a beacon
Known.Include (New_Item => Beacon);
end if;
end One_Pair;
end loop All_Pairs;
Ada.Text_IO.Close (File => Input);
Sensors.Iterate (Process => Check_One'Access);
Ada.Text_IO.Put_Line (Item => Known_Not.Length'Image);
end Day15_1;
|