C'est un défi sur Internet que Palantir Technologies a demandé dans leurs interviews .

Un groupe d'agriculteurs a des données d'altitude, et nous allons les aider à comprendre comment les précipitations coulent sur leurs terres agricoles. Nous représenterons la terre comme un tableau bidimensionnel d'altitudes et utiliserons le modèle suivant, basé sur l'idée que l'eau s'écoule vers le bas:

Si les quatre cellules voisines d'une cellule ont toutes des altitudes plus élevées, nous appelons cette cellule un puits; l'eau s'accumule dans les éviers. Sinon, l'eau coulera vers la cellule voisine avec l'altitude la plus basse. Si une cellule n'est pas un puits, vous pouvez supposer qu'elle a un voisin le plus bas unique et que ce voisin sera inférieur à la cellule.

Les cellules qui s'écoulent dans le même évier - directement ou indirectement - feraient partie du même bassin.

Votre défi est de partitionner la carte en bassins. En particulier, étant donné une carte des élévations, votre code doit partitionner la carte en bassins et afficher les tailles des bassins, par ordre décroissant.

Supposons que les cartes d'élévation sont carrées. L'entrée commencera par une ligne avec un entier, S, la hauteur (et la largeur) de la carte. Les S lignes suivantes contiendront chacune une ligne de la carte, chacune avec S entiers - les élévations des S cellules de la ligne. Certains agriculteurs ont de petites parcelles de terrain comme les exemples ci-dessous, tandis que d'autres ont des parcelles plus grandes. Cependant, en aucun cas, un agriculteur ne disposera d'une parcelle de terrain supérieure à S = 5000.

Votre code doit afficher une liste des tailles de bassin séparées par des espaces, par ordre décroissant. (Les espaces de fin sont ignorés.)

Voici quelques exemples.

Contribution:

3
1 5 2
2 4 7
3 6 9 

Production: 7 2

Les bassins, étiquetés avec A et B, sont:

A A B
A A B
A A A 

Contribution:

1
10

Production: 1

Il n'y a qu'un seul bassin dans ce cas.

Contribution:

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 

Production: 11 7 7

Les bassins, étiquetés avec A, B et C, sont:

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 

Contribution:

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

Production: 7 5 4

Les bassins, étiquetés avec A, B et C, sont:

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

Mathematica

La liste des tailles de bassin peut être obtenue par

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

où msont les données d'entrée données. Pour afficher une matrice comme celles de la question, on peut remplacer // Reverse@Sort@Part[Tally[Flatten@#], All, 2] &par /. {1 -> "A", 2 -> "B", 3 -> "C"} // MatrixFormou on peut l'afficher comme une image à la place en utilisant //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(" "));

Résultats des tests (avec 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
$

Il y aurait probablement des problèmes de pile pour les cartes de taille 5000 (mais c'est un détail d'implémentation :).

La source non minimisée dans toute sa grossièreté:

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

J'ai obtenu de meilleurs résultats de minimisation en divisant les objets élément en tableaux séparés, en globalisant partout où cela était possible et en adoptant les effets secondaires. NSFW.

Les effets de la minimisation du code:

• 4537 octets, non réduit
• 1180 octets, packer
• 855 octets, optimisations packer + main (noms globaux à 1 caractère)
• 751 octets, Google Closure Compiler avec ADVANCED_OPTIMIZATIONS (NB, il a élidé un "retour 0" résiduel comme code mort)
• 730 octets, optimisation imprudente de la main (je ne change pas la source non minimisée, donc NSFW)
• 707 octets, optimisation plus imprudente de la main (supprimez toutes les références à sink []);
• 673 octets, supprimer tous les "var", supprimer l'indicateur Nashorn -strict

J'aurais pu atteindre près de 700 octets sans éditer le code minimisé si j'avais voulu modifier la source d'origine. Mais je ne l'ai pas fait car je pense que le laisser tel quel donne une vue intéressante du point de départ.

Python: 276 306 365 octets

Ceci est ma première tentative de golf. Les suggestions sont appréciées!

edit: les importations et la fermeture des fichiers prennent trop de caractères! Il en va de même pour le stockage de fichiers dans des variables et la compréhension de listes imbriquées.

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

entièrement commenté (2130 octets ...)

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 caractères

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

Explication

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.

Version précédente - 286 caractères

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

Suppose que l'entrée est dans une variable S;

Explication

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

Tester

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

Les sorties: [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]})

Les sorties: [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]})

Les sorties: [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))])

Juste une fonction récursive qui détermine que la cellule actuelle est un puits ou trouve le drain, puis appelez cela sur chaque ensemble d'indices. Je n'ai pas pris la peine de faire la partie entrée car je n'allais pas gagner de toute façon, et cette partie n'est pas amusante.

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

Peut-être encore du code à jouer ici.

& 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

Explication

Idée de base: pour chaque cellule (i, j), trouvez la cellule la plus basse du "voisinage". Cela donne un graphique [ (i, j) → (mi, mj) ]. Si une cellule est la cellule la plus basse elle-même, alors (i, j) == (mi, mj) .

Ce graphique peut être itéré: Pour chaque a → b dans le graphique, remplacez-le par a → c où b → c est dans le graphique. Lorsque cette itération ne produit plus de modifications, chaque cellule du graphique pointe vers la cellule la plus basse vers laquelle elle ira.

Pour jouer au golf, plusieurs changements ont été apportés: Premièrement, les coordonnées sont représentées comme une liste de longueur 2, plutôt que comme une paire. Deuxièmement, une fois que les voisins ont été trouvés, les cellules sont représentées par leur indice dans un tableau linéaire des cellules, et non par des coordonnées 2D. Troisièmement, comme il y a n * n cellules, après n * n itérations, le graphique doit être stable.

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

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

C'est une approche légèrement différente, qui n'appelle "flow" sur chaque carré qu'une seule fois (les performances dépendent de la performance d'Array :: index). Il va de l'élévation la plus élevée à la plus basse, vidant une cellule à la fois dans son voisin le plus bas et marquant la cellule comme terminée (en ajoutant 1 à l'élévation) lorsqu'elle est terminée.

Commenté et espacé:

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

Journal des modifications:

216 - meilleure façon de désélectionner les indices hors limites

221 - se révèle, "11" vient avant "2" ... revenir à to_i, mais économisez un peu d'espace sur notregets es.

224 - Pourquoi déclarer squand même? Et each=>map

229 - Golf massif - Triez d'abord les élévations s(et supprimez ainsi la whileclause), utilisez min_byplutôt que sort_by{...}[0], ne vous embêtez pas to_ipour les élévations, utilisez flat_mapet réduisezselect{} bloc

271 - déplacement de la taille du bassin versant dans un nouveau tableau et utilisation de sort_by

315 - déplacé les résultats vers un tableau qui offrait toutes sortes d'avantages et une liste d'index de voisin raccourcie. a également gagné un caractère dans l'indice lambda.

355 - premier commit

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

Je ne peux pas m'arrêter!

Pas une solution gagnante, mais j'ai eu beaucoup de plaisir à la créer. Cette version ne suppose pas que l'entrée soit stockée n'importe où et la lit à partir de stdin. Profondeur de récursivité maximale = distance la plus longue d'un point à son puits.

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

Je n'ai pas le temps de l'expliquer aujourd'hui, mais voici le code non golfé:

Il est en fait assez différent du code d'origine. J'ai lu les lignes S de stdin, split, mappé en pouces et aplati les listes pour obtenir le champ aplati. Ensuite, je passe en revue toutes les tuiles (permettez-moi de les appeler des tuiles) une fois. La fonction de flux vérifie les tuiles voisines et sélectionne celle avec la plus petite valeur. Si elle est plus petite que la valeur de la tuile actuelle, déplacez-vous dessus et récursivement. Sinon, la tuile actuelle est un évier et un nouveau bassin est créé. La valeur de retour de la récursivité est l'id du bassin.

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

Éditer Un peu plus ES6ish (1 an plus tard ...)

Définir une fonction avec des lignes d'entrée sous forme de chaîne, y compris les sauts de ligne, renvoyer la sortie sous forme de chaîne avec des espaces de fin

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

Ajout de nouvelles lignes pour plus de clarté. Vous pouvez les retirer en toute sécurité.

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}

Ancienne solution:

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}

Et pourtant, je suis battu par les solutions Python et JavaScript.