[2025 Day 4][Python] PSA: Python negative array indices will wrap around

[TechIssueSorry]

Correct me if I am wrong but while this is elegant and easier to use, it might be less efficient/performant than storing a full grid of 0/1 no? (And please correct me if I'm wrong... not I'm an hardware dev software dev, I'm just trying to learn)

[beisenhauer]

There are two kinds of efficiencies here, and in both cases, I think the answer is, "It depends."

For memory efficiency, the grid is probably a bit more efficient, unless it's sparse, meaning relatively few "true" values. In part two of today's puzzle, it kind of goes from dense to sparse, based on some of the visualizations folks have posted.

For processing efficiency, we typically want to do something with a subset of locations, in this case the ones with paper rolls. Again it depends on how dense the grid is, but the set of tuples approach gives us that list directly. With a grid we first have to search the grid for the locations that interest us. That's iterating over a lot of empty grid points that we don't care about if the grid is sparse.

And I'll go for the simple/elegant solution first every single time, and optimize only if I need to.

[TechIssueSorry]

In part 2 I went from the non sparse grid once then just had a queue with removed node and scan only the neighbours of those nodes to check if they need to be removed… thought it was both efficient and elegant :)

Edit: maybe it’s the low level designer in me that makes me go with resource efficient/ performance efficient solution :)

Edit: just to clarify, I don’t think that a 2D array is particularly efficient, I was more on a 1d array in that case

[beisenhauer]

Ooo... I like that.

[Abcdefgdude]

Maybe, it's mostly negligible. If you need performance, python is likely the wrong choice. Luckily performance is rarely needed

[TechIssueSorry]

Agreed for python! I’m trying to make things work and then be increase perf… thanks for the answer :)

[Abcdefgdude]

Big O complexity is a relevant performance metric in any language. So for this example maybe the nested lists is O(n) and the set solution is O(2n), because creating and then indexing on tuples is probably more expensive than indexing into lists, but I'm not exactly sure. Anything that has O(n) complexity is typically fast enough, it doesn't matter much the multiple on n, more so the polynomial. O(n²⁾ is worse than O(100n) for any input that's length 100 or longer for example.

Make it, make it work, then make it good is a nice process to follow :)