该代码是我为解决2016年8月社区挑战所做的尝试。来自一个每天都会下雨的城市，这个挑战正好在我的小巷=）
2。算法
我使用了他的答案中概述的解决方案200_success♦：每个
Cell跟踪它属于哪个Basin；最初假定每个Cell位于其自己的Basin中。每个Basin都有一个sink或最低的Cell，它充当Basin的“代表元素” 以及成员数。
Topography跟踪所有Basin的。
对于每个
Basin，找到水槽邻居中的最低邻居。如果最低的还不是此Basin的成员，请将其单元格转移到最低的邻居
Basin中，并通知Topography不再存在更高的盆地。重复步骤2，直到不再存在为止。
让
Topography枚举Basin s及其计数。3。输入和输出
示例1
输入：rainage-example-1.txt
输出：
Height Farmland:
[[1 5 2]
[2 4 7]
[3 6 9]]
Basins:
(A) A (B)
A A B
A A A
Letter Size Sink
A 7 (0, 0)
B 2 (0, 2)
示例2
输入：rainfall-example-2.txt
输出：
Height Farmland:
[[1 0 2 5 8]
[2 3 4 7 9]
[3 5 7 8 9]
[1 2 5 4 3]
[3 3 5 2 1]]
Basins:
A (A) A A A
A A A A A
B B A C C
(B) B B C C
B B C C (C)
Letter Size Sink
A 11 (0, 1)
B 7 (3, 0)
C 7 (4, 4)
示例3
输入：rainage-example-3.txt
输出：
Height Farmland:
[[0 2 1 3]
[2 1 0 4]
[3 3 3 3]
[5 5 2 1]]
Basins:
(B) B A A
B A (A) A
B A A C
B C C (C)
Letter Size Sink
A 7 (1, 2)
B 5 (0, 0)
C 4 (3, 3)
示例4
输入：rainage-example-4.txt
输出：
Height Farmland:
[[ 4 23 25 21 29 16 23 29 12 28]
[ 0 12 26 0 19 23 9 13 11 29]
[26 24 18 21 22 4 29 1 5 28]
[13 15 18 3 6 7 15 15 0 9]
[29 29 23 6 28 1 11 1 3 21]
[ 6 3 0 13 11 0 28 0 25 17]
[20 15 7 24 3 8 5 21 12 23]
[ 0 9 24 12 19 23 9 29 26 21]
[ 1 12 12 2 14 2 0 16 2 6]
[14 5 14 7 26 12 24 6 5 25]
[18 25 20 29 17 23 23 2 24 19]
[ 9 0 6 2 19 19 12 10 18 28]
[ 8 27 7 23 14 9 3 14 18 25]
[ 6 19 13 9 3 0 21 3 2 16]
[ 6 1 14 12 19 22 15 2 19 12]
[17 24 27 8 15 26 16 6 0 27]
[ 0 15 3 4 2 19 0 3 17 19]
[ 3 17 14 19 20 20 25 1 7 19]
[10 13 13 22 27 20 21 28 12 4]
[27 20 19 17 28 0 13 4 1 10]]
Basins:
K K M M AI (AI) AE A A A
(K) K M (M) M Y (AE) AB A A
K K (AN) M Y (Y) AB (AB) A A
(AJ) AJ X (X) X C C A (A) A
B B B X C C C T A A
B B (B) B C (C) C (T) T (AR)
N B B AA (AA) C (AS) T (AK) AK
(N) N B L AA F F F P P
N N L (L) L F (F) F (P) P
N (AL) AL L L F F I P P
H H H U (AP) F I (I) I (AO)
H (H) H (U) U G AF I I I
AH H H U G G (AF) V W W
(AH) Q H G G (G) G V (W) W
Q (Q) Q E G G V (V) O (AQ)
D Q AD E E E J O (O) O
(D) D (AD) E (E) J (J) J O O
D D AD E E J J (Z) Z AG
D D (AC) AC E R R Z S (AG)
D D AC (AM) R (R) R S (S) S
Letter Size Sink
A 12 (3, 8)
B 10 (5, 2)
C 9 (5, 5)
D 9 (16, 0)
E 9 (16, 4)
F 9 (8, 6)
G 9 (13, 5)
H 9 (11, 1)
I 7 (10, 7)
J 6 (16, 6)
K 6 (1, 0)
L 6 (8, 3)
M 6 (1, 3)
N 6 (7, 0)
O 6 (15, 8)
P 6 (8, 8)
Q 5 (14, 1)
R 5 (19, 5)
S 4 (19, 8)
T 4 (5, 7)
U 4 (11, 3)
V 4 (14, 7)
W 4 (13, 8)
X 4 (3, 3)
Y 3 (2, 5)
Z 3 (17, 7)
AA 3 (6, 4)
AB 3 (2, 7)
AC 3 (18, 2)
AD 3 (16, 2)
AE 2 (1, 6)
AF 2 (12, 6)
AG 2 (18, 9)
AH 2 (13, 0)
AI 2 (0, 5)
AJ 2 (3, 0)
AK 2 (6, 8)
AL 2 (9, 1)
AM 1 (19, 3)
AN 1 (2, 2)
AO 1 (10, 9)
AP 1 (10, 4)
AQ 1 (14, 9)
AR 1 (5, 9)
AS 1 (6, 6)
示例5
输入：rainfall-example-5.txt [20x20地图，高度= 1000]
示例6
输入：rainage-example-6.txt [地图：55x55，高度：55 ^ 2]
4。评论
不赞成使用
chararray，因为它似乎已被弃用。我尝试将数组与bool = string一起使用，但是当我尝试更新数组时，这使我出错。 我处理琴弦和
str_rep的方式感觉不对。 我的代码结构感觉不错，但是类感觉很空。
我的代码在大片土地上挣扎，例如rainfall-example-6.txt。这是正常现象还是可以改进算法？
无用的文档字符串？
5。代码
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import string
import numpy as np
from numpy import unravel_index
ALPHABETH = string.ascii_uppercase
ALPHABETH_len = len(ALPHABETH)
def num_2_alpha(num):
'''
Converts an arabic number 0, 1, 2.. to it's corresponding letter A, B, C, ....
Example:
0 > A
1 > B
26 > Z
27 > AA
'''
quotient, remainder = divmod(num, ALPHABETH_len)
return quotient*ALPHABETH[0] + ALPHABETH[remainder]
def create_test_file(max_height, shape):
'''
Creates a random height map with dimensions x, y (from shape)
and height from 0 to max_height.
'''
random_integers = np.random.randint(max_height, size=shape[0]*shape[1])
return random_integers.reshape(shape[0], shape[1])
def format_topography(topography_):
'''
Inputs a typography of the farmland formated in a character array
this function formats the typography into a nicer looking string.
Input
[['(A)' 'A' '(B)']
['A' 'A' 'B']
['A' 'A' 'A']]
Output:
(A) A (B)
A A B
A A A
'''
rows, columns = topography_.shape
column_padding = [0]*columns
for i in range(columns):
column_padding[i] = len(max(topography_[:, i], key=len))
padded_string = ''
for i in range(rows):
for j in range(columns):
padded_string += ' {:^{}} '.format(
topography_[i, j], column_padding[j])
padded_string += '\n'
return padded_string
def basin_2_string(basin_list):
'''
Input is a dictionary of basins where the key is the sink
Example output:
A: 7, Sink: (1, 2)
B: 5, Sink: (0, 0)
C: 4, Sink: (3, 3)
'''
letter_padding = len(num_2_alpha(len(basin_list)))
sep1 = ' '*(len('letter')-letter_padding)
size_padding = len(str(basin_list[0].size))
sep2 = ' '*(len('Size')-size_padding)
basin_string = 'Letter Size Sink\n'
for i, basin in enumerate(basin_list):
basin_string += '''{:>{}} {} {:{}d} {} {}
'''.format(num_2_alpha(i), letter_padding, sep1, basin.size, size_padding, sep2, basin.sink)
return basin_string
def create_height_map(filename):
'''
Input: a filename with a textfile formated as
1 5 2
2 4 7
3 6 9
Ouputs a matrix of the height map.
'''
file = open(filename, 'r')
matrix = np.matrix([map(int, line.split()) for line in file])
file.close()
return matrix
def create_matrix_map(class_type, shape):
'''
Creates a dictionary where the keys are (x, y) coordinates.
This is used to store / index the basins and the cells
'''
length, width = shape
matrix = dict()
for i in xrange(length):
for j in xrange(width):
matrix[(i, j)] = class_type([i, j], [length, width])
return matrix
def neighboors_list(coordinates, shape):
'''
Makes a list of all the neighboors to a point in the height map
'''
length, width = shape
x, y = coordinates
neighboors = []
if x < 0 or x == length or y < 0 or y == width:
ValueError("The coordinates lies outside the matrix")
if x > 0:
neighboors.append((x-1, y))
if x + 1 < length:
neighboors.append((x+1, y))
if y > 0:
neighboors.append((x, y-1))
if y + 1 < width:
neighboors.append((x, y+1))
return neighboors
def create_basins_and_cells(height_map, shape):
'''
This creates the basins and the cells using the following algorithm:
1. Each Cell keeps track of which Basin it belongs to; each Cell is initially assume to be in its own Basin.
Each Basin has a sink, or lowest Cell, which acts as a "representative element" of the Basin,
as well as a member count. Topography keeps track of all Basins.
2. For each Basin, find lowest of the sink's neighbours. If the lowest is not already a member of this Basin,
transfer its cells into the lowest neighbour's Basin, and notify Topography that the higher basin no longer exists.
3. Repeat step 2 until no further action is necessary.
'''
basins = create_matrix_map(Basin, shape)
cells = create_matrix_map(Cell, shape)
topography_changed = True
while topography_changed:
topography_changed = False
for old_basin_coords in basins:
sink_coords = basins[old_basin_coords].sink
lowest_neighboor_height = height_map[sink_coords]
lowest_neighboor_coords = sink_coords
for neighboor in cells[sink_coords].neighboors:
if height_map[neighboor] < lowest_neighboor_height:
lowest_neighboor_height = height_map[neighboor]
lowest_neighboor_coords = neighboor
if lowest_neighboor_coords not in basins[old_basin_coords].cells:
topography_changed = True
new_basin_coords = cells[lowest_neighboor_coords].basin
for cell_coords in basins[old_basin_coords].cells:
basins[new_basin_coords].cells.append(tuple(cell_coords))
cells[cell_coords].basin = new_basin_coords
basins[new_basin_coords].size = len(
basins[new_basin_coords].cells)
del basins[old_basin_coords]
break
basin_list = sorted(basins.values(), key=lambda x: x.size, reverse=True)
return basin_list, cells
def create_topography(basin_list, shape):
'''
Enumerates the basins, in practice this creates the topography of the farmland
'''
character_length = len(num_2_alpha(len(basin_list)))
topography = np.chararray(shape, itemsize=character_length+2)
for i, basin in enumerate(basin_list):
letter = num_2_alpha(i)
for coords in basin.cells:
if coords == basin.sink:
topography[coords] = '('+letter+')'
else:
topography[coords] = letter
return topography
class Cell():
'''
Simple class describing a single cell in the height map.
'''
def __init__(self, coordinates, shape):
self.coordinates = tuple(coordinates)
self.neighboors = neighboors_list(coordinates, shape)
self.basin = tuple(coordinates)
class Basin():
'''
Simple class describing the basins in the height map.
'''
def __init__(self, coordinates, shape):
self.coordinates = tuple(coordinates)
self.sink = tuple(coordinates)
self.cells = [tuple(coordinates)]
self.size = 1
def __repr__(self):
return '''<Size: {}, Sink: {}, Cells: {}>\n
'''.format(self.size, self.sink, self.cells)
class Topography():
'''
A group of farmers has some elevation data, and we're going to help them understand
how rainfall flows over their farmland.
We'll represent the land as a two-dimensional array of altitudes and use the following
model, based on the idea that water flows downhill:
If a cell’s four neighboring cells all have higher altitudes, we call this cell a sink; water collects in sinks.
Otherwise, water will flow to the neighboring cell with the lowest altitude. If a cell is not a sink,
you may assume it has a unique lowest neighbor and that this neighbor will be lower than the cell.
Cells that drain into the same sink – directly or indirectly – are said to be part of the same basin.
Your challenge is to partition the map into basins. In particular, given a map of elevations,
your code should partition the map into basins and output the sizes of the basins, in descending order.
'''
def __init__(self, filename):
self.height_map = create_height_map(filename)
self.shape = self.height_map.shape
self.basins, self.cells = create_basins_and_cells(
self.height_map, self.shape)
self.topography = create_topography(self.basins, self.shape)
self.basin_sizes = [basin.size for basin in self.basins]
def __str__(self):
string = '''
Height Farmland:
{}
Basins:
{}
{}'''.format(
str(self.height_map),
format_topography(self.topography),
basin_2_string(self.basins))
return string
if __name__ == '__main__':
n = 50
seperator = '-'*n
print seperator
for i in range(1, 5):
print Topography('rainfall-example-{}.txt'.format(i))
print seperator
print
# np.savetxt('rainfall-example-4.txt', create_test_file(30, (20, 10)), delimiter = ' ', fmt='%d')
# np.savetxt('rainfall-example-5.txt', create_test_file(15, (30, 25)), delimiter = ' ', fmt='%d')
#1 楼
这些类感觉空虚，因为您基本上只是在使用精美的词典和一堆函数。别误会我的意思-基本上这就是一个类的全部，但是如果您打算使用类，那么您确实想在其中封装功能。您几乎所有的函数都应该成为您其中一个类的实例方法。从入口点到结尾，我将概述编写的代码。
我遇到的最大问题是，您的
create_test_file是名字不好-更好的名字是
create_test_matrix 损坏。它不能保证每个单元格都是一个接收器或具有唯一的最小邻居。
我要解决三件事。
编写一种称为
create_test_matrix的方法，该方法可使矩阵更改
create_test_file以实际写入有效的测试文件使矩阵创建成为一个迭代过程-从左到右，从上到下生成新值（或您喜欢的任何方向）。确保它们不违反已创建值的约束，然后继续。
现在我们实际上正在生成有效的测试文件，让我们看一下其余的代码。
Topography类使用文件名对我来说很有趣。我希望Topography能够接收数据，并提供一种从文件中加载它的类方法。这也意味着通过测试，您不需要遍历中间文件。顺便说一句，您的实现存在错误（并且您的测试文件无效）。它们应该具有矩阵大小作为第一行，并且您的测试文件没有该大小（并且您的代码无法处理它）。这个类方法基本上将以
create_height_map结尾，因此我将把该函数的内容拉出来并放在其中。这样做时，我还将使用上下文管理器安全地打开和关闭文件。我还将重命名文件对象变量，以便它不会掩盖内置的file。我还将使用列表推导而不是map，因为它更加Python易读。我忘记了np.matrix是否可以使用生成器对象，但是如果可以，那么我将使用生成器理解而不是列表理解。@classmethod
def from_file(cls, filename):
with open(filename, 'r') as rainfall_data:
data_iter = iter(rainfall_data)
# skip the shape
next(data_iter)
rainfall_matrix = np.matrix(
[[int(data) for data in line.split()]
for line in data_iter]
)
return Topography(rainfall_matrix)
接下来我要将
create_basins_and_cells拉入Topography和create_matrix_map。我将从
create_matrix_map开始。这可能只是字典理解。我还将交换元组的列表，因为您通常应该首选不变性。@staticmethod
def create_matrix_map(cls, shape):
length, width = shape
return {(i, j): cls((i, j), shape) for i in xrange(length) for j in xrange(width)}
我将其设为静态方法，因为它不需要任何内在函数类或实例的属性。我仍然给它第一个参数
cls而不是class_type，因为这对我来说更容易理解-YMMV。接下来，我将深入研究
create_basins_and_cells。我不是您的算法的忠实拥护者-看来您应该能够以更智能的方式遍历单元格。当我自己解决此问题时，我按降序对单元格进行了排序，并将其借给一种非常干净的算法。但是，我的解决方案也遇到了性能问题，因此，我将在这里提出一些新的建议（使用伪代码，因为我尚未完全编写出代码）。目标能够以任意顺序遍历所有单元，而不必进行太多次。为此，我认为我们希望将“创建盆和单元”阶段与“分类为正确的盆”阶段结合起来。这可能看起来像这样（伪代码，我还没有完全弄清楚实际代码）。
for row in topography
for cell in row
for each neighbor of cell
if the neighbor feeds into this cell and has already been loaded
add it to this cell's basin
if the cell is a sink
add it to an array of sinks
else
add this cell to the lowest neighbor (if it already has been loaded)
sizes = []
for sink in sinks
count the number of connected components to that sink, append it to sizes
print sizes sorted in descending order, space separated
这还是很粗糙的，但是我认为我们可以通过只传递一次数据来加快速度。我们也可以分阶段将数据加载到内存中，如果我们将这些计算的结果存储在其他单元格上，那么我认为我们将避免每个单元格做过多的额外工作（这是您可以做的另一件事。计算-您的许多计算都会重复进行，并且可以存储在单元格中。我希望本周末回到这个答案，并修复此部分并添加实际的代码。
我将只涉及一些字符串内容以完成操作。总的来说，这些都应该成为您不同类的实例方法。您应该确保每个类都有自己的
__str__，__repr__和__unicode__方法。然后，当您最终打印出地形图时，您不必担心具有合理的盆地和单元格字符串表示形式，您要做的就是担心填充。，您最好的朋友也会成为
textwrap.dedent-使用多行字符串时，您不必那样丑陋地缩进。 #2 楼
次要自动记账注意事项：您可以basins[new_basin_coords].size = len(
basins[new_basin_coords].cells)
但是由于这种关系（盆地的大小始终是其
.cells的长度）是固定的，因此应在代码中使其自动在Basin对象上：@property
def size(self):
return len(self.cells)
此外，您是对的，您的课程有点裸露。尝试使它们独立。唯一调用
create_topography的是Topography.__init__，所以也许将其移动为Topography.__init_topography。与create_height_map和create_basins_and_cells和neighbors_list和basin_2_string和format_topography相似... #3 楼
以下是一些可以帮助您改进代码的事情：使用更好的算法
由于尚未指出，因此该算法有问题。通过简单的输入就可以很容易地看到问题，其中整个区域是一个正方形盆地：
Height Farmland:
[[2 2 2 2 2]
[2 1 1 1 2]
[2 1 0 1 2]
[2 1 1 1 2]
[2 2 2 2 2]]
Basins:
(H) D A B (I)
D (D) A (B) B
A A (A) A A
E (E) A (C) C
(F) E A C (G)
Letter Size Sink
A 9 (2, 2)
B 3 (1, 3)
C 3 (3, 3)
D 3 (1, 1)
E 3 (3, 1)
F 1 (4, 0)
G 1 (4, 4)
H 1 (0, 0)
I 1 (0, 4)
解决该问题的一种方法是针对每个正方形， “水往哪儿流？”如果我们假设（如问题所述）水总是沿着最陡峭的坡度流下，那么只需创建一条从网格上每个点到水不再流向的路径的问题。
Don' t误导文档
num_2_alpha的文档字符串说26将转换为Z，而27会产生AA，但事实并非如此。实际上，由于编号从0开始，因此25将分别产生Z和26和27分别产生AA和AB。在Python 2.7中，
xrange优于range 这只是一个小问题，但是当前代码在多个地方使用了
range，而xrange可能会提供更好的性能。有关range和xrange的讨论，请参见此问题。 #4 楼
这个整洁的小挑战有两个棘手的方面（如他们所说的“ Knackpunkte”）：基于4个单元格的局部邻域对给定单元格的宿识别
/>所连接组件的标识
解决方案的正确性取决于正确解决这两个问题-其余就是梦游。因此，重要的是使这两件事分开代码的重点，以便可以分别进行编码（和验证/测试）。
如果相关逻辑的某些部分散布在数十个工件（函数，结构，类）和数百个源代码行中，那将是有害的。例如，我仍然不了解原始Python解决方案的一些重要细节，尽管我怀疑这是不正确的，但我不能肯定地说一遍。
所以这是一个替代方案
不相交集联合
最简单，最有效的方法来标识连接的组件集（“盆地”） ）当然是Disjoint Set Forest，它只是一个带有微小功能的谦虚数组。请参见Wikipedia中的不相交集数据结构，或相关的HackerEarth教程。
为给定集合成员查找集合代表（“ root”）的函数的经典形式如下所示：
static int root (int[] a, int i)
{
for (int j = a[i]; j != i; )
a[i] = j = a[i = j];
return i;
}
在寻找根的同时，此功能还执行一点路径压缩，以加快进一步的搜索速度。这并不是使算法可证明是最优的全路径压缩（如Wikipedia文章所述），因为这将需要辅助堆栈或真正笨拙的调用堆栈。但是它确实可以以微不足道的成本改善性能。
在这里，我提出一种变体，其中设置的根插槽用于跟踪成员身份计数（存储为负数），而不是指向自己。这需要对查找根代码进行一些修改：由于根不再指向自己，因此引入了一步的滞后，因此它们的槽位内容不能再盲目存储到其他槽位中。副作用是，此修改消除了经典版本的最终冗余存储：
static int root (int[] a, int i)
{
int j = a[i];
if (j >= 0)
for (int k; (k = a[i = j]) >= 0; j = k)
a[i] = k;
return i;
}
以经典形式，可以通过简单的赋值将由任意成员x和y标识的两个集合连接起来：
a[root(x)] = root(y);
拥有可用的成员计数可以按等级进行并集，即始终将较小的集合附加到较大的集合，以使内容紧凑并最小化路径压缩的工作量。这样可以确保结构在重载下表现良好（尽管压缩路径并不是最佳选择），因此值得为连接集创建单独的函数：
static void join (int[] a, int i, int j)
{
if ((i = root(a, i)) != (j = root(a, j)))
{
if (a[i] <= a[j]) // the roots hold negative membership counts
{
a[i] += a[j];
a[j] = i;
}
else
{
a[j] += a[i];
a[i] = j;
}
}
}
连接的组件分析已经完成并得到了简化，并且效率非常简单（几乎）。
分析本地邻居一个单元格
现在进行邻域/接收器分析。每个单元格的汇点由其在指南针的四个点上的相邻邻居确定。这样确定的接收器是最终的-永远都不可能改变。流域成员资格在处理过程中可能会有所不同，但对于任何给定的单元格而言，汇区是什么。因此，可以在一次扫描输入中执行此分析，一次只在内存中保留三行（上一，当前和下一个）。
一个简单的技巧是用无害的伪值填充地图的外部边缘，以减少需要单独处理的案例（实际上是边缘案例）的数量。由于我们正在寻找最小值，因此如果填充单元格的数据类型具有最大可能值，则它们是透明的。将坐标编码为
row * column_count + column可以减少混乱，并将坐标映射到紧凑的索引范围，这些索引可以直接与不相交的集合林一起使用。处理代码的要点是遍历当前行的此循环，找到每个像元的接收器并更新代表盆地成员资格的不相交集林
dsf[]： for (int col = 1; col <= col_count; ++col)
{
var n_w = Math.Min(prev_row[col], curr_row[col - 1]);
var s_e = Math.Min(next_row[col], curr_row[col + 1]);
var min = Math.Min(n_w, s_e);
if (curr_row[col] > min)
{
int curr = (row - 1) * col_count + (col - 1), sink = curr;
if (min == prev_row[col])
sink -= col_count;
else if (min == next_row[col])
sink += col_count;
else if (min == curr_row[col - 1])
sink -= 1;
else
sink += 1;
join(dsf, curr, sink);
}
}
由于填充，列和行索引以1为底，因此在对坐标进行编码时必须减去1。分别进行最小查找和确定相关坐标以获取更清晰，更紧凑的代码，这是必需的，因为C＃在元组分配等方面缺乏Python的优雅。
其余的是基本知识，不值得在谈论。请参阅PasteBin上的CodeReview_Rainfall.cs，其中包含有条件的
using指令，以便它可以与LINQPad一起使用（可以免费下载）。为了完整起见，以下是按降序打印计数的方法： var basins = new HashSet<int>(Enumerable.Range(0, dsf.Length).Select(i => root(dsf, i)));
var counts = basins.Select(sink => -dsf[sink]).OrderBy(x => -x);
Console.WriteLine(string.Join(" ", counts));
表明像Python和Perl这样的语言不再以最小的麻烦完成事情。 ;-)
评论
\ $ \ begingroup \ $
在我看来，这可能是一个新的C＃问题，而不是Python答案。
\ $ \ endgroup \ $
–爱德华
16年8月21日在13:21