一年后，我实际上想出了解决这个问题的方法，我再也高兴不了。但是，我希望对解决方案的设计或其他有关以下方面的意见提出批评：样式，OOP做法等。
问题陈述
一群农民有一些海拔数据，我们将帮助他们
了解降雨如何流过农田。
我们将土地表示为二维的海拔高度数组，并且
基于水下坡的想法，使用以下模型：
如果一个单元格的四个相邻单元格都具有较高的海拔高度，我们称此单元格为汇。水在水槽中积聚。
否则，水将以最低的
流向相邻的小室。如果某个单元格不是接收器，则可以假定它具有唯一的最低邻居，并且该邻居将低于该单元格。
直接或间接排入同一水槽的细胞
被称为同一水池的一部分。
您的挑战是将地图分成多个盆地。特别是，给定高程图，您的代码应将地图划分为
盆地，并按降序输出盆地的大小。
假定高程图是正方形的。输入将以一行
开始，该行带有一个整数S，即地图的高度（和宽度）。接下来的S
行将分别包含地图的一行，每行具有S个整数–行中S个单元格的高程。一些农民土地面积较小，如下例所示，而有些土地面积较大。
但是，在任何情况下，农民土地面积都不大于S =
5000。
您的代码应按
降序输出以空格分隔的清单。 （忽略尾随空格。）
下面是一些示例：
-----------------------------------------
Input: Output:
3 7 2
1 5 2
2 4 7
3 6 9
The basins, labeled with A’s and B’s, are:
A A B
A A B
A A A
-----------------------------------------
Input: Output:
1 1
10
There is only one basin in this case.
The basin, labeled with A’s is:
A
-----------------------------------------
Input: Output:
5 11 7 7
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
The basins, labeled with A’s, B’s, and C’s, are:
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
-----------------------------------------
Input: Output:
4 7 5 4
0 2 1 3
2 1 0 4
3 3 3 3
5 5 2 1
The basins, labeled with A’s, B’s, and C’s, are:
A A B B
A B B B
A B B C
A C C C
-----------------------------------------
我用Perl编写的解决方案如下：
Cell类（在矩阵中对单个单元进行建模）： {
package Cell;
use List::MoreUtils qw(all);
# models 4 nearest neighbors to position i,j forall i,j
my $neighbors = [ [ 0, -1], # left
[-1, 0], # top
[ 0, 1], # right
[+1, 0], # bottom
];
sub new {
my ($class, %attrs) = @_;
$attrs{is_sink} ||= 0;
bless \%attrs, $class;
}
# accessor/setter methods
sub elevation {
return shift->{elevation};
}
sub x {
return shift->{x};
}
sub y {
return shift->{y};
}
sub is_sink {
return shift->{is_sink};
}
sub set_sink {
shift->{is_sink} = 1;
}
sub xy {
my $self = shift;
return [$self->x, $self->y];
}
# string representation of a Cell
sub to_s {
my ($self) = @_;
return "(" . $self->x . "," . $self->y . ") = " . $self->elevation;
}
# returns the neighbors that flow into this Cell
sub get_flowing_neighbors {
my ($self, $rainfall) = @_;
# the neighbors of this cell flow into it
# iff this cell's elevation is less than their neighbors
# AND the neighboring cell has no other neighbors
# (that are not this cell) that have a lower (or equal) elevation
return grep {
$self->elevation < $_->elevation
&& all { $self->elevation <= $_->elevation } $_->get_neighbors($rainfall)
} $self->get_neighbors($rainfall);
}
# returns the neighbors of this Cell
sub get_neighbors {
my ($self, $rainfall) = @_;
my ($rows, $cols) = ($rainfall->rows, $rainfall->cols);
my ($x, $y) = ($self->x, $self->y);
my @adjs;
NEIGHBORS:
for my $neighbor ( @$neighbors ) {
my ($xmod, $ymod) = ($x + $neighbor->[0], $y + $neighbor->[1]);
# x and y must be in the bounds of the matrix
next NEIGHBORS
if $xmod > $rows - 1 || $ymod > $cols - 1 || $xmod < 0 || $ymod < 0;
push @adjs,
$rainfall->cell($xmod, $ymod);
}
return @adjs;
}
1;
} # end Cell
Rainfall类（对整个矩阵及其上的操作进行建模）： {
package Rainfall;
sub new {
my ($class, %attrs) = @_;
# initialize all elements of the matrix to cells O(n)
for my $i ( 0 .. @{ $attrs{field} } - 1) {
for my $j ( 0 .. @{ $attrs{field}->[$i] } - 1 ) {
$attrs{field}->[$i]->[$j] =
Cell->new( x => $i,
y => $j,
elevation => $attrs{field}->[$i]->[$j],
);
}
}
bless \%attrs, $class;
}
# accessor methods
sub field {
my $self = shift;
return $self->{field};
}
sub cell {
my ($self, $i, $j) = @_;
return $self->field->[$i]->[$j];
}
sub rows {
my $self = shift;
return $self->{rows};
}
sub cols {
my $self = shift;
return $self->{cols};
}
# determines if a given Cell is a sink
sub is_sink {
my ($self, $cell) = @_;
my $min = $cell->elevation;
my @neighbors = $cell->get_neighbors($self);
for my $neighbor ( @neighbors ) {
$min = ($min, $neighbor->elevation)[$min > $neighbor->elevation];
}
# found a sink, mark it
if( $min == $cell->elevation ) {
$cell->set_sink;
return 1;
}
return 0;
}
# returns a list of all Sinks in the matrix
# O(N * M) where N = # of rows and M = # of cols
sub find_sinks {
my ($self) = @_;
my @sinks;
for my $row ( 0 .. $self->rows - 1 ) {
for my $cell ( @{ $self->field->[$row] } ) {
push @sinks, $cell
if $self->is_sink($cell);
}
}
return @sinks;
}
# given an Array of Sinks, find the Basins in this field
# O(n)
sub find_basins_from_sinks {
my ($self, @sinks) = @_;
my %basin;
my $basin_marker = 'A';
# determine how many cells eventually flow into this one
for my $sink ( @sinks ) {
$basin{$basin_marker++} = $self->basin_size($sink);
}
return %basin;
}
# recursively find the number of Cells in the Basin
# attached to the given Cell
sub basin_size {
my ($self, $cell) = @_;
my $size = 1;
for my $neighbor ( $cell->get_flowing_neighbors($self) ) {
$size += $self->basin_size($neighbor);
}
return $size;
}
1;
} # end Rainfall
单元测试可验证结果是否与上述示例匹配：
{ # Tests
use Test::More tests => 4;
{ # 3x3 field
my $r = Rainfall->new( rows => 3,
cols => 3,
field => [ [1, 5, 2],
[2, 4, 7],
[3, 6, 9] ]);
my @sinks = $r->find_sinks;
my %basin = $r->find_basins_from_sinks(@sinks);
is_deeply(
[sort { $b <=> $a } values %basin],
[7, 2],
'Correctly divided 3x3 field into 2 basins'
);
}
{ # 1x1 field
my $r = Rainfall->new( rows => 1,
cols => 1,
field => [ [1] ]);
my @sinks = $r->find_sinks;
my %basin = $r->find_basins_from_sinks(@sinks);
is_deeply(
[sort { $b <=> $a } values %basin],
[1],
'Correctly divided 1v1 field into 1 basin'
);
}
{ # 5x5 field
my $r = Rainfall->new( rows => 5,
cols => 5,
field => [ [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] ]);
my @sinks = $r->find_sinks;
my %basin = $r->find_basins_from_sinks(@sinks);
is_deeply(
[sort { $b <=> $a } values %basin],
[11, 7, 7],
'Correctly divided 5v5 field into 3 basins'
);
}
{ # Test 4x4 field
my $r = Rainfall->new( rows => 4,
cols => 4,
field => [ [0, 2, 1, 3],
[2, 1, 0, 4],
[3, 3, 3, 3],
[5, 5, 2, 1] ]);
my @sinks = $r->find_sinks;
my %basin = $r->find_basins_from_sinks(@sinks);
is_deeply(
[sort { $b <=> $a } values %basin],
[7, 5, 4],
'Correctly divided 4v4 field into 3 basins'
);
}
}
基本算法搜索矩阵中的每个元素，并确定该元素是否为接收器（意味着其所有邻居都流入其中）。
sinks = []
for i in matrix: # rows
for j in matrix[i]: # columns
if matrix[i][j] is a sink:
sinks.add( matrix[i][j] )
从问题描述中，您可以知道每个接收器一个
Basin，因此，有了水槽之后，您需要找到Basin。要查找Basin，请从Sink开始，然后向外搜索，如果元素A）流入水槽或B）流入流入水槽的单元，则向其添加元素。当没有更多的流路要考虑时，您就停止向外搜索。#1 楼
这是一些看起来很不错的代码，看起来好像正在工作。我的批评涉及以下主题：关于样式，命名，使用的工具等的讨论。我认为您已经有意识地选择了某种样式，但是某些方面让我感到与众不同我想谈一谈。
我也喜欢过度设计。但是我觉得设计中的某些部分可以改进。
Cell 样式我很惊讶地看到您自己完成了所有OOP。 Moo / Mouse / Moose在哪里？您什么都不使用的原因是什么？有充分的理由，例如较少的依赖关系，但它们变得越来越少。
样式二空格缩进是有争议的。我（连同perlstyle）推荐4列。
样式我注意到您正在使用
{ package Foo; ... }。建议将不同的类放在不同的文件中，这样
在v5.14或更高版本（IIRC）中，存在一个
package Foo { ... }形式，它看起来更好。除非您针对的是较早的Perls，否则可能要改用它。样式您具有数组引用
$neighbors。如果作为个人风格决策，您更喜欢引用而不是非标量变量，则可以这样做。似乎并非如此，该变量的唯一用法是@$neighbors。 注意请尽可能避免使用名为
y的子例程，因为这也是音译运算符。当然，仅用作方法时这没问题。设计
is_sink方法仅返回状态值。最好（懒惰？）搜索邻居以查看它是否是一个接收器。当前，这在容易混淆的命名为Rainfall::is_sink中实现，可以说是制动封装。在Cell类之外没有充分的理由这样做。样式
xy方法不在任何地方使用。它还返回一个arrayref，这使得使用值变得更加困难。返回平面列表将更加Perlish，以便我们可以执行my ($x, $y) = $cell->xy。但是，由于我们已经有了访问器，我们不妨删除该方法。样式
to_s给我留下了相当像Ruby的名字。在Perl中，没有约定命名toString方法。但是，可以重写字符串化运算符，这可能是一个更好的选择：use overload '""' => sub { ... };
设计您的某些方法需要传入
Rainfall实例。由于每个单元格都属于某个网格，因此最好将网格存储在每个单元格中。为避免循环引用，应使用Scalar::Util::weaken来使用弱引用。或者，如果您已切换到对象系统：has grid => (weak => 1)。样式A
grep并不总是最佳解决方案：grep {
$self->elevation < $_->elevation
&& all { $self->elevation <= $_->elevation } $_->get_neighbors($rainfall)
} $self->get_neighbors($rainfall);
这是什么？代码表示：选择比我高且我是最低邻居的所有邻居。但是，由于
$_绑定了许多不同的值，因此很难理解。切勿嵌套$_的多种含义。一个简单的解决方案是添加lowest_neighbor方法。然后：grep { !$_->is_sink && $self == $_->lowest_neighbor } $self->get_neighbors;
否则，使用显式循环可以提高可读性：
my @flowing_neighbors;
for my $neighbor ($self->get_neighbors) {
next if not $self->elevation < $neighbor->elevation;
next if not all { $self->elevation <= $_->elevation } $neighbor->get_neighbors;
push @flowing_neighbors, $neighbor;
}
return @flowing_neighbors;
样式使用
@adjs作为@adjacents的缩写是不必要的混淆。要进行边界检查，可能更容易做，而不是
next NEIGHBORS
if $xmod > $rows - 1 || $ymod > $cols - 1 || $xmod < 0 || $ymod < 0;
此：遗憾的是Perl不支持链接比较运算符，但这是显示变量在特定范围内的最佳方法。比较C型
for回路的范围规格：next NEIGHBORS if not 0 <= $xmod && $xmod < $rows;
next NEIGHBORS if not 0 <= $ymod && $xmod < $cols;
Rainfall 设计您将构建一个单元对象网格。使用Flyweight模式可能会更有趣，因为每个单元格仅包含很少的状态（是否是接收器，可以很便宜地进行检查）。
设计要查找所有接收器，请查看网格中的每个单元格。如果我们暂时忘记了要编写面向对象的代码，可以考虑使用以下算法：
for (my $i = 0; $i < 10; $i++) {...} # 0..9
虽然可以构造一个病理情况，遍历所有单元格，通常可以更快地找到下一个接收器。
在Perl中，可以将单元格集实现为将坐标映射到单元格对象的哈希。
设计
basin_size与Rainfall无关。这是在Cell上的一种方法。指示符：您不使用Rainfall实例$self中的任何内容。因此，它应该是静态方法或普通子例程。您总是将Cell作为第一个参数传递，因此它可能应该是Cell实例上的方法。单一大小就足够了，就像从网格本身获取此信息一样！样式，您对输入执行零验证（例如，确保它实际上具有请求的大小，所有必需的参数实际上都是那里，或者没有使用未知参数）。为此，我经常使用
create a set of all cells.
while the set contains elements:
pick one element from the set.
until the element is a sink:
element = element->lowest_neighbor
calculate the size of the basin,
remove each member of the basin from the cells-set
模式，然后进行
rows检查。另一种选择是使用对象系统并使用my $thing = delete $args{thing} // die q("thing" required);
测试
指定属性，这看起来非常好，没有注释这里。但是，测试之间存在大量的代码重复，可以通过单个循环将其删除。
结论
这是非常好的代码，它显示了一个经验丰富，认真的程序员的工作。该算法还可以。该设计有些混乱，表示采用代码优先，设计后期的方法（可以，因为可以很容易地对其进行重构）。
评论
\ $ \ begingroup \ $
我希望我能投票两次。这非常有帮助。
\ $ \ endgroup \ $
–亨特·麦克米伦
2014年1月3日17:04
\ $ \ begingroup \ $
为了回答您的一些问题，我工作的公司仍在使用Perl 5.12（支持一些版本），所以我没有得到5.14的漂亮封装语法。同样，我们也不使用Moose。 （或Moo；我希望更改），而是拥有自己的对象系统。我决定只为这个小程序使用一个有福的哈希，如果它的大小更大，我可能会使用Moose。考虑到所有人的意见后，我仍然可以将这种可能重构为Moose软件包。
\ $ \ endgroup \ $
–亨特·麦克米伦
2014年1月3日17:07
\ $ \ begingroup \ $
您对Basin_size（）的看法是正确的，我将其移到Cell类中，它看起来更整洁，现在不必绕过Rainfall状态。您正在撰写有关错误检查的信息，即使我是该程序的唯一用户，我也需要将其包括在内（我想采访员会这样做）。关于to_s，这只是为了调试，但是感谢过载的建议，我什至不知道该功能的存在。再次感谢您的所有建议，Flyweight模式看起来特别适用，尤其是当我允许每个Cell都拥有对自己邻居的引用时。
\ $ \ endgroup \ $
–亨特·麦克米伦
2014年1月3日，17：13
\ $ \ begingroup \ $
我已经发布了修订版（仍然没有对Github进行错误检查），请看一下一下：github.com/mcmillhj/Rainfall
\ $ \ endgroup \ $
–亨特·麦克米伦
2014年1月3日，17：29
#2 楼
这是一个面试问题，这一事实改变了我如何看待代码。面试官几乎肯定会在寻找一个答案：“联合查找数据结构”或“不交集数据结构”。您是否会在开始的几秒钟内说出这些神奇的话来判断自己，是否可以自己想出类似的东西，是否可以在面试官的指导下想出类似的东西。您的解决方案可以使用抽象术语（例如
Member和DisjointSet）或特定领域的术语（Cell和Basin）。因此，您在建模中缺少盆地类。我认为，使用特定领域的术语会更好。我还希望将Rainfall重命名为Topography，因为问题是要分析地形图。这是解决方案的概述：跟踪它属于哪个
Cell；最初假定每个Basin位于其自己的Cell中。每个Basin都有一个Basin或最低的sink，它充当Cell的“代表元素”以及成员数。 Basin跟踪所有Topography。对于每个
Basin，找到水槽邻居中最低的一个。如果最低的还不是此Basin的成员，请将其单元格转移到最低的邻居Basin中，并通知Basin不再有较高的盆地。重复步骤2，直到不需要采取进一步的操作为止。
让
Topography枚举Topography s及其计数。评论
\ $ \ begingroup \ $
+1用于显式建模盆地以及使用特定于域的名称。
\ $ \ endgroup \ $
–韦恩·康拉德
2014年1月4日在16:06
\ $ \ begingroup \ $
感谢您的回复，这真的很有帮助。我可能会尝试这种解决方案，并比较我以前的解决方案。
\ $ \ endgroup \ $
–亨特·麦克米伦
2014年1月4日在16:23
#3 楼
我在这里看到的一些建议可能会有所不同。我不喜欢
Rainfall和Cell上都存在确定单元格是否为宿的逻辑。实际上，这两个类都具有称为is_sink的方法... 我的偏好是将逻辑转移到Cell上，该Cell已经知道如何计算其邻居....然后是Rainfall该类只能调用：
push @sinks, $cell
if $cell->is_sink($self);
这表示一个更大的问题，那就是重复了大量的代码（计算邻居等）。我的建议是，在创建每个单元格之后，您应该对该字段进行初始遍历。此初始化过程应使每个单元都可以计算，并存储其邻居列表，并计算该单元是否为宿。将其放在Rainfall类的构造函数中似乎是正确的主意，但是，由于初始化也可以记录接收器，因此对于构造函数而言，它似乎很多。我在栅栏上。有利的一面是它将使执行速度更快。...考虑RainFall构造函数：
sub new {
my ($class, %attrs) = @_;
# initialize all elements of the matrix to cells O(n)
for my $i ( 0 .. @{ $attrs{field} } - 1) {
for my $j ( 0 .. @{ $attrs{field}->[$i] } - 1 ) {
$attrs{field}->[$i]->[$j] =
Cell->new( x => $i,
y => $j,
elevation => $attrs{field}->[$i]->[$j],
);
}
}
my @sinks;
for my $i ( 0 .. @{ $attrs{field} } - 1) {
for my $j ( 0 .. @{ $attrs{field}->[$i] } - 1 ) {
my $cell = $attrs{field}->[$i]->[$j];
$cell.initialize($self);
push @sinks if $cell->is_sink;
}
}
$attrs{sinks} = @sinks;
bless \%attrs, $class;
}
Cell上的initialize方法将计算并存储，邻居的数组。这将大大减少需要计算它们的次数。
如果您进行了一次一次性初始化，则Cell-> is_sink可以不再使用任何参数。
从is_sink的重组以及neighbors数组的持久性来看，我对您的某些循环条件有个选择....您经常有类似以下代码：
for my $row ( 0 .. $self->rows - 1 ) {
..
您应该使用last-index运算符而不是标量运算符：
for my $row ( 0 .. $#{$self->rows} ) {
类似的东西：
for my $i ( 0 .. @{ $attrs{field} } - 1) {
应该是：
for my $i ( 0 .. $#{ $attrs{field} }) {
最后一个-pick，为什么> =时也能很好地进行减法运算：
next NEIGHBORS
if $xmod > $rows - 1 || $ymod > $cols - 1 || $xmod < 0 || $ymod < 0;
可能很容易地是：
next NEIGHBORS
if $xmod >= $rows || $ymod >= $cols || $xmod < 0 || $ymod < 0;
尽管如此，但仍不清楚$ rows和$ columns是否为数组，我更愿意：
next NEIGHBORS
if $xmod > $#{$rows} || $ymod > $#{$cols} || $xmod < 0 || $ymod < 0;
评论
\ $ \ begingroup \ $
感谢您的答复，我完全同意在Rainfall的构造函数中确定接收器，这很有意义，并使我能够将Rainfall和Cell与get_neighbors和get_flowing_neighbors分离。我也同意$ i（0 .. $＃{$ attrs {field}}）的for语句，但是$ row和$ col实际上只是表示矩阵大小的整数，因此sizeof运算符on然后返回-1。不过，您对<= vs <的评论很有意义。
\ $ \ endgroup \ $
–亨特·麦克米伦
2014年1月3日在16:07
#4 楼
我看到以下三行：my $self = shift;
my ($self) = @_;
my ($self, $rainfall) = @_;
如果选择一种样式并坚持使用，通常会更好。将第一行和第三行混合在同一程序中可能是有意义的，但前两行不应共存。我会使用第二个和第三个版本，但是如果您喜欢第一个和第二个版本，则可以使用以下版本：
my $self = shift;
my $rainfall = shift;
稍长一些，但是使代码一致。
Perl有很多做事的方法（TIMTOWTDI）。但是，如果您可以在任何给定程序（BSCINABTE）中选择仅一种方式进行操作，它仍然会很有帮助。
类似地，在以下代码中：
sub x {
return shift->{x};
}
值得思考正在发生的事情：
sub x {
my $self = shift @_;
return $self->{x};
}
希望您知道前者是后者的简写，但请考虑下一个维护您代码的人。如果这是该人第一次使用Perl，该怎么办？处于这种情况的人们将看到您的代码，并认为
shift是Perl类中的某种特殊变量名（一旦他们意识到在类中未定义它）。这样的人如何从那里到达后者？ shift是Perl的内置函数，默认为@_变量。在这种情况下，将@_设置为x函数的参数，并将对象作为第一个参数。内置的shift将数组作为第一个参数，删除第一个条目，然后返回该条目。然后，您可以使用->运算符取消引用结果，并使用哈希查找获取x键的值（因为类通常是基于Perl中的哈希构建的）。 另外，
x似乎是一个令人困惑的函数名称。我会发现get_x甚至get_x_coordinate更容易阅读和理解。 如果我是评估您的面试代码的人，那么我会给出编写干净，一致，易读的代码的要点。花一些额外的时间使代码漂亮通常是值得的。我大部分的工作时间都花在维护现有代码上，而不是编写新代码上。正确编写原始代码很重要。我不太在乎。最重要的是，它应该便于我调试和修改。那就是大多数时间。如果您节省了十五分钟的代码编写时间，但是我花了十五个小时试图使其正常工作，那么这不是一个很好的折衷方案。
和往常一样，其他审阅者可能会有所不同。他们要求您在截止日期之前编写大量代码的事实，可能表明他们的工作重点与我不同。
评论
您介意用伪代码描述该算法吗？这个问题看起来确实很有趣，但是我对Perl语法不再很熟悉。@Josay当然，我在上面以不太Perly的方式概述了基本算法。
给了多少时间来解决任务？
@mpapec我认为在采访中分配了100分钟，我无法按时完成。这是我第二次在大约1个小时内完成。
您是否确定算法在O（区域）中运行？我的评论不是风格而是方法。替代解决方案的建议是否可以作为此处的主题答案？