Dies ist eine Herausforderung im Internet, die Palantir Technologies in ihren Interviews gestellt hat .

Eine Gruppe von Landwirten verfügt über einige Höhendaten, und wir werden ihnen helfen, zu verstehen, wie der Niederschlag über ihr Ackerland fließt. Wir werden das Land als eine zweidimensionale Anordnung von Höhen darstellen und das folgende Modell verwenden, basierend auf der Idee, dass Wasser bergab fließt:

Wenn die vier benachbarten Zellen einer Zelle alle eine höhere Höhe haben, bezeichnen wir diese Zelle als Senke. wasser sammelt sich in waschbecken. Andernfalls fließt Wasser in die benachbarte Zelle mit der niedrigsten Höhe. Wenn eine Zelle keine Senke ist, können Sie davon ausgehen, dass sie einen eindeutigen niedrigsten Nachbarn hat und dieser Nachbar niedriger als die Zelle ist.

Zellen, die direkt oder indirekt in dasselbe Waschbecken abfließen, werden als Teil desselben Beckens bezeichnet.

Ihre Herausforderung besteht darin, die Karte in Becken zu unterteilen. Insbesondere sollte Ihr Code bei einer Karte mit Höhenangaben die Karte in Becken unterteilen und die Größe der Becken in absteigender Reihenfolge ausgeben.

Angenommen, die Höhenkarten sind quadratisch. Die Eingabe beginnt mit einer Zeile mit einer ganzen Zahl, S, der Höhe (und Breite) der Karte. Die nächsten S-Zeilen enthalten jeweils eine Zeile der Karte mit S-ganzen Zahlen - den Höhen der S-Zellen in der Zeile. Einige Landwirte haben kleine Grundstücke, wie in den folgenden Beispielen gezeigt, während andere größere Grundstücke haben. Ein Bauer wird jedoch in keinem Fall ein Grundstück haben, das größer als S = 5000 ist.

Ihr Code sollte eine durch Leerzeichen getrennte Liste der Beckengrößen in absteigender Reihenfolge ausgeben. (Nachgestellte Leerzeichen werden ignoriert.)

Einige Beispiele finden Sie unten.

Eingang:

3
1 5 2
2 4 7
3 6 9 

Ausgabe: 7 2

Die mit A und B gekennzeichneten Becken sind:

A A B
A A B
A A A 

Eingang:

1
10

Ausgabe: 1

In diesem Fall gibt es nur ein Becken.

Eingang:

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 

Ausgabe: 11 7 7

Die mit A, B und C gekennzeichneten Becken sind:

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 

Eingang:

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

Ausgabe: 7 5 4

Die mit A, B und C gekennzeichneten Becken sind:

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

Mathematica

Die Beckengrößenliste erhalten Sie von

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

Wo msind die angegebenen Eingabedaten? Zur Anzeige kann eine Matrix wie die , die in der Frage ersetzen // Reverse@Sort@Part[Tally[Flatten@#], All, 2] &mit /. {1 -> "A", 2 -> "B", 3 -> "C"} // MatrixFormoder man kann es als Bild angezeigt werden, statt unter Verwendung //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(" "));

Testergebnisse (mit 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
$

Es würde wahrscheinlich Stapelprobleme für Karten der Größe 5000 geben (aber das ist ein Implementierungsdetail :).

Die ungeklärte Quelle in ihrer ganzen Flüchtigkeit:

// 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(' '));

Ich habe bessere Ergebnisse bei der Minimierung erzielt, indem ich die Elementobjekte in separate Arrays aufgeteilt, überall globalisiert und Nebenwirkungen berücksichtigt habe. NSFW.

Die Auswirkungen der Code-Minimierung:

• 4537 Bytes, ungekürzt
• 1180 Bytes, Packer
• 855 Bytes, Packer + Hand Optimierungen (1 Zeichen globale Namen)
• 751 bytes, Google Closure Compiler mit ADVANCED_OPTIMIZATIONS
• 730 Bytes, rücksichtslose Handoptimierung (Ich ändere nicht die nicht minimierte Quelle, also NSFW)
• 707 Bytes, mehr rücksichtslose Handoptimierung (alle Verweise auf sink [] entfernen);
• 673 Bytes, entferne alle "var" s und lasse das Nashorn-strikte Flag fallen

Ich hätte fast 700 Bytes erreichen können, ohne den minimierten Code zu bearbeiten, wenn ich gewillt gewesen wäre, die ursprüngliche Quelle zu ändern. Aber ich habe es nicht getan, weil ich denke, es so zu belassen, wie es ist, gibt einen interessanten Blick vom Ausgangspunkt.

Python: 276 306 365 Bytes

Dies ist mein erster Golfversuch. Vorschläge werden geschätzt!

Bearbeiten: Importieren und Schließen von Dateien dauert zu viele Zeichen! Das Gleiche gilt für das Speichern von Dateien in Variablen und das Verstehen von verschachtelten Listen.

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 '',

vollständig kommentiert (2130 Bytes ...)

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 Zeichen

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(' ')

Erläuterung

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.

Vorherige Version - 286 Zeichen

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]})

Es wird davon ausgegangen, dass sich die Eingabe in einer Variablen befindet S.

Erläuterung

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.
})

Prüfung

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]})

Ausgänge: [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]})

Ausgänge: [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]})

Ausgänge: [5, 7, 4]

Julia, 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))])

Nur eine rekursive Funktion, die entweder die aktuelle Zelle bestimmt, ist eine Senke oder findet den Drain. Rufen Sie dies dann für jeden Satz von Indizes auf. Ich habe mich nicht darum gekümmert, den Input-Teil zu machen, da ich sowieso nicht gewinnen würde und dieser Teil keinen Spaß macht.

Haskell, 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

Könnte noch ein Code sein, um hier Golf zu spielen.

& 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

Erläuterung

Grundidee: Finden Sie für jede Zelle (i, j) die unterste Zelle in der "Nachbarschaft". Dies ergibt einen Graphen [ (i, j) → (mi, mj) ]. Wenn eine Zelle die unterste Zelle selbst ist, dann ist (i, j) == (mi, mj) .

Dieses Diagramm kann iteriert werden: Ersetzen Sie es für jedes a → b im Diagramm durch a → c, wobei b → c im Diagramm steht. Wenn diese Iteration keine Änderungen mehr ergibt, zeigt jede Zelle im Diagramm auf die unterste Zelle, zu der sie fließt.

Um dies zu erreichen, wurden einige Änderungen vorgenommen: Erstens werden Koordinaten als Liste der Länge 2 und nicht als Paar dargestellt. Zweitens, sobald die Nachbarn gefunden wurden, werden die Zellen durch ihren Index in einem linearen Array der Zellen dargestellt, nicht in 2D-Koordinaten. Drittens muss der Graph, da es n * n Zellen gibt, nach n * n Iterationen stabil sein.

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

Rubin, 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*' '

Es ist ein etwas anderer Ansatz, bei dem nur einmal "flow" für jedes Quadrat aufgerufen wird (die Leistung hängt von der Leistung von Array :: index ab). Es geht von der höchsten zur niedrigsten Erhebung, entleert jeweils eine Zelle in den untersten Nachbarn und markiert die erledigte Zelle (indem 1 zur Erhebung hinzugefügt wird), wenn sie erledigt ist.

Kommentiert und beabstandet:

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]}

Änderungsprotokoll:

216 - Besseres Abwählen von Out-of-Bounded-Indizes

221 - stellt sich heraus, "11" kommt vor "2" ... zurück to_i, aber sparen Sie etwas Platz auf unseren getses.

224 - Warum überhaupt deklarieren s? Und each=>map

229 - massiv Golf - Art der Erhebungen zunächst in s(und fällt dadurch die whileKlausel), verwenden Sie min_bystatt sort_by{...}[0], nicht die Mühe , to_ifür Erhebungen, Verwendung flat_mapund schrumpft select{}Block

271 - Größe der Wasserscheide in neues Array verschoben und sort_by verwendet

315 - Die Ergebnisse wurden in ein Array verschoben, das alle möglichen Vorteile bot, und die Liste der Nachbarn wurde verkürzt. gewann auch ein Zeichen im Index Lambda.

355 - Erstes Festschreiben

Python - 470 447 445 393 392 378 376 375 374 369 Bytes

Ich kann mich nicht aufhalten!

Keine gewinnbringende Lösung, aber es hat mir viel Spaß gemacht, sie zu erstellen. Diese Version setzt nicht voraus, dass die Eingabe irgendwo gespeichert wird, sondern liest sie stattdessen von stdin. Maximale Rekursionstiefe = größte Entfernung von einem Punkt zu seiner Senke.

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]))

Ich habe heute keine Zeit, es zu erklären, aber hier ist der ungolfed Code:

Es ist eigentlich ganz anders als der ursprüngliche Code. Ich lese S-Zeilen aus dem Standard, teile sie auf, ordne sie den Ints zu und drücke die Listen zusammen, um das abgeflachte Feld zu erhalten. Dann durchlaufe ich einmal alle Kacheln (ich nenne sie Kacheln). Die Flow-Funktion prüft die benachbarten Kacheln und wählt die mit dem kleinsten Wert aus. Wenn es kleiner als der Wert der aktuellen Kachel ist, gehen Sie dorthin und wiederholen Sie den Vorgang. Ist dies nicht der Fall, handelt es sich bei der aktuellen Kachel um ein Waschbecken, und es wird ein neues Becken erstellt. Der Rückgabewert der Rekursion ist die ID des Beckens.

# --- 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

Bearbeiten Ein wenig mehr ES6ish (1 Jahr später ...)

Definieren Sie eine Funktion mit Eingabezeilen als Zeichenfolge, einschließlich Zeilenumbrüchen, und geben Sie die Ausgabe als Zeichenfolge mit nachgestellten Leerzeichen zurück

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

Zeilenumbrüche zur Verdeutlichung hinzugefügt. Sie können sie sicher entfernen.

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 \[email protected](
&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}

Alte Lösung:

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 \[email protected]({@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}

Und doch werde ich von Python- und JavaScript-Lösungen geschlagen.