I’m not sure if the problem is awkward or if I’m just dumb, but my solution felt like the wrong way to do it. Looking forward to reading how everyone else did it!
In part 1, I initially defined a type Dial is mod 100 but this just made things more complicated than it needed to be, trying to add a signed value. In part 2, I thought I could do something clever with (Dial + abs Distance) / 100 but never got it to work. Eventually just wrote a loop going through every step of the dial and checking the value. Feels wrong, but it works.
I had the exact same experience on part 2. I’m washed up.
Consider dial at 1 with L101. 1 - 101 = -100. This is 2 turns, so you can’t just divide by 100. I haven’t worked out the correct math yet, but I think you need to account for the fact that the dial starts at 1 and get the equation to a point where you have 200/100.
EDIT: I think the key edge case I’m missing is this:
0 - 100 = 0 mod 100, 1 turn
1 - 101 = 0 mod 100, 2 turns
EDIT2: I managed to solve it by comparing the output of the working brute force method to my mathy solution until I worked out all the edge cases. It did turn out to be the problem from my prior edit.
I did it with a mod 100 type, I just kept the number of clicks as a Natural (actually, for the second part, I split it into the number of full turns and number of clicks from 0 .. 99). It’s just that when it was a left turn, I subtracted the clicks.
For part 2, I just looked to see if turning right made the dial value lower than it was, indicating that it passed or hit 0, and if turning left made it higher. The edge case there was if you turned left exactly to 0, so I also check to see if the number of left clicks equals the dial: if Dist_Mod > 0 and then ((Dial > 0 and then Dial - Dist_Mod > Dial) or else Dial = Dist_Mod) and then Zero_Count_B < Natural'Last then Zero_Count_B := Zero_Count_B + 1; end if;
I didn’t even think about using type Dial is mod 100. Used type Dial is 0 .. 99 instead and implemented Increment and decrement procedures where I could do part 2 easier.
But had a really nasty mental error where I mixed up Dial’First with Dial’Last if Pointer = Dial’Last then -- should be first!!! Put (" (crossed Zero) "); Test_Two := Test_Two + 1; end if;
Eventually just wrote a loop going through every step of the dial and checking the value. Feels wrong, but it works.
That’s definitely the surest way to get it to work. Feels more pragmatic to me than wrong.
I also got stuck on my first attempt and then decided I need to be able to do it the math way. (Partly because I have another leaderboard with colleagues who are space engineers and I don’t want to look like the imperative brute-force problem solver right away…) But it took me a while to figure out the edge cases; it actually only worked once I realized there are two edge cases and it’s easiest to handle them separately.
I guess I am lucky to be HACking it this year; as far as I can tell, HAC doesn’t have a modular integer type, so when I made my mistakes I had to face the fact that it wasn’t because I was being too clever but because I was being too stupid.
(Tagging @zertovitch so he can correct me if I’m wrong about HAC.)
Do you mean “every” step of the dial as in, adding or subtracting 1, then checking, for every single turn? I didn’t find that necessary, though I’m not especially proud of what I did, either. I need to look more closely at the approaches using mod that some others have posted. Maybe watch @Max’s bonus, too.
My approach for Part 2 was to figure out how far it takes to get from the knob’s position to 0. Since
Cycles := Distance / 100;
Distance := Distance - Cycles * 100;
Result := Result + abs (Cycles);
if Distance < 0 then
while Distance /= 0 loop
-- HAC lacks Max attribute of integer?
if Position = 0 or else Distance > -Position then
Change := Distance;
else
Change := -Position;
end if;
Position := Position + Change;
Distance := Distance - Change;
if Position < 0 then
Position := Position + 100;
end if;
if Position = 0 then
Result := Result + 1;
end if;
end loop;
else
-- etc.
Yes, exactly. Admittedly not elegant, but it did make it easier to prove absence of overflow with SPARK.
A very unscientific microbenchmark showed that the iterative solution was faster as the CPU’s branch predictor did a good job with the loop and avoided the expensive divmod machinery.
Same situation on my side.
I made a dumb solution for part 2 (also smelling the possible traps of edge cases) in a few minutes, but later I was too ashamed of that dumb solution and made an alternative solution using division and handling the edge cases. The “smarter” solution took an hour or more to debug. The smarter solution runs 29x faster than the dumb one on my data.
Such situation is very illustrative of the forces behind Wirth’s law: the dumb solution runs in less than a second, even on slow environment: unoptimized machine code for a virtual machine (HAC’s). So, what is the immediate incentive to program better?
For AoC, the incentive is immediate (you have to train your brain and program efficient things for one the next days).
But in a school or a large corporation…
I found these fairly easy. In the first part, I used a modular type Dial_Number and added or subtracted Dial_Number'Mod of the input value. For the second part, it only took a few minutes to get the iterative solution running, and it ran in less than 0.03 seconds, so I saw no reason to improve it.
