Tiré de Google Code Jam 2013 Qualification Round Problem B :

Alice et Bob ont une pelouse devant leur maison, en forme de rectangle de N mètre par M mètre. Chaque année, ils essaient de couper la pelouse selon un schéma intéressant. Ils coupaient avec des cisailles, ce qui prenait beaucoup de temps; mais maintenant, ils ont une nouvelle tondeuse à gazon automatique avec plusieurs réglages, et ils veulent l'essayer.

La nouvelle tondeuse à gazon a un réglage de hauteur - vous pouvez le régler à n'importe quelle hauteur h entre 1 et 100 millimètres, et il coupera toute l'herbe plus haut que h qu'il rencontre à la hauteur h. Vous l'exécutez en entrant dans la pelouse à n'importe quelle partie du bord de la pelouse; puis la tondeuse à gazon va en ligne droite, perpendiculaire au bord de la pelouse où elle est entrée, coupant l'herbe dans un andain de 1 m de large, jusqu'à ce qu'elle sorte de la pelouse de l'autre côté. La hauteur de la tondeuse à gazon ne peut être réglée que lorsqu'elle n'est pas sur la pelouse.

Alice et Bob ont un certain nombre de motifs d'herbe différents qu'ils pourraient avoir sur leur pelouse. Pour chacun d'eux, ils veulent savoir s'il est possible de couper l'herbe dans ce modèle avec leur nouvelle tondeuse à gazon. Chaque motif est décrit en spécifiant la hauteur de l'herbe sur chaque carré de 1 mx 1 m de la pelouse.

L'herbe mesure initialement 100 mm de hauteur sur toute la pelouse.

Écrivez une fonction qui prend un tableau 2D de hauteurs entières et détermine si la pelouse peut être coupée en conséquence.

Voici 100 cas de test de Google Code Jam. Les 35 premiers cas devraient passer, les autres non.

Le code le plus court gagne.

J, 15 caractères

   (-:>./"1<./>./)

Je ne m'attendais pas à cette solution courte.

Brève explication:

(input == ((max of rows of input) table with min of left and right (max in columns of input)))
(      -:          >./"1                        <./                       >./              )

Si votre fonction est 4 autre fonction comme dans la solution: (f1 f2 f3 f4)et une entrée J la calcule comme f1(input,f3(f2(input),f4(input)))ie input f1 ((f2 input) f3 (f4 input)).

APL, 15 caractères

{⍵≡(⌈/⍵)∘.⌊⌈⌿⍵}

Explication:

• ⌈⌿⍵ calcule le maximum des colonnes de rhs
• ⌈/⍵ fait de même avec les lignes
• ∘.⌊ le produit extérieur des deux précédents par rapport à la fonction minimale
• ⍵≡ compare le résultat aux rhs

Exemples:

      {⍵≡(⌈/⍵)∘.⌊⌈⌿⍵} 3 3 ⍴ 2 1 2 1 1 1 2 1 2
1

      {⍵≡(⌈/⍵)∘.⌊⌈⌿⍵} 2 3 ⍴ 2 2 2 2 1 1
0 

Python, 112 104

z=zip
y=lambda l:[[max(r)]*len(r)for r in l]
f=lambda l:l==[map(min,z(*r))for r in z(y(l),z(*y(z(*l))))]

J'ai un code python un peu plus long mais il a réussi tous les cas de test donnés lors de Google Code Jam 2013.

 a=input();io=0
 while io<a:
     io+=1;[b,c]=map(int,raw_input("").strip().split());koi=[];koi1=[]
     for i in xrange(b):
         koi.append(map(int,raw_input("").strip().split()))
    rowmax=[]
    for i in koi:
        rowmax.append(max(i))
    for i in xrange(c):
        t=[]
        for j in koi:
            t.append(j[i])
        koi1.append(t);colmax=[]
    for i in koi1:
        colmax.append(max(i))
    toi1=[]
    for i in xrange(b):
        s=[]
        for j in xrange(c):
           s.append(min(colmax[j],rowmax[i]))
        toi1.append(s)
     if toi1==koi:
        print "Case #%d:"%io,"YES"
     else:
        print "Case #%d:"%io,"NO"