I'm sure I thought of more items for this page when lying in bed the other night, but this is what I can come up with at the moment...

Caching / Memoisation

I don't recall having used this in previous years, but I may be wrong. It did make a big difference to at least one puzzle this year.

The use cases I can think of (though there may well be more):

• Storing a reasonably expensive state to generate, that will likely be required again. The second time it can just be looked up rather than calculated.
• Storing the output from a deterministic function or method and keying it on the parameters passed in. See this method.

  No memoisation: 
  
    2022 24.1: 401ms   Blizzard basin
    2022 24.2: 831ms
               -------
               1232ms
  
  Memoisation:
  
    2022 24.1: 241ms   Blizzard basin
    2022 24.2: 495ms
               -------
               736ms
  

UPDATE: I have since optimised the solution for that puzzle, that the memoisation is no longer helpful, but at the point in time linked above, it made a difference.

Data Types

This is C# specific, though the collections can have similar/wildly different names across languages.

• If you don't care about order, use a HashSet<T> rather than a List<T>, T[] or whatever. Should be much faster.
• Quite specific to some puzzles, but if the "arena" is small enough and the use case supports it, store the values as bits. Convoluted example, but if a cell has 2 states and the arena is 1 x 64, that can be accommodated in a ulong rather than byte[64] or char[64]. Less state data to copy if required. Also, bit manipulation techniques can be used for comparisons/moves, which will be super fast. I've definitely used this to good effect in at least a few puzzles. E.g. for storing opened valves in day 22.

Compiler Hints

Again, C# specific though other languages might have equivalents. Sometimes (and I mean, not very often in my experience), the compiler hints for methods [MethodImpl(MethodImplOptions.AggressiveOptimization)] and/or [MethodImpl(MethodImplOptions.AggressiveInlining)] can speed things up. I'm guessing the fact that it only rarely helps is why the compiler doesn't do it all the time for everything.

Over the next few posts, I'll dive into some optimisations I discovered specific to particular puzzles. They will be in the order that they pop into my head...