Why filter() modified the list?

Question

In this code, I'm using the filter() method to collect the next edges available.

According to the post in stackoverflow, filter returns a new iterable.
https://stackoverflow.com/questions/44401103/does-filter-work-in-place-in-JUMP_LINK__&&__python__&&__JUMP_LINK

I guess I can work around by using deepcopy inside the filter function, but why the filter modified the list "edges" as it should not be?

https://sololearn.com/compiler-playground/cyYXla1sXKnE/?ref=app

Answer 1

I can find your filter only in the
get_next_node(last) function. and you are using it on edges, but I don't see it modifying the edges. you can print (edges) before and after the filter is applied and the edges is not affected in this function.

your try except blocks is strange, though. you have some unused variables and the logic is hard to follow. Also, it's throwing exception (list index out of range)... I suspect you have strange things going on in your loops, or you're overwriting something...

Answer 2

Bob_Li

Apparently my brain's auto-correction is working...

I have a theory about this behavior.
Filter() returns an iterable, which contains a copy of the element.

In my case, however, the iterable which the filter() works on is a list of lists.
When filter() constructing the returning iterable, it copies the nested list.
Since a list is a reference to the memory location, not the actual value, when I remove an element from the returned value, it actually removing the original nested list element from the original list.

Answer 3

Bob_Li
It is a WIP code for advent of code, day 16, part 1, year 2024, therefore it contains unused variables such as "end" and "finished", as I planned to use them later.
https://adventofcode.com/2024/day/16

I'm planning to use a BFS like method to solve the problem, more action / separate function will be added along the way.

My intention is to keep all the possible routes from "start" to "end" (just in case I might need it in part 2), then calculate the score later.

Now I print the edges inside the while loop, but before exception. And the result is mind-blowing. All 39 edges are the same? It is a total mystery how the variable edges changed.

https://sololearn.com/compiler-playground/c1dp5CN9MR9U/?ref=app

Answer 4

Wong Hei Ming
you have a typo in line 137. in
https://sololearn.com/compiler-playground/c1dp5CN9MR9U/?ref=app

for edeg in edges:

maybe you mean

for edge in edges:

Answer 5

Wong Hei Ming
sounds reasonable. nested lists are tricky to work with, so filter might have been actually modifying the edges even if it's supposed to be a new iterable object.

Another thing that's bothering me is the amount of deep copies you're making. it's going to be very inefficient. maybe there is a better method.

Answer 6

Bob_Li

I read about adjacency list, I just don't have a clear idea how to create them from a 2D map.
If I can come up with a structure like this, it would avoid any deepcopy at all.
edges = {(node1 position): [(North pos), (East pos), (South pos), (West pos)],
(node2 position): [(North pos), (East pos), (South pos), (West pos)],
etc...
}

So far I borrowed the idea from day 23, getting all "single" edge between the nodes.
https://adventofcode.com/2024/day/23
It is easier to get a single edge by scanning right and downward.
If it scans the left and upward......with try & except block......refactor find_edges() to scan all 4 directions......

Oh, I don't the filter() actually modifying the list at all now. The list is modified because the return value is a memory reference, and I did modify the return value...