1

我有一个有趣的小问题。

我需要计算文件中字符“组”的数量。说文件是...

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

然后代码将计算# 组的数量。例如，上面将是3. 它包括对角线。到目前为止，这是我的代码：

build = []
height = 0
with open('file.txt') as i:
  build.append(i)
  height += 1
length = len(build[0])
dirs = {'up':(-1, 0), 'down':(1, 0), 'left':(0, -1), 'right':(0, 1), 'upleft':(-1, -1), 'upright':(-1, 1), 'downleft':(1, -1), 'downright':(1, 1)}

def find_patches(grid, length):
  queue = []
  queue.append((0, 0))
  patches = 0
  while queue:
    current = queue.pop(0)
    line, cell = path[-1]
    if ## This is where I am at. I was making a pathfinding system.
4

2 回答 2

1

这是我想出的一个天真的解决方案。最初我只是想遍历所有元素一次检查每个元素，如果我可以将它放入现有组中。但是，这不起作用，因为某些组仅在以后合并（例如，在处理#该行中的第二个之前，第二行中的第一个不属于大组#）。所以我开始研究一个合并算法，然后我想我可以从一开始就做到这一点。

所以现在它的工作原理是我把每一个都#放在自己的组中。然后我继续查看两组的组合，并检查它们是否彼此足够接近以至于它们属于同一组。如果是这种情况，我将它们合并并重新开始检查。如果我完全查看了所有可能的组合并且无法再合并，我知道我已经完成了。

from itertools import combinations, product
def canMerge (g, h):
    for i, j in g:
        for x, y in h:
            if abs(i - x) <= 1 and abs(j - y) <= 1:
                return True
    return False

def findGroups (field):
    # initialize one-element groups
    groups = [[(i, j)] for i, j in product(range(len(field)), range(len(field[0]))) if field[i][j] == '#']

    # keep joining until no more joins can be executed
    merged = True
    while merged:
        merged = False
        for g, h in combinations(groups, 2):
            if canMerge(g, h):
                g.extend(h)
                groups.remove(h)
                merged = True
                break

    return groups

# intialize field
field = '''\
..##.#..#
##..####.
.........
###.###..
##...#...'''.splitlines()
groups = findGroups(field)

print(len(groups)) # 3
于 2013-09-02T09:50:54.910 回答
0

我不确定您的代码要做什么。您的with语句打开一个文件，但您所做的只是将文件对象附加到with结束前的列表中，然后它被关闭（不读取其内容）。我怀疑他不是你想要的，但我不确定你的目标是什么。

如果我正确理解您的问题，您正在尝试计算图形的连接分量。在这种情况下，图形的顶点是“#”字符，而边是这些字符在任何方向（水平、垂直或对角线）上彼此相邻的位置。

有非常简单的算法可以解决这个问题。一种是使用不相交的集合数据结构（也称为“联合查找”结构，因为union和find是它支持的两个操作）'#'在从文件中读取字符组时将它们连接在一起。

这是我不久前为回答另一个问题而写的一个相当小的不相交集：

class UnionFind:
    def __init__(self):
        self.rank = {}
        self.parent = {}

    def find(self, element):
        if element not in self.parent: # leader elements are not in `parent` dict
            return element
        leader = self.find(self.parent[element]) # search recursively
        self.parent[element] = leader # compress path by saving leader as parent
        return leader

    def union(self, leader1, leader2):
        rank1 = self.rank.get(leader1,1)
        rank2 = self.rank.get(leader2,1)

        if rank1 > rank2: # union by rank
            self.parent[leader2] = leader1
        elif rank2 > rank1:
            self.parent[leader1] = leader2
        else: # ranks are equal
            self.parent[leader2] = leader1 # favor leader1 arbitrarily
            self.rank[leader1] = rank1+1 # increment rank

以下是如何将它用于您的问题，x, y为节点使用元组：

nodes = set()
groups = UnionFind()

with open('file.txt') as f:
    for y, line in enumerate(f): # iterate over lines
        for x, char in enumerate(line): # and characters within a line
            if char == '#':
                nodes.add((x, y)) # maintain a set of node coordinates

                # check for neighbors that have already been read
                neighbors = [(x-1, y-1), # up-left
                             (x, y-1),   # up
                             (x+1, y-1), # up-right
                             (x-1, y)]   # left
                for neighbor in neighbors:
                    if neighbor in nodes:
                        my_group = groups.find((x, y))
                        neighbor_group = groups.find(neighbor)
                        if my_group != neighbor_group:
                            groups.union(my_group, neighbor_group)

# finally, count the number of unique groups
number_of_groups = len(set(groups.find(n) for n in nodes))
于 2013-09-02T09:51:05.157 回答