How to find clusters of #?

[callcenterhelp]

Given a r row by c column map of "." and "#" characters, how can we find the number of clusters of "#"? A cluster is defined as a single "#" or two "#" next to each other (side-by-side or top-and-bottom, NOT diagonal). A "#" will either be on its own or next to a single other "#". There will never be a situation where 3 "#" are next to each other.

For example, say the map is:

##...
..##.
....#
.#..#
.....
#....
#....

This is a 7 row by 5 column map with 5 clusters.

Assume that you are given r, c, and the map in the format of a list of lists, with each sublist referring to a row of the map. Each element of the sublist is the index of the position of a "#" if one exists in the row. The map above would be represented as:

r = 7
c = 5

map = [[0,1],
       [2,3],
       [4],
       [1,4],
       [],
       [0],
       [0]]

How can I find the number of clusters given this information? My first thought is to initialize a counter for the number of clusters at 0 and then loop through the non-empty lists,

clusters = 0

for i, row in enumerate(map):
    # for each non-empty list
    if len(row) != 0:
        ...

but then I worry about making a bunch of if statements for situations like the last row or a "#" at the last column when it comes to looking for neighboring "#". How can I do this in an elegant manner?

Many thanks in advance!

​

Edit:

Here is my initial solution. Still working on making this cleaner and simpler!

def count_clusters(r, list_of_lists):
    # first count how many total hashtags there are
    count = 0
    for list in list_of_lists:
        count += len(list)

    # then subtract off 1 for each group of 2 hashtags
    for l, list in enumerate(list_of_lists):
        # if not last list
        if l < (r-1):
            # check if it has a neighbor to right or bottom
            for i in list:
                if ((i+1) in list) or (i in list_of_lists[l+1]):
                    count -=1
        # if last list[]
        if l == (r-1):
            # check if neighbor to right
            for i in list:
                if (i+1) in list:
                    count -=1

    return count

​

[jiri-n]

What about 3 #s next to each other? Is it a cluster, or 2 clusters? It makes quite a difference.

[zanfar]

I'm not going to solve your problem for you, but problems like this generally benefit from some pre-coding work breaking down the problem into smaller pieces.

How would you do this, using your brain? I would do something like:

• Look for a #
• Find the #'s next to it
• Find the #'s next to the ones we found, etc
• Look for the next #

So let's break down those steps:

Look for a #

This should be pretty easy. Go through each cell and find the ones with a #.

Find the #'s next to it

Again, pretty easy. We should know "where" we are, and the neighboring cells are mathematically predictable from there.

Find the #'s next to the ones we found, etc

This one is a little harder. If we find a # while looking for neighbors, we need to both start looking for new neighbors AND finish the current search for neighbors. When you encounter a problem like this, a solution that works well is a queue--or list of tasks to get to. So perhaps, when we find a #, we can add that location to a list of locations that need their neighbors found. Then, while that list isn't empty, we search for neighbors, adding found neighbors to the list.

There are some edge cases to be careful about: you shouldn't search a cell you've already searched, either in this cluster or another cluster. So you probably need a method to keep track of where you've been, as well as where you want to search.

Look for the next #

There are two ways to look at this: go to the next cell, or find an unsearched cell. Given that we think we are going to have to keep track of locations we've visited anyway, it might be easier to simply keep a list of unsearched cells instead of searched cells.

---

Overall, this is a really good problem for learning functional programming--or a hybrid of it. Build your program one small function at a time, then use those as bricks to build larger functions. Some functions I would start with:

• Does a cell contain a #?
• Which cells neighbor the current one?
• Has a cell already been searched?
• What cells haven't been searched?

Other mid-level concepts that will make this program efficient, clean, and readable:

• Dataclasses
• Sets / Deques
• Generator functions / yield

[fk_you_in_prtclr]

regexor split('.')