AoC 2020 - Day 11: Seating System

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…