How to check if elements(coordinates) of a set form a continous shape?

Question

I am trying to write a function that gets a set of tuples as parameter, and checks if given characters form a continuous shape in an NxN grid. Tuples are the indexes of characters in the lists that form the grid. The shape is continuous if there is a character directly below, above or to the sides of another character.

continuous             not continous         not continous
  xxxxx                   xxxxx                 ooxxx   
  xxoox                   xxoox                 xxxxx
  xxxoo                   ooxxx                 xxoox 
  xxxoo                   oxxxx                 xxoox
  xxxxo                   xoxxx                 xxxxx

========================

    def connected(characters):
        result = True
        for i in characters:
            if (i[0]+1, i[1]) in characters or (i[0]-1, i[1]) in characters or (i[0], i[1]+1) in characters or (i[0], i[1]-1) in characters:
                result = True
                characters.discard(i)
            else:
                result = False
                return result
        return result

>>>connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1)})

would form this shape, thus it wouldn't be continuous but my code thinks it is.

xxxo
xoxo
xoxo
xxxx

This works for the most time, but doesn't work when given characters form two separate continuous shapes like the 2nd wrong example I gave above. I tried to solve this problem by removing each tuple after it was checked but I get

Traceback (most recent call last):
  File "C:/Users/User/PycharmProjects/untitled6/venv/1.py", line 47, in <module>
    connected({(1, 2), (1, 3), (2, 2), (0, 3), (0, 4)})
  File "C:/Users/User/PycharmProjects/untitled6/venv/1.py", line 15, in connected
    for i in grid:
RuntimeError: Set changed size during iteration

error. What can I do to solve this?

Don't change the size of the set during iteration then! Use a new set. — Marcin, Mar 10 '20 at 19:15
Please provide the entire error message, as well as a [mcve]. — AMC, Mar 10 '20 at 19:17
@arthionne Add that to your post, it's practically impossible to read as a comment. — AMC, Mar 10 '20 at 19:24

score 1 · Accepted Answer · answered Mar 11 '20 at 21:09

For more info on the error, see https://stackoverflow.com/a/38423075. Basically, you have to iterate over a copy of a set if you want to modifiy this set in the loop.

Apart from that, there is a flaw in your algorithm.

If you don't discard the current character, you check only if every character has a neighbor. This will be ok:

xxxxx
xoxox
xoxox
xxxxx

But if you discard the current character, you may have suprises:

 xxx            xxx
 xox <- cur     x x <- discarded
 xox            xox <- has no neighbor!
 xxx            xxx

The classic algorithm is based on a tree traversal: start from any not and traverse all the directly linked nodes. If all nodes where seen, the graph is connected.

I use a DFS here, but you can use a BFS if you want:

def connected(characters):
    seen = set()
    stack = [next(iter(characters))] if characters else []
    while stack:
        c = stack.pop()
        seen.add(c)
        for other_c in [(c[0]+1, c[1]), (c[0]-1, c[1]), (c[0], c[1]+1), (c[0], c[1]-1)]:
            if other_c not in seen and other_c in characters:
                stack.append(other_c)

    return not (characters - seen)

print(connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1)}))
# False
print(connected({(1, 3), (2, 1), (2, 3), (0, 3), (1, 1), (1, 2)}))
# True

How to check if elements(coordinates) of a set form a continous shape?

1 Answers1