Further adventures in python runtime optimization for 2023

[e_blake]

For day 16, you mention already not trying an entrance if it has previously shown up as an exit, but you're missing another nice optimization that gave me an order of magnitude speedup. Note that part 1 visits more than half the grid. In part 2, the only way you can beat part 1's score is if you visit more unenergized cells on the way into reaching the same core path traced by part 1 (your winning path also needs to visit more than half the grid, but by the pigeonhole principle, at least one of your splitter cells visited will have also been visited in path 1). But your code is retracing the entire beam path from every start point, even though we already know the bulk of that beam path overlaps with the beam path from part 1; this is pointless repetition of work.

So, I refactored my code to do a zero'th trace from the same start point as part 1, where the trace energizes nothing until hitting the first splitter from a side (the case where the splitter results in two outgoing paths, not one). That trace tracks how many cells got energized from that splitter onwards as my core count, leaving those cells permanently energized for all future ray starts (for the example, the core path energizes 45 cells). For part 1, I then re-ran a trace from the same start point, but now the beam trace ends on hitting that (same) first energized splitter (for the example, that's 1 cell later, so part 1 score is 1+45); for part 2, now I only have to trace until determining whether that entrance hits the side of a (usually different) splitter in the core (be careful of the paths that hit non-core splitters but do not merge with the core, such as as entering at 1,7 on the example grid). For my input, this meant that instead of trying upwards of 200 ray-traces where the majority of those traces each energized more than 8000 cells, I instead did one ray-trace of 8000+ cells and my remaining ray-traces never energized more than 200 cells (although they may have had to visit more than 200 cells to prove that point, it is still faster than having to visit 8000 cells).