Today, I am pretty sure I have ended up with a sub-optimal solution.
It takes few seconds to complete – an acceptable amount of seconds, but still
it is not instant.
Furthermore, it took much more time to solve than usual, and this is another hint that I have chosen the wrong data structure.
For part 2, I wanted to treat the map as a graph, and simply connect nodes skipping the floors. I decided to take the effort to refactor part 1 as well, because it was still useful as a test case for all the parsing (I do a lot of small mistakes there), but again, the slowness of the test was annoying.
Overall, it came out almost at the first try; still, I cannot stop thinking that I could have used a better approach.
Update after Day 13
Today, I took the chance to work a bit on the performance.
The new approach is much faster, but still slow. I am afraid this is the best I can do with pure python. Tha algorithm more or less stayed the same, with one important optimization (trace only changed seats); maybe there is another approach much more performant.
Moving from a “pure functional” approach, with immutable data, to changes in
place helped cutting times by half. This is a very data-intensive exercise, so
this was quite expected.
Then, tracing helped cutting another second and a half, plus a bunch of other small changes (including using
__slots__, which helped gaining about 200ms) to
arrive to a final execution time a bit lower than a couple of seconds.
Maybe using something like Nuitka might help, but it is already taking a bit too much time…