Это проблема в Интернете, заданная Palantir Technologies в своих интервью .

У группы фермеров есть некоторые данные по высоте, и мы собираемся помочь им понять, как ливень течет по их сельхозугодьям. Мы представим землю в виде двумерного массива высот и будем использовать следующую модель, основанную на идее, что вода течет вниз:

Если четыре соседние ячейки имеют большую высоту, мы называем эту ячейку стоком; вода собирается в раковинах. В противном случае вода будет поступать в соседнюю ячейку с наименьшей высотой. Если ячейка не является приемником, вы можете предположить, что у нее есть уникальный младший сосед, и что этот сосед будет ниже ячейки.

Считается, что клетки, которые попадают в одну и ту же раковину - прямо или косвенно - являются частью одного и того же бассейна.

Ваша задача состоит в том, чтобы разделить карту на бассейны. В частности, учитывая карту высот, ваш код должен разбить карту на бассейны и вывести размеры бассейнов в порядке убывания.

Предположим, карты высот являются квадратными. Ввод начнется со строки с одним целым числом, S, высотой (и шириной) карты. Каждая из следующих S строк будет содержать строку карты, каждая с S целыми числами - отметками S ячеек в строке. У некоторых фермеров есть небольшие земельные участки, такие как примеры ниже, а у некоторых есть большие участки. Тем не менее, ни в коем случае фермер не будет иметь участок земли больше, чем S = 5000.

Ваш код должен выводить разделенный пробелами список размеров бассейна в порядке убывания. (Конечные пробелы игнорируются.)

Несколько примеров ниже.

Входные данные:

3
1 5 2
2 4 7
3 6 9 

Выход: 7 2

Бассейны, помеченные буквами A и B:

A A B
A A B
A A A 

Входные данные:

1
10

Выход: 1

В этом случае есть только один бассейн.

Входные данные:

5
1 0 2 5 8
2 3 4 7 9
3 5 7 8 9
1 2 5 4 2
3 3 5 2 1 

Выход: 11 7 7

Бассейны, обозначенные буквами A, B и C:

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 

Входные данные:

4
0 2 1 3
2 1 0 4
3 3 3 3
5 5 2 1 

Выход: 7 5 4

Бассейны, обозначенные буквами A, B и C:

A A B B
A B B B
A B B C
A C C C

Mathematica

Список размеров бассейна может быть получен

WatershedComponents[
 Image[Rest@ImportString[m,"Table"]] // ImageAdjust,
 CornerNeighbors -> False,
 Method -> "Basins"
 ] // Reverse@Sort@Part[Tally[Flatten@#], All, 2] &

где m заданные входные данные. Чтобы отобразить матрицу, аналогичную приведенной в вопросе, можно заменить // Reverse@Sort@Part[Tally[Flatten@#], All, 2] &на /. {1 -> "A", 2 -> "B", 3 -> "C"} // MatrixFormили вместо нее можно отобразить ее в виде изображения //ImageAdjust//Image.

JavaScript - 673 707 730 751

e=[],g=[],h=[],m=[],q=[];function r(){a=s,b=t;function d(d,A){n=a+d,p=b+A;c>e[n][p]&&(u=!1,v>e[n][p]&&(v=e[n][p],w=n,k=p))}c=e[a][b],u=!0,v=c,w=a,k=b;0!=a&&d(-1,0);a!=l&&d(1,0);0!=b&&d(0,-1);b!=l&&d(0,1);g[a][b]=w;h[a][b]=k;return u}function x(a,b,d){function c(a,b,c,k){g[a+b][c+k]==a&&h[a+b][c+k]==c&&(d=x(a+b,c+k,d))}d++;0!=a&&c(a,-1,b,0);a!=l&&c(a,1,b,0);0!=b&&c(a,0,b,-1);b!=l&&c(a,0,b,1);return d}y=$EXEC('cat "'+$ARG[0]+'"').split("\n");l=y[0]-1;for(z=-1;z++<l;)e[z]=y[z+1].split(" "),g[z]=[],h[z]=[];for(s=-1;s++<l;)for(t=-1;t++<l;)r()&&m.push([s,t]);for(z=m.length-1;0<=z;--z)s=m[z][0],t=m[z][1],q.push(x(s,t,0));print(q.sort(function(a,b){return b-a}).join(" "));

Результаты теста (с использованием Nashorn):

$ for i in A B C D; do jjs -scripting minlm.js -- "test$i"; done
7 2
1
11 7 7
7 5 4
$

Вероятно, будут проблемы со стеком для карт размером 5000 (но это детали реализации :).

Неограниченный источник во всем его бесполезности:

// lm.js - find the local minima


//  Globalization of variables.

/*
    The map is a 2 dimensional array. Indices for the elements map as:

    [0,0] ... [0,n]
    ...
    [n,0] ... [n,n]

Each element of the array is a structure. The structure for each element is:

Item    Purpose         Range       Comment
----    -------         -----       -------
h   Height of cell      integers
s   Is it a sink?       boolean
x   X of downhill cell  (0..maxIndex)   if s is true, x&y point to self
y   Y of downhill cell  (0..maxIndex)

Debugging only:
b   Basin name      ('A'..'A'+# of basins)

Use a separate array-of-arrays for each structure item. The index range is
0..maxIndex.
*/
var height = [];
var sink = [];
var downhillX = [];
var downhillY = [];
//var basin = [];
var maxIndex;

//  A list of sinks in the map. Each element is an array of [ x, y ], where
// both x & y are in the range 0..maxIndex.
var basinList = [];

//  An unordered list of basin sizes.
var basinSize = [];


//  Functions.

function isSink(x,y) {
    var myHeight = height[x][y];
    var imaSink = true;
    var bestDownhillHeight = myHeight;
    var bestDownhillX = x;
    var bestDownhillY = y;

    /*
        Visit the neighbors. If this cell is the lowest, then it's the
    sink. If not, find the steepest downhill direction.

        This would be the place to test the assumption that "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." But right now, we'll
    take that on faith.
    */
    function visit(deltaX,deltaY) {
        var neighborX = x+deltaX;
        var neighborY = y+deltaY;
        if (myHeight > height[neighborX][neighborY]) {
            imaSink = false;
            if (bestDownhillHeight > height[neighborX][neighborY]) {
                bestDownhillHeight = height[neighborX][neighborY];
                bestDownhillX = neighborX;
                bestDownhillY = neighborY;
            }
        }
    }
    if (x !== 0) {
        // upwards neighbor exists
        visit(-1,0);
    }
    if (x !== maxIndex) {
        // downwards neighbor exists
    visit(1,0);
    }
    if (y !== 0) {
        // left-hand neighbor exists
        visit(0,-1);
    }
    if (y !== maxIndex) {
        // right-hand neighbor exists
        visit(0,1);
    }

    downhillX[x][y] = bestDownhillX;
    downhillY[x][y] = bestDownhillY;
    return imaSink;
}

function exploreBasin(x,y,currentSize) {//,basinName) {
    //  This cell is in the basin.
    //basin[x][y] = basinName;
    currentSize++;

    /*
        Visit all neighbors that have this cell as the best downhill
    path and add them to the basin.
    */
    function visit(x,deltaX,y,deltaY) {
        if ((downhillX[x+deltaX][y+deltaY] === x) && (downhillY[x+deltaX][y+deltaY] === y)) {
            currentSize = exploreBasin(x+deltaX,y+deltaY,currentSize); //,basinName);
        }
        return 0;
    }
    if (x !== 0) {
        // upwards neighbor exists
        visit(x,-1,y,0);
    }
    if (x !== maxIndex) {
        // downwards neighbor exists
        visit(x,1,y,0);
    }
    if (y !== 0) {
        // left-hand neighbor exists
        visit(x,0,y,-1);
    }
    if (y !== maxIndex) {
        // right-hand neighbor exists
        visit(x,0,y,1);
    }

    return currentSize;
}

//  Read map from file (1st argument).
var lines = $EXEC('cat "' + $ARG[0] + '"').split('\n');
maxIndex = lines.shift() - 1;
for (var i = 0; i<=maxIndex; i++) {
    height[i] = lines.shift().split(' ');
    //  Create all other 2D arrays.
    sink[i] = [];
    downhillX[i] = [];
    downhillY[i] = [];
    //basin[i] = [];
}

//  Everyone decides if they are a sink. Create list of sinks (i.e. roots).
for (var x=0; x<=maxIndex; x++) {
    for (var y=0; y<=maxIndex; y++) {
        if (sink[x][y] = isSink(x,y)) {
            //  This node is a root (AKA sink).
            basinList.push([x,y]);
        }
    }
}
//for (var i = 0; i<=maxIndex; i++) { print(sink[i]); }

//  Each root explores it's basin.
//var basinName = 'A';
for (var i=basinList.length-1; i>=0; --i) { // i-- makes Closure Compiler sad
    var x = basinList[i][0];
    var y = basinList[i][1];
    basinSize.push(exploreBasin(x,y,0)); //,basinName));
    //basinName = String.fromCharCode(basinName.charCodeAt() + 1);
}
//for (var i = 0; i<=maxIndex; i++) { print(basin[i]); }

//  Done.
print(basinSize.sort(function(a, b){return b-a}).join(' '));

Я добился лучших результатов минимизации, разбив объекты-элементы на отдельные массивы, повсеместно глобализируя и используя побочные эффекты. NSFW.

Эффекты минимизации кода:

• 4537 байт, не унифицировано
• 1180 байт, упаковщик
• 855 байт, упаковщик + ручная оптимизация (глобальные имена из 1 символа)
• 751 байт, Google Closure Compiler с ADVANCED_OPTIMIZATIONS (примечание: в качестве мертвого кода он исключил рудиментарное «возвращение 0»)
• 730 байт, безрассудная оптимизация рук (я не изменяю unminified source, поэтому NSFW)
• 707 байт, более безрассудная ручная оптимизация (уберите все ссылки на сток []);
• 673 байта, убрать все "var", сбросить флаг Nashorn -strict

Я мог бы достичь почти 700 байтов, не редактируя свернутый код, если бы я хотел изменить исходный код. Но я не сделал, потому что я думаю, что оставление этого как есть дает интересную точку зрения с начальной точки.

Python: 276 306 365 байт

Это моя первая попытка игры в гольф. Предложения приветствуются!

редактировать: импорт и закрытие файлов занимает слишком много символов! То же самое касается хранения файлов в переменных и понимания вложенного списка.

t=map(int,open('a').read().split());n=t.pop(0);q=n*n;r,b,u=range(q),[1]*q,1
while u!=0:
    u=0
    for j in r:
        d=min((t[x],x)for x in [j,j-1,j+1,j-n,j+n]if int(abs(j/n-x/n))+abs(j%n-x%n)<=1 and x in r)[1]
        if j-d:u|=b[j];b[d]+=b[j];b[j]=0
for x in sorted(b)[::-1]:print x or '',

полностью прокомментировано (2130 байт ...)

from math import floor
with open('a') as f:
    l = f.read()
    terrain = map(int,l.split()) # read in all the numbers into an array (treating the 2D array as flattened 1D)
    n = terrain.pop(0) # pop the first value: the size of the input
    valid_indices = range(n*n) # 0..(n*n)-1 are the valid indices of this grid
    water=[1]*(n*n) # start with 1 unit of water at each grid space. it will trickle down and sum in the basins.
    updates=1 # keep track of whether each iteration included an update

    # helper functions
    def dist(i,j):
        # returns the manhattan (L1) distance between two indices
        row_dist = abs(floor(j/n) - floor(i/n))
        col_dist = abs(j % n - i % n)
        return row_dist + col_dist

    def neighbors(j):
        # returns j plus up to 4 valid neighbor indices
        possible = [j,j-1,j+1,j-n,j+n]
        # validity criteria: neighbor must be in valid_indices, and it must be one space away from j
        return [x for x in possible if dist(x,j)<=1 and x in valid_indices]

    def down(j):
        # returns j iff j is a sink, otherwise the minimum neighbor of j
        # (works by constructing tuples of (value, index) which are min'd
        # by their value, then the [1] at the end returns its index)
        return min((terrain[i],i) for i in neighbors(j))[1]

    while updates!=0: # break when there are no further updates
        updates=0 # reset the update count for this iteration
        for j in valid_indices: # for each grid space, shift its water 
            d =down(j)
            if j!=d: # only do flow if j is not a sink
                updates += water[j] # count update (water[j] is zero for all non-sinks when the sinks are full!)
                water[d] += water[j] # move all of j's water into the next lowest spot
                water[j] = 0 # indicate that all water has flown out of j
    # at this point, `water` is zeros everywhere but the sinks.
    # the sinks have a value equal to the size of their watershed.
    # so, sorting `water` and printing nonzero answers gives us the result we want!
    water = sorted(water)[::-1] # [::-1] reverses the array (high to low)
    nonzero_water = [w for w in water if w] # 0 evaulates to false.
    print " ".join([str(w) for w in nonzero_water]) # format as a space-separated list

JavaScript (ECMAScript 6) - 226 символов

s=S.split(/\s/);n=s.shift(k=[]);u=k.a;t=s.map((v,i)=>[v,i,1]);t.slice().sort(X=(a,b)=>a[0]-b[0]).reverse().map(v=>{i=v[1];p=[v,i%n?t[i-1]:u,t[i-n],(i+1)%n?t[i+1]:u,t[+n+i]].sort(X)[0];p==v?k.push(v[2]):p[2]+=v[2]});k.join(' ')

объяснение

s=S.split(/\s/);                  // split S into an array using whitespace as the boundary.
n=s.shift();                      // remove the grid size from s and put it into n.
k=[];                             // an empty array to hold the position of the sinks.
u=k.a;                            // An undefined variable
t=s.map((v,i)=>[v,i,1]);          // map s to an array of:
                                  // - the elevation
                                  // - the position of this grid square
                                  // - the number of grid squares which have flowed into
                                  //      this grid square (initially 1).
X=(a,b)=>a[0]-b[0];               // A comparator function for sorting.
t.slice()                         // Take a copy of t
 .sort(X)                         // Then sort it by ascending elevation
 .reverse()                       // Reverse it to be sorted in descending order
 .map(v=>{                        // For each grid square (starting with highest elevation)
   i=v[1];                        // Get the position within the grid
   p=[v,i%n?t[i-1]:u,t[i-n],(i+1)%n?t[i+1]:u,t[+n+i]]
                                  // Create an array of the grid square and 4 adjacent
                                  //   squares (or undefined if off the edge of the grid)
     .sort(X)                     // Then sort by ascending elevation
     [0];                         // Then get the square with the lowest elevation.
   p==v                           // If the current grid square has the lowest elevation
     ?k.push(v[2])                // Then add the number of grid square which have
                                  //   flowed into it to k
     :p[2]+=v[2]});               // Else flow the current grid square into its lowest
                                  //   neighbour.
k.join(' ')                       // Output the sizes of the block with  space separation.

Предыдущая версия - 286 персонажей

s=S.split(/\s/);n=s.shift()*1;k=[];u=k[1];t=s.map((v,i)=>({v:v,p:i,o:[]}));for(i in t){t[p=[t[i],i%n?t[i-1]:u,t[i-n],(+i+1)%n?t[+i+1]:u,t[+i+n]].sort((a,b)=>(a.v-b.v))[0].p].o.push([i]);p==i&&k.push([i])}k.map(x=>{while(x[L="length"]<(x=[].concat(...x.map(y=>t[y].o)))[L]);return x[L]})

Предполагается, что входные данные находятся в переменной S;

объяснение

s=S.split(/\s/);                  // split S into an array using whitespace as the boundary.
n=s.shift()*1;                    // remove the grid size from s and put it into n.
k=[];                             // an empty array to hold the position of the sinks.
u=k[1];                           // Undefined
t=s.map((v,i)=>({v:v,p:i,o:[]})); // map s to an Object with attributes:
                                  // - v: the elevation
                                  // - p: the position of this grid square
                                  // - o: an array of positions of neighbours which
                                  //      flow into this grid square.
for(i in t){                      // for each grid square
  p=[t[i],i%n?t[i-1]:u,t[i-n],(+i+1)%n?t[+i+1]:u,t[+i+n]]
                                  // start with an array containing the objects 
                                  //   representing that grid square and its 4 neighbours
                                  //   (or undefined for those neighbours which are
                                  //   outside the grid)
      .sort((a,b)=>(a.v-b.v))     // then sort that array in ascending order of elevation
      [0].p                       // then get the first array element (with lowest
                                  //   elevation) and get the position of that grid square.
  t[p].o.push([i]);               // Add the position of the current grid square to the
                                  //   array of neighbours which flow into the grid square
                                  //   we've just found.
  p==i&&k.push([i])               // Finally, if the two positions are identical then
                                  //   we've found a sink so add it to the array of sinks (k)
}
k.map(x=>{                        // For each sink start with an array, x, containing the
                                  //   position of the sink.
  while(x.length<(x=[].concat(...x.map(y=>t[y].o))).length);
                                  // Compare x to the concatenation of x with all the
                                  //   positions of grid squares which flow into squares
                                  //   in x and loop until it stops growing.
  return x.length                 // Then return the number of grid squares.
})

Тестовое задание

S="3\n1 5 2\n2 4 7\n3 6 9";
s=S.split(/\s/);n=s.shift()*1;k=[];u=k[1];t=s.map((v,i)=>({v:v,p:i,o:[]}));for(i in t){t[p=[t[i],i%n?t[i-1]:u,t[i-n],(+i+1)%n?t[+i+1]:u,t[+i+n]].sort((a,b)=>(a.v-b.v))[0].p].o.push([i]);p==i&&k.push([i])}k.map(x=>{while(x[L="length"]<(x=[].concat(...x.map(y=>t[y].o)))[L]);return x[L]})

Выходы: [7, 2]

S="5\n1 0 2 5 8\n2 3 4 7 9\n3 5 7 8 9\n1 2 5 4 2\n3 3 5 2 1"
s=S.split(/\s/);n=s.shift()*1;k=[];u=k[1];t=s.map((v,i)=>({v:v,p:i,o:[]}));for(i in t){t[p=[t[i],i%n?t[i-1]:u,t[i-n],(+i+1)%n?t[+i+1]:u,t[+i+n]].sort((a,b)=>(a.v-b.v))[0].p].o.push([i]);p==i&&k.push([i])}k.map(x=>{while(x[L="length"]<(x=[].concat(...x.map(y=>t[y].o)))[L]);return x[L]})

Выходы: [11, 7, 7]

S="4\n0 2 1 3\n2 1 0 4\n3 3 3 3\n5 5 2 1"
s=S.split(/\s/);n=s.shift()*1;k=[];u=k[1];t=s.map((v,i)=>({v:v,p:i,o:[]}));for(i in t){t[p=[t[i],i%n?t[i-1]:u,t[i-n],(+i+1)%n?t[+i+1]:u,t[+i+n]].sort((a,b)=>(a.v-b.v))[0].p].o.push([i]);p==i&&k.push([i])}k.map(x=>{while(x[L="length"]<(x=[].concat(...x.map(y=>t[y].o)))[L]);return x[L]})

Выходы: [5, 7, 4]

Юлия, 315

function f(a,i,j)
    z=size(a,1)
    n=filter((x)->0<x[1]<=z&&0<x[2]<=z,[(i+1,j),(i-1,j),(i,j-1),(i,j+1)])
    v=[a[b...] for b in n]
    all(v.>a[i,j]) && (return i,j)
    f(a,n[indmin(v)]...)
end
p(a)=prod(["$n " for n=(b=[f(a,i,j) for i=1:size(a,1),j=1:size(a,2)];sort([sum(b.==s) for s=unique(b)],rev=true))])

Просто рекурсивная функция, которая либо определяет текущую ячейку, является приемником, либо находит сток, а затем вызывает ее для каждого набора индексов. Не удосужился сделать входную часть, так как я все равно не собирался выигрывать, и эта часть не веселая.

Хаскелл, 271 286

import Data.List
m=map
q[i,j]=[-1..1]>>= \d->[[i+d,j],[i,j+d]]
x%z=m(\i->snd.fst.minimum.filter((`elem`q i).snd)$zip(zip z[0..])x)x
g(n:z)=iterate(\v->m(v!!)v)(sequence[[1..n],[1..n]]%z)!!(n*n)
main=interact$unwords.m show.reverse.sort.m length.group.sort.g.m read.words

Может быть, еще какой-то код для игры в гольф здесь.

& runhaskell 19188-Partition.hs <<INPUT
> 5
> 1 0 2 5 8
> 2 3 4 7 9
> 3 5 7 8 9
> 1 2 5 4 2
> 3 3 5 2 1
INPUT
11 7 7

объяснение

Основная идея: для каждой ячейки (i, j) найдите самую нижнюю ячейку в «окрестности». Это дает график [ (I, J) → (mi, mj) ]. Если ячейка является самой нижней ячейкой, то (i, j) == (mi, mj) .

Этот график может быть повторен: для каждого a → b в графе замените его на a → c, где b → c находится в графе. Когда эта итерация больше не приводит к изменениям, то каждая ячейка в графе указывает на самую нижнюю ячейку, в которую она будет перемещаться.

Для игры в гольф было сделано несколько изменений: во-первых, координаты представлены в виде списка длиной 2, а не пары. Во-вторых, как только соседи найдены, ячейки представляются своим индексом в виде линейного массива ячеек, а не 2D-координат. В-третьих, поскольку существует n * n ячеек, после n * n итераций граф должен быть устойчивым.

Ungolf'd

type Altitude = Int     -- altitude of a cell

type Coord = Int        -- single axis coordinate: 1..n
type Coords = [Coord]   -- 2D location, a pair of Coord
    -- (Int,Int) would be much more natural, but Coords are syntehsized
    -- later using sequence, which produces lists

type Index = Int        -- cell index
type Graph = [Index]    -- for each cell, the index of a lower cell it flows to


neighborhood :: Coords -> [Coords]                              -- golf'd as q
neighborhood [i,j] = concatMap (\d -> [[i+d,j], [i,j+d]]) [-1..1]
    -- computes [i-1,j] [i,j-1] [i,j] [i+1,j] [i,j+1]
    -- [i,j] is returned twice, but that won't matter for our purposes

flowsTo :: [Coords] -> [Altitude] -> Graph                      -- golf'd as (%)
flowsTo cs vs = map lowIndex cs
  where
    lowIndex is = snd . fst                          -- take just the Index of
                  . minimum                          -- the lowest of
                  . filter (inNeighborhood is . snd) -- those with coords nearby
                  $ gv                               -- from the data

    inNeighborhood :: Coords -> Coords -> Bool
    inNeighborhood is ds = ds `elem` neighborhood is

    gv :: [((Altitude, Index), Coords)]
        -- the altitudes paired with their index and coordinates
    gv = zip (zip vs [0..]) cs


flowInput :: [Int] -> Graph                                     -- golf'd as g
flowInput (size:vs) = iterate step (flowsTo coords vs) !! (size * size)
  where
    coords = sequence [[1..size],[1..size]]
        -- generates [1,1], [1,2] ... [size,size]

    step :: Graph -> Graph
    step v = map (v!!) v
        -- follow each arc one step

main' :: IO ()
main' = interact $
            unwords . map show      -- counts a single line of text
            . reverse . sort        -- counts from hi to lo
            . map length            -- for each common group, get the count
            . group . sort          -- order cells by common final cell index
            . flowInput             -- compute the final cell index graph
            . map read . words      -- all input as a list of Int

Руби, 216

r=[]
M=gets('').split.map &:to_i
N=M.shift
g=M.map{1}
M.sort.reverse.map{|w|t=[c=M.index(w),c%N<0?c:c-1,c%N<N-1?c+1:c,c+N,c-N].min_by{|y|M[y]&&y>=0?M[y]:M.max}
M[c]+=1
t!=c ?g[t]+=g[c]:r<<g[c]}
$><<r.sort.reverse*' '

Это немного другой подход, вызывая «поток» только для каждого квадрата один раз (производительность зависит от производительности Array :: index). Он идет от самой высокой отметки к самой низкой, опустошая по одной ячейке за раз в своего нижнего соседа и помечая ячейку как выполненную (добавляя 1 к отметке), когда это будет сделано.

Комментарии и интервалы:

results=[]
ELEVATIONS = gets('').split.map &:to_i  # ELEVATIONS is the input map
MAP_SIZE = ELEVATIONS.shift             # MAP_SIZE is the first line of input
watershed_size = ELEVATIONS.map{1}      # watershed_size is the size of the watershed of each cell

ELEVATIONS.sort.reverse.map { |water_level| 
    # target_index is where the water flows to.  It's the minimum elevation of the (up to) 5 cells:
    target_index = [
        current_index = ELEVATIONS.index(water_level),                              # this cell
        (current_index % MAP_SIZE) < 0           ? current_index : current_index-1, # left if possible
        (current_index % MAP_SIZE) >= MAP_SIZE-1 ? current_index : current_index+1, # right if possible
        current_index + MAP_SIZE,                                                   # below
        current_index - MAP_SIZE                                                    # above
    ].min_by{ |y|
        # if y is out of range, use max. Else, use ELEVATIONS[y]
        (ELEVATIONS[y] && y>=0) ? ELEVATIONS[y] : ELEVATIONS.max
    }
# done with this cell.
# increment the elevation to mark done since it no longer matters
ELEVATIONS[current_index] += 1

# if this is not a sink
(target_index != current_index) ? 
    # add my watershed size to the target's
    watershed_size[target_index] += watershed_size[current_index] 
    # else, push my watershed size onto results
    : results << watershed_size[current_index]}

Changelog:

216 - лучший способ отменить выбор внеклассных индексов

221 - получается, «11» предшествует «2» ... вернуться к to_i, но сэкономить место на нашемgets эс.

224 - Зачем sвообще декларировать ? И each=>map

229 - массивный гольф - сначала рассортируйте возвышения s(и, таким образом, отбросьте whileпредложение), используйте min_byвместо sort_by{...}[0], не беспокойтесь to_iо возвышениях, используйте flat_mapи сокращайтеselect{} блок

271 - перенес размер водораздела в новый массив и использовал sort_by

315 - переместил результаты в массив, который дал все виды преимуществ, и сократил список соседних индексов. также получил один символ в индексе лямбда.

355 - первый коммит

Питон - 470 447 445 393 392 378 376 375 374 369 байт

Я не могу остановить себя!

Не выигрышное решение, но мне было очень весело создавать его. Эта версия не предполагает, что ввод будет храниться где-либо, а вместо этого читает его из стандартного ввода. Максимальная глубина рекурсии = наибольшее расстояние от точки до ее раковины.

def f(x,m=[],d=[],s=[]):
 n=[e[a]if b else 99for a,b in(x-1,x%z),(x+1,x%z<z-1),(x-z,x/z),(x+z,x/z<z-1)];t=min(n)
 if t<e[x]:r=f(x+(-1,1,-z,z)[n.index(t)])[0];s[r]+=x not in m;m+=[x]
 else:c=x not in d;d+=[x]*c;r=d.index(x);s+=[1]*c
 return r,s
z,e=input(),[]
exec'e+=map(int,raw_input().split());'*z
for x in range(z*z):s=f(x)[1]
print' '.join(map(str,sorted(s)[::-1]))

У меня нет времени, чтобы объяснить это сегодня, но вот незакрашенный код:

На самом деле это сильно отличается от исходного кода. Я читаю S строк из stdin, split, map to ints и сглаживаю списки, чтобы получить сглаженное поле. Затем я перебираю все плитки (позвольте мне называть их плитками) один раз. Функция потока проверяет соседние листы и выбирает тот, у которого наименьшее значение. Если он меньше, чем значение текущей плитки, перейдите к нему и выполните повторный поиск. Если нет, то текущая плитка является раковиной, и создается новый бассейн. Возвращаемое значение рекурсии - это идентификатор бассейна.

# --- ORIGINAL SOURCE ---

# lowest neighboring cell = unique and next
# neihboring cells all higher = sink and end

basinm = [] # list of the used tiles
basins = {} # list of basin sizes
basinf = [] # tuples of basin sinks
field = []  # 2d-list representing the elevation map
size = 0

def flow(x, y):
    global basinf, basinm
    print "Coordinate: ", x, y
    nearby = []
    nearby += [field[y][x-1] if x > 0 else 99]
    nearby += [field[y][x+1] if x < size-1 else 99]
    nearby += [field[y-1][x] if y > 0 else 99]
    nearby += [field[y+1][x] if y < size-1 else 99]
    print nearby
    next = min(nearby)
    if next < field[y][x]:
        i = nearby.index(next)
        r = flow(x+(-1,1,0,0)[i], y+(0,0,-1,1)[i])
        if (x,y) not in basinm:
            basins[r] += 1
            basinm += [(x,y)]
    else:
        c = (x,y) not in basinf
        if c:
            basinf += [(x,y)]
        r = basinf.index((x,y))
        if c: basins[r] = 1
    return r

size = input()
field = [map(int,raw_input().split()) for _ in range(size)]
print field
for y in range(size):
    for x in range(size):
        flow(x, y)
print
print ' '.join(map(str,sorted(basins.values(),reverse=1)))

JavaScript (ES6) 190 203

редактировать немного больше ES6ish (1 год спустя ...)

Определить функцию с входными строками в виде строки, включая переводы строк, вернуть вывод в виде строки с конечными пробелами

F=l=>{[s,...m]=l.split(/\s+/);for(j=t=[];k=j<s*s;t[i]=-~t[i])for(i=j++;k;i+=k)k=r=0,[for(z of[-s,+s,i%s?-1:+s,(i+1)%s?1:+s])(q=m[z+i]-m[i])<r&&(k=z,r=q)];return t.sort((a,b)=>b-a).join(' ')}

// Less golfed
U=l=>{
      [s,...m] = l.split(/\s+/);
      for (j=t=[]; k=j<s*s; t[i]=-~t[i])
        for(i=j++; k; i+=k)
          k=r=0,
          [for(z of [-s,+s,i%s?-1:+s,(i+1)%s?1:+s]) (q=m[z+i]-m[i]) < r && (k=z,r=q)];
      return t.sort((a,b)=>b-a).join(' ')
    }

// TEST    
out=x=>O.innerHTML += x + '\n';

out(F('5\n1 0 2 5 8\n 2 3 4 7 9\n 3 5 7 8 9\n 1 2 5 4 2\n 3 3 5 2 1'))// "11 7 7"

out(F('4\n0 2 1 3\n2 1 0 4\n3 3 3 3\n5 5 2 1')) //"7 5 4"

<pre id=O></pre>

Perl 6, 419 404

Новые строки добавлены для ясности. Вы можете безопасно удалить их.

my \d=$*IN.lines[0];my @a=$*IN.lines.map(*.trim.split(" "));my @b;my $i=0;my $j=0;
for @a {for @$_ {my $c=$_;my $p=$i;my $q=$j;my &y={@a[$p+$_[0]][$q+$_[1]]//Inf};
loop {my @n=(0,1),(1,0);push @n,(-1,0) if $p;push @n,(0,-1) if $q;my \o=@n.sort(
&y)[0];my \h=y(o);last if h>$c;$c=h;$p+=o[0];$q+=o[1]};@b[$i][$j]=($p,$q);++$j};
$j=0;++$i};say join " ",bag(@b.map(*.flat).flat.map(~*)).values.sort: {$^b <=>$^a}

Старое решение:

my \d=$*IN.lines[0];my @a=$*IN.lines.map(*.trim.split(" "));my @b;my $i=0;my $j=0;
for @a {for @$_ {
my $c=$_;my $p=$i;my $q=$j;
loop {my @n=(0,1),(1,0);@n.push: (-1,0) if $p;@n.push: (0,-1) if $q;
my \o=@n.sort({@a[$p+$_[0]][$q+$_[1]]//Inf})[0];
my \h=@a[$p+o[0]][$q+o[1]];last if h>$c;
$c=h;$p+=o[0];$q+=o[1]};@b[$i][$j]=($p,$q);++$j};$j=0;++$i};
say join " ",bag(@b.map(*.flat.flat).flat.map(~*)).values.sort: {$^b <=>$^a}

И все же меня побеждают решения Python и JavaScript.