CODEWITHSUNDEEP
pythonalgorithmlist
Guolf3377
Guolf3377

Reputation: 107

How to check if list's elements are contiguous

I have to check if ■ are contiguous:

_|_ _|_1_|_2_|_3_|_
_|_1_|_■_|_■_|_ _|_
_|_2_|_ _|_ _|_■_|_
_|_3_|_ _|_■_|_ _|_
_|_4_|_■_|_■_|_ _|_

in this case return True

and for example if something like this happens:

_|_ _|_1_|_2_|_3_|_
_|_1_|_■_|_■_|_ _|_
_|_2_|_ _|_ _|_■_|_
_|_3_|_ _|_ _|_ _|_
_|_4_|_■_|_■_|_ _|_

in this case return False

I'm using lists like:

my_list=[[" "," "," "],[" "," "," "],[" "," "," "],
[" "," "," "]]

The numbers appear only when printing the board, so I work anything else with my_list.

Upvotes: 2

Views: 1669

Answers (3)

AChampion
AChampion

Reputation: 30268

Walk the graph, and if you visit every node then you are connected (contiguous), e.g.:

def is_contiguous(grid):
    items = {(x, y) for x, row in enumerate(grid) for y, f in enumerate(row) if f}
    directions = [(0, 1), (1, 0), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
    neighbours = {(x, y): [(x+dx, y+dy) for dx, dy in directions if (x+dx, y+dy) in items]
                  for x, y in items}

    closed = set()
    fringe = [next(iter(items))]
    while fringe:
        i = fringe.pop()
        if i in closed:
            continue
        closed.add(i)
        for n in neighbours[i]:
            fringe.append(n)

    return items == closed

>>> is_contiguous([["X", "X", ""], ["", "", "X"], ["", "X", ""], ["X", "X", ""]])
True
>>> is_contiguous([["X", "X", ""], ["", "", "X"], ["", "", ""], ["X", "X", ""]])
False

As long as a blank tile is falsy then this should work as is, e.g. [[1, 1, 0], [0, 0, 1], [0, 1, 0], [1, 1, 0]] would also return True. If you have a different definition of a blank tile then just change if f on the items definition.

Upvotes: 5

TabsNotSpaces
TabsNotSpaces

Reputation: 1357

This worked for me:

def findContiguous(myList):
    rowCount = 0
    previousRowFound = []
    rowsWithItems = []     
    for row in myList:
        currentRowFound = []
        rowCount += 1
        # Determine if target is in the row
        if "■" in row:
            currentRowFound = [i for i, x in enumerate(row) if x == "■"]
            rowsWithItems.append(rowCount)

        # Check if there is a cell adjacent or diagonal to previous
        if len(currentRowFound) != 0 and len(previousRowFound) != 0:
            for cell in currentRowFound:
                if not((cell + 1 in previousRowFound) or (cell - 1 in previousRowFound) or (cell in previousRowFound)):
                    return False

        # Check for blank rows in between rows with item
        if len(rowsWithItems) > 1 and len(previousRowFound) == 0:
            if rowsWithItems[-2] != rowCount - 1:
                print(rowsWithItems)
                print(rowCount)
                return False

        # Move on to next row
        previousRowFound = currentRowFound
        first = False
    return True

Upvotes: 0

Salvador Dali
Salvador Dali

Reputation: 222761

I will not give you the code that you can just insert (because it looks to me like a programming challenge), but I will give you the idea how to solve your problem.

You need to construct a graph. So for every black dot, you have the list of adjacent black dots (you define here what is adjacent). For example if all diagonals count as such, then for point (2, 3) your adjacent list will be: (1, 2), (3, 2). And your graph will look like

{
  (2, 3): {(1, 2), (3, 2)},
  ... every other node
}

You can come up with a simpler schema, where (2, 3) will correspond to (2 - 1) * len(matrix row) + (3 - 1) = 5. I am subtracting one because I use zero as a starting point.

Now when you have a graph, you use the algorithm for a connected components and check whether there is only one such component. If it is, you get True, otherwise false.

Your single connected component is just a BFS or DFS.

Upvotes: 2

Related Questions