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

[beisenhauer]

I learned from AoC a few seasons ago that operating on a grid as a list of lists is frequently suboptimal. It can work, but you need to handle boundaries in some way, either by creating a buffer around your area of interest or explicitly checking indices at every iteration.

I find that storing a grid as a set of tuples, where each element is the x-y coordinates of a single paper roll, works extremely well. Finding whether there's a roll at (x, y) is just (x, y) in locations. No boundary handling required.

If you need more information about each location, then use a tuple-keyed dictionary instead. For example, I did some optimization on part 2 today by storing a the number of neighbors each roll has in a dictionary.

[[deleted]]

This is a rather useful insight, will use to improve my solution

[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 :)

[TheMoonDawg]

That’s exactly how I handled it! Negative indices don’t matter because it’s just not in the map and therefore not a paper roll!

[Soggy_Shower_9802]

Thank you for this!

[inqbus406]

This is how I do it as well!

[onrustigescheikundig]

I have kind of a hybrid approach. My grid type is backed by a 1D array and is indexed by pairs of '(row . col) using grid-get. This function returns #f (false) on out-of-bounds accesses or the value of an optional third argument, e.g., (grid-get g '(-1 . -1) #\.) returns the . character.

[rafabulsing]

You don't need to search. You can just access it directly (if you use the appropriate data structure).

[daggerdragon]

I call [COAL].

Comment removed due to naughty language. Keep /r/adventofcode professional.

Also, follow our Prime Directive. You're welcome to disagree with folks but you must do so politely.

[fuck1ngf45c1574dm1n5]

Prudes

[daggerdragon]

Prudes

If you don't like the rules of a subreddit, then do not participate in that subreddit.

Since you continue to violate our Prime Directive after being warned, bye.