Tomado de la ronda de calificación de Google Code Jam 2013 Problema B :

Alice y Bob tienen un césped frente a su casa, con forma de rectángulo de N metro por M metro. Cada año, intentan cortar el césped en un patrón interesante. Solían cortar con tijeras, lo que consumía mucho tiempo; pero ahora tienen un nuevo cortacésped automático con múltiples configuraciones, y quieren probarlo.

El nuevo cortacésped tiene una configuración de altura: puede configurarlo a cualquier altura h entre 1 y 100 milímetros, y cortará todo el césped más alto de lo que h encuentra a la altura h. Lo ejecutas entrando al césped en cualquier parte del borde del césped; luego la cortadora de césped va en línea recta, perpendicular al borde del césped en el que ingresó, cortando el césped en una franja de 1 m de ancho, hasta que sale del césped por el otro lado. La altura del cortacésped solo se puede establecer cuando no está en el césped.

Alice y Bob tienen varios patrones diferentes de hierba que podrían tener en su césped. Para cada uno de ellos, quieren saber si es posible cortar el césped en este patrón con su nueva cortadora de césped. Cada patrón se describe especificando la altura del césped en cada cuadrado de 1m x 1m del césped.

La hierba es inicialmente de 100 mm de altura en todo el césped.

Escriba una función que tome una matriz 2D de alturas enteras y determine si el césped se puede cortar en consecuencia.

Aquí hay 100 casos de prueba de Google Code Jam. Los primeros 35 casos deben pasar, el resto no.

El código más corto gana.

J, 15 caracteres

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

No esperaba esta solución corta.

Breve explicación:

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

Si su función es otra función 4 como en la solución: (f1 f2 f3 f4)y una entrada J la calcula como f1(input,f3(f2(input),f4(input)))es decir input f1 ((f2 input) f3 (f4 input)).

APL, 15 caracteres

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

Explicación:

• ⌈⌿⍵ calcula el máximo de las columnas de rhs
• ⌈/⍵ hace lo mismo con las filas
• ∘.⌊ ¿El producto externo de los dos anteriores con respecto a la función mínima
• ⍵≡ compara el resultado con la derecha

Ejemplos:

      {⍵≡(⌈/⍵)∘.⌊⌈⌿⍵} 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))))]

Tengo un código de Python un poco más largo, pero pasó todos los casos de prueba dados en 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"