I didn’t think too hard about optimization here, just implemented the problem as written. I’m not really happy with my solution, but it works so I guess that’s good enough.
Might do some cleanup/optimization later.
Looking at other people’s solutions on reddit I can see that it’s just a custom sort operator. I implemented a bubble sort from scratch without really thinking about what I was doing.
Super interesting. I didn’t catch that and instead went full graph theory and implemented topological sort. It also looks like some people ran into issues with topo sort. I did too at first (you can’t find root nodes for a sort if you consider the whole graph), but I solved them by only considering the subgraph containing the page numbers in each list.
1 Like
I tried the sorting first, then ran into a problem, read your comment, tried it again, and got it to work. Basically this:
procedure Sort_Page_Number_List is new Ada.Containers.Generic_Sort
(Index_Type => Natural, Before => Page_Number_In_Order,
Swap => Page_Number_Swap);
It’s neat, but the bad thing is: you can’t infer from the problem that this should work. I was almost going to make a transitive closure of the ordering, which I now understand would lead to more trouble.
1 Like
My approach:
As I read in the page orderings, I build a Hashed_Map of Hashed sets with the left number as the key to the map, and the set containing all right numbers that had it as a left number.
EX:
[47] => [13, 29, 53, 61],
[97] => [13, 29, 47, 53, 61, 75]
etc.
Then when I read in the update orders after, I iterated starting with the 2nd number and verified it either wasn’t a key to the map (no association) or the all of the numbers to the left of it were not in its hashed set if it did exist as a key.
EX:
-- Here the upper loop number is supplied to Left and the numbers to the
-- left of it are supplied to Right and we verify if there is a specified order
-- that matches
function Must_Be_Before(Left, Right : Page_Number; Map : Page_Map) return Boolean is
Map_Cursor : constant Page_Maps.Cursor := Map.Find(Left);
Set_Cursor : constant Page_Sets.Cursor :=
(if Map_Cursor in Page_Maps.No_Element then
Page_Sets.No_Element
else
Map(Map_Cursor).Find(Right));
begin
return Set_Cursor not in Page_Sets.No_Element;
end Must_Be_Before;
So for a list of 5 numbers:
1 check vs the 2nd number
2 checks vs the 3rd number
3 checks vs the 4th number
4 checks vs the 5th number
etc.
So not dissimilar to some sorting algorithms, but checking as I go without actually sorting the page numbers.
1 Like
Jeez, I keep falling behind! Lots of (much needed) practice using maps and vectors for this one.