Now, this one has been the bane of my life from an optimisation standpoint.

It's not a difficult one to comprehend or implement, but everything I did seemed slow in comparison to other puzzle run-times.

I tried a self-implemented circular linked list, a circular list based upon List<T>, then simply a List<T> which I thought got me as far is I could go.

I think I was at around the ~250ms execution time when I just couldn't see how to make it faster. This was annoying, because it isn't actually doing much... just many repetitions.

The Optimisation

Unfortunately, this one doesn't really have a clever optimisation from spotting something in the puzzle that didn't need to be done or finding patterns.

Instead, I went down to the metal and looked at List<T> to see what it was doing.

List<T> is basically backed by an array. However, because it is generic, it has to perform many checks on how to determine equivalence, boundary checks, etc...

As I knew the size of my array and the type stored, there was no need for these to consume precious processor cycles.

So, long story short, I ditched the List<T> for an array.

Here's the meat of the change.

- private readonly List<Number> _numbers = new();
+ private Number[] _numbers;

...

- var oldIndex = _numbers.IndexOf(number);
+ var oldIndex = 0;
+
+ for (var i = 0; i < _length; i++)
+ {
+     if (_numbers[i] == number)
+     {
+         oldIndex = i;
+
+         break;
+     }
+ }

...

- _numbers.RemoveAt(oldIndex);
-
- _numbers.Insert(newIndex, number);
+ if (oldIndex < newIndex)
+ {
+     Array.Copy(_numbers, oldIndex + 1, _numbers, oldIndex, newIndex - oldIndex);
+ }
+ else
+ {
+     Array.Copy(_numbers, newIndex, _numbers, newIndex + 1, oldIndex - newIndex);
+ }
+
+ _numbers[newIndex] = number;

It's difficult to say exactly as the run-times do differ from execution to execution (I thought computers were deterministic...), but I think this shaved ~100ms off the run-time on average.

A win, but it's my last remaining puzzle that exceeds 100ms... can I let this go?