(The downside is that the problems have suddenly stepped up in difficulty!)
For the second day in a row, writing a program that solves the example wasn’t enough. Twice I ran it and got solutions that were rejected as too large. I had to comb through some of the pairs that my program claimed were legitimate. In both cases, it was the case where I had to compare a number and a list. The instructions are to create a new list that includes the number, then compare the lists, but it seemed equivalent to me simply to compare the number with the first element of the list. This produced false positives. I haven’t quite figured out why, though.
Curiously, in part 2 I was able to make it work simply by inserting the packets 2 and 6 instead of [[2]] and [[6]]. I don’t know if this is a bug, but I don’t think so, since as in the case above the comparison will simply convert the guards to lists as needed. Since I was using Vectors, it was straightforward to implement a sorter, then find the guards.
Same here, my solution for part 1 didn’t work with the real data. After I fixed it, it worked. Part 2 directly worked for the test data, but the ordering wasn’t correct for the real data. Had to debug a lot.
At first, I used Multiway_Trees, but then I realized it was much simpler. You can simply use flat arrays, when you replace empty lists with -1. Then you can use comparison and sorting provided by Ada itself.
My list parser is much more bloated than necessary but it’s not too dramatic in terms of run time: 0.035 seconds in LEA / with HAC; 0.0022 seconds with GNAT, compiled in fast mode.
One trap in the puzzle lays in the wording of the part 2: “Now, you just need to put all of the packets in the right order.” It suggests you need to store the data lines and sort them. Actually it is only needed in the story, where the character will so something with the distress signal.
When parsing the data, you can recycle the same comparison function you wrote for part 1 and compare the input line and the string “[[2]]”. By counting the occurrences of “correct” you know where “[[2]]” should be in a sorted set of lines. Same for [[6]].
This portion is relatively slim in my code:
Open (f, "aoc_2022_13.txt");
Read_Data :
loop
for i in 1 .. 2 loop
Get_Line (f, s (i));
before_2 := before_2 + One_if_lesser (s (i), +"[[2]]");
before_6 := before_6 + One_if_lesser (s (i), +"[[6]]");
end loop;
pair_index := pair_index + 1;
if Compare_List (s (1), s (2)) = correct then
sum_correct_pair_indices := sum_correct_pair_indices + pair_index;
end if;
exit when End_Of_File (f);
Skip_Line (f);
end loop Read_Data;
Close (f);
r (1) := sum_correct_pair_indices;
r (2) := (before_2 + 1) * (before_6 + 2);
The function One_if_lesser is defined as:
function One_if_lesser (s1, s2 : VString) return Natural is
begin
if Compare_List (s1, s2) = correct then
return 1;
else
return 0;
end if;
end One_if_lesser;
I made a Cursor struct for navigating the list while leaving it as a string. I have functions to check whether it is at the end, or if the next item is a number or a list and then to extract the number or list (as a Cursor).
Mostly I did that because I thought it would make it easier to prove with SPARK. But, I sure had to have a lot of pre & post conditions, and some loop invariants.
It made me wonder if there is, or will be, a way to assign invariants to a struct so my functions that manipulate it don’t have to repeat the invariants on the struct.
I was able to assign an invariant to my struct. Basically, I split out the cursor into a separate package and I was able to define a ghost function that verified the cursor integrity, and assign the type invariant when defining the struct in the private part of the package. I still had to define some pre & post conditions and a couple of loop invariants within the package body, but then in the main program I didn’t need any. Also, the validation function made the pre, post, loop_invariant conditions much cleaner. https://github.com/wutka/advent-of-code-2022-spark/tree/main/day13
Also, for part 2…
Instead of having to sort the lists, I just count how many lines are less than [[2]] and how many are less than [[6]] remembering to add 1 to that second number to account for [[2]].
