This one should’ve been straightforward, but I tried to use Ada.Containers.Ordered_Sets which somehow allowed multiple elements with the same value to exist. This kept confusing me until I switched to inefficiently using Vector guarded by checking Contains before adding an element. This got me to the right answer, then I replaced it with Hashed_Sets, which works as expected.
I’m sure I’m doing something wrong with the comparison operator on Ordered_Sets, but I have no idea what.
type Coordinate is record
Y, X : Integer;
end record;
function "<" (Left, Right : Coordinate) return Boolean
is (Left.Y < Right.Y or else Left.X < Right.X);
package Coordinate_Sets is new Ada.Containers.Ordered_Sets (Coordinate);
In general when you’re ordering over multiple fields, you should only compare the subsequent fields if the earlier fields are equal. Something like:
if Left.Y < Right.Y then return True; end if;
if Left.Y > Right.Y then return False; end if;
return Left.X < Right.X;
Your current comparison doesn’t handle the case where Left.Y > Right.Y and uses the ordering of their X fields instead. This has bit me more times than I’d like to admit.
In case someone wants to search further: it’s called lexicographical ordering, as in a (e.g.) English Dictionary. There are some variations on it. E.g., when comparing variable length sequences, it’s cheaper to first check for differences in length, and only then compare all the elements. In an (English) dictionary, that would lead to sorting “a”, “b”, … “z”, “aa”, “ab”, …, “zz”, “aaa”, …
Since an antinode could overlap with an an antenna, I duplicated the input map and updated both with antinodes but the original map I didn’t overwrite the antenna node on an overlap. It wasn’t as efficient, but made the logic for counting unique locations easier.
Data structure wise I made a Hashed map of Coordinate lists keyed by frequency ID. That way when I parsed the input map of antennas, I could either insert a new frequency ID list or append to an existing list easily.
Once that data structure was filled, I looped over the hashed map and then looped over the list for each frequency. Then for each coordinate in the list, I would calculate the delta between it and each successive coordinate and try to insert antinodes based on that delta
Something like:
for Frequency of Frequencies loop
for Current in 1 .. Frequency.Last_Index loop
for Index in Current+1 .. Frequency.Last_Index loop
Add_Antinode
(c1 => Frequency(Current), -- First coordinate
c2 => Frequency(Index), -- Second coordinate
Map => Map,
Antinode_Map => Antinode_Map,
Count => Count);
end loop;
end loop;
end loop;
with the declarations:
type Map_Point is new Character
with Static_Predicate => Map_Point in '#' | '.' | 'a'..'z' | 'A'..'Z' | '0'..'9';
subtype Frequency_ID is Map_Point
with Static_Predicate => Frequency_ID in 'a'..'z' | 'A'..'Z' | '0'..'9';
type X_Index is new Positive;
type Y_Index is new Positive;
type Coordinate is record
X : X_Index;
Y : Y_Index;
end record;
package Coordinate_Vectors is new Ada.Containers.Vectors(Positive, Coordinate);
subtype Coordinate_List is Coordinate_Vectors.Vector;
use type Coordinate_List;
function Hash(Frequency : Frequency_ID) return Ada.Containers.Hash_Type is
(Ada.Containers.Hash_Type'Mod(Frequency_ID'Pos(Frequency)));
package Frequency_Maps is new Ada.Containers.Hashed_Maps
(Key_Type => Frequency_ID,
Element_Type => Coordinate_List,
Hash => Hash,
Equivalent_Keys => "=");
subtype Frequency_Records is Frequency_Maps.Map;
Frequencies : Frequency_Records;
@JeremyGrosser As others pointed out, your ordering was set up wrong. I do the lexicographic ordering this way (taken straight from my solution – we had the same idea!):
function "<" (Left, Right : Location_Record) return Boolean
is (Left.Row < Right.Row
or else (Left.Row = Right.Row and then Left.Col < Right.Col));
Basically, for the _i_th field, you’d need a third test: are fields 1, 2, …, _i_th - 1 equal, and is Left smaller than Right for the _i_th field.
This gets really annoying when there are more than 3 fields. I wish Ada had a several default orderings built-in, or at least an easier way to auto-generate them, such as a way to iterate through the fields of a record, but I can see how that latter approach could be very unsafe.
There are other orderings, too. Lexicographic ordering has unfortunate computational properties for certain problem domains. You can visualize this easily in the x-y plane: pick a point (even (1,1) will do) and try sketching all the points that are lexicographically smaller than that point. It should become very clear very quickly why this isn’t always a great ordering. If it isn’t, repeat the exercise with a graded ordering, where you first compare the sum of the coordinates (e.g., (3,5) < (2,7) because 3+5 < 2+7) and break ties recursively after dropping the highest dimension (e.g., (3,5) < (4,4) because 3+5 = 4+4 and 3 < 4). The undesirable computational property goes away.
(Sorry if the details are unwanted, I used to study this.)
The puzzle master disappointed me on part 2. At least for my input, none of the nodes appear at locations where an intermediate antinode would appear between them. For example: if you have nodes at (1,4) and (7,1), you would also get antinodes at (5,2) and (3,3). But he took the time to generate locations so that each pair’s Δx and Δy have no common factor.
I know I have no right to complain, as he kept the problem relatively easy (it’s still day 8) and I arrived at the correct answer. But I wasted time being a tad too clever and I just know he’ll pull something like this later in the month when I least expect it. Happens every year.