Esta es una continuación floja de mi desafío anterior sobre la construcción de gráficos .

Antecedentes

Un artista excéntrico te ha contratado para estimar la integridad estructural de sus esculturas. Él crea sus obras de arte tomando un montón de imanes en forma de cubo y colocándolos uno por uno en una enorme pila. Para analizar mejor su método, utilizamos el siguiente modelo bidimensional. Comenzamos con un piso vacío y colocamos un imán #en cualquier coordenada entera, digamos 0:

       |
       v
       #
===============
       0

Si se deja caer otro imán 0, termina encima del anterior:

       |
       v
       #
       #
===============
       0

Ahora, dejemos caer un imán más en 0, y luego uno en 1:

        |
       #v
       ##
       #
===============
       0

Como se ve arriba, un imán que cae se pega al segundo imán que pasa (el primero simplemente lo ralentiza). El segundo imán no necesita estar directamente debajo del primero, y un imán en ambos lados todavía cuenta como un imán:

      #   #
      ##|##
      # v #
      ### #
      #   #
===============
       0

Los artistas quieren que calcules el espacio vertical máximo en la escultura final, es decir, el número máximo de espacios vacíos entre dos imanes en la misma columna, o un imán y el suelo debajo de él. En la imagen de arriba, este número sería 3 (en la columna 2).

Entrada

Una lista de enteros, que representan las coordenadas donde el artista deja caer sus imanes, leídos de izquierda a derecha. Puede suponer que las coordenadas satisfacen -1024 <= i < 1024y que la longitud de la lista es como máximo 1024, si eso ayuda.

Salida

La brecha vertical máxima en la escultura final. La escultura vacía tiene un hueco -1, y este caso tiene que ser incluido, ya que nuestro escultor es dadaísta.

Reglas adicionales

Puede dar una función o un programa completo. El conteo de bytes más corto gana, y las lagunas estándar no se permiten. Se prefiere el código con explicaciones.

Casos de prueba

[] -> -1
[0,2,1] -> 0
[0,0,0,0,0,1,-1] -> 3
[0,0,0,0,0,1,1,1,2] -> 4
[1,1,2,2,2,2,2,2,1] -> 2
[1,1,2,2,2,2,2,2,1,0,1,0] -> 2
[1,2,1,2,1,2,1,2,2,2,2,1,0] -> 3
[-1,-1,-1,1,1,1,0] -> 1
[-1,-1,-1,-1,2,2,1,1,2,2,2,1,0] -> 2
[-2,-2,-2,-1,-1,-1,0,0,0,1,1,1,2,2,2,3,3,4,4,5,5,5,6] -> 6

Dyalog APL, 73 70 caracteres

{y←⍬⋄⌈/¯1,,¯1-2-/0,x⊢⌸{y,←⌈/(1+y/⍨0=⍵),Y⊃⍨2⊃⍒Y←1 1,∪y/⍨1=⍵}¨|x-¯1↓¨,\x←⍵}

{y←⍬⋄¯1⌈⌈/,¯1-2-/¯1,⍵⊢⌸{y,←⌈/(1+y/⍨0=⍵),⊃1↓{⍵[⍒⍵]}∪y/⍨1=⍵}¨|⍵-¯1↓¨,\⍵}

First statement:
       y←⍬  initialize semi-global variable y with an empty vector
Second statement, from right to left:
         ⍵  the vector of x coordinates
       ,\⍵  concat-scan: all prefixes of ⍵ of length 1, 2, ..., ≢⍵
   ¯1↓¨,\⍵  drop the last element of each prefix, lengths are 0, 1, ..., (≢⍵)-1
|⍵-¯1↓¨,\⍵  for each x: magnitudes of differences between x and its predecessors
 {...}¨...  execute the code in parens for each item of the argument
         ⍵  is now a single vector of differences from those described above
       1=⍵  boolean mask, where are our neighbouring xs?
    y/⍨1=⍵  select the ys corresponding to our neighbouring xs
   ∪y/⍨1=⍵  unique ys
   {⍵[⍒⍵]}  sort descending
       ⊃1↓  first of one-drop, i.e. get the second element if it exists, otherwise 0
       0=⍵  which previous xs are the same as our x?
  1+y/⍨0=⍵  select the corresponding ys and add 1 to them
        ⌈/  maximum of all the ys described so far
       y,←  append to the semi-global y
            the result from {} will be identical to y
  ⍵⊢⌸{...}  a matrix of ys, grouped in rows by x (which is now in ⍵) and zero-padded
       ¯1,  prepend ¯1 to the left of each row
       2-/  differences between consecutive horizontal elements, result is a matrix
       ¯1-  negative one minus each element of the matrix
         ,  ravel the matrix (linearize it to a vector)
        ⌈/  maximum; if the vector is empty, return ¯1.8e308, a very small number
     ¯1⌈⌈/  greater of ¯1 and the ⌈/  to avoid the very small number

Haskell - 217 185 182 Bytes

import Data.List
r g n m|m==n=max(head(g m)+1)((reverse.(0:).nub.sort$g(m-1)++g(m+1))!!1):g m|1<3=g m
j x=(-1)-minimum(0:(map(foldl r(\_->[0])x)[-1024..1024]>>=(tail>>=zipWith(-))))

Uso:

j [1,2,1,2,1,2,1,2,2,2,2,1,0]

Esta función genera otra función que devuelve una lista de posiciones y de imán para una posición x dada. Con él, calcula los huecos para todas las posiciones x -1024 .. 1024 y toma el máximo (Editar: ahora estoy tomando el mínimo, porque los huecos son negativos: cuanto menor es el número, mayor es el hueco).

Javascript, 201 193

F=P=>{m=[];for(p of P){s=2;c=m[p]=m[p]||[];for(i=1e4;~i&&s;i--){if((m[p-1]||[])[i]||(m[p+1]||[])[i])s--;if(c[i-1]) s=0}c[++i]=1}g=-1;m.map(c=>{ d=0;for(i in c){g=i-d>g?i-d:g;d=++i} });return g}

F ([1,1,2,2,2,2,2,2,1]) === 2

O versión legible

F=P=>{
  m=[];  // magnet positions
  for(p of P){ // every dropped magnet
    s=2; // initial speed
    c=m[p]=m[p]||[]; // column where magnet is dropping
    for(i=1e4;~i&&s;i--){ // continue until at floor or zero speed
      if((m[p-1]||[])[i]||(m[p+1]||[])[i])s--;  // magnet on either side, decrease speed
      if(c[i-1]) s=0; // magnet is directly below
    }
    c[++i]=1;
  }
  g=-1; // maximum gap
  m.map(c=>{ 
          d=0;for(i in c){g=i-d>g?i-d:g;d=++i;} 
       });
  return g;
};

Python 2.7, 327

from itertools import * 
s=input()
if s:m=min(s);l=[[] for _ in range(max(s)-m+3)]
for t in s:
    i=t-m+1;r=l[i];c=[x or y for x,y in izip_longest(l[i-1],l[i+1])][::-1][1:];j=len(c)-c.index(1)-1-len(r) if any(c) else 0;l[i]=r+[0]*j+[1]
print -1 if not s else max([len(list(q)) if b==0 else 0 for k in l for b,q in groupby(k)])

Antes del golf de espacios en blanco, se ve así:

from itertools import * 
s=input()
if s:
    m=min(s)
    l=[[] for _ in range(max(s)-m+3)]
for t in s:
    i=t-m+1;r=l[i]
    c=[x or y for x,y in izip_longest(l[i-1],l[i+1])][::-1][1:]
    j=len(c)-c.index(1)-1-len(r) if any(c) else 0
    l[i]=r+[0]*j+[1]
print -1 if not s else max([len(list(q)) if b==0 else 0 for k in l for b,q in groupby(k)])

Aquí hay una explicación de las líneas más complejas, principalmente para mi propio beneficio.

l=[[] for _ in range(max(s)-m+3)] 

Esto construye una matriz de listas vacías de longitud máxima (gotas) -min (gotas) +1 más un marcador de posición a cada lado. Siempre quiero escribir [[]] * K para construir una matriz de listas vacías, pero eso hace que K apuntes a la misma lista vacía.

c=[x or y for x,y in izip_longest(l[i-1],l[i+1])][::-1][1:] 

La función izip_longest de itertools es como zip, pero llena la lista más corta con None para comprimir las listas. La división [:: - 1] invierte la lista de 0 y 1 de la comparación "o". La lista se invierte para usar el método de índice en la siguiente línea, que encuentra la primera instancia de un elemento. Dado que el último elemento de una columna no vacía debe ser 1, este es el primer elemento de la lista invertida y se ignora a través del segmento [1:].

j=len(c)-c.index(1)-1-len(r) if any(c) else 0 
l[i]=r+[0]*j+[1]

Primero calcule la diferencia entre la longitud de la columna i y la posición del segundo 1 en las columnas adyacentes. Si la diferencia es positiva, agregue esa cantidad de ceros a la columna i antes de agregar un 1. Cualquier número no positivo multiplicado por [0] es la lista vacía.

max([len(list(q)) if b==0 else 0 for k in l for b,q in groupby(k)])

La función groupby de itertools divide una lista en subsecuencias de elementos consecutivos. Esta línea encuentra el máximo de las longitudes de todas las subsecuencias de ceros en todas las columnas. Es necesario convertir cada subsecuencia q en una lista, porque groupby devuelve un generador (como todas las funciones de itertools) que naturalmente no admite un método len.

Java - 281 bytes

Muy claro.

Primero construye la escultura en una matriz.

Entonces encuentra la mayor brecha.

int a(int[]b){
        int[][]d=new int[9999][9999];
        int g,r,t,y=-1;
        for(int c:b){
            c+=5000;
            g=0;
            for(r=9998;r>=0;r--){
                if(r==0||d[c][r-1]==1){d[c][r]=1;break;}
                if((d[c-1][r]==1||d[c+1][r]==1)&&++g==2){d[c][r]=1;break;}
            }
        }
        for(int[] k:d){
            t=0;
            for(int i:k){
                if(i==0)t++;
                else{if(t>y)y=t;t=0;}
            }
        }
        return y;
    }

pequeño -

int a(int[]b){int[][]d=new int[9999][9999];int g,r,t,y=-1;for(int c:b){c+=5000;g=0;for(r=9998;r>=0;r--){if(r==0||d[c][r-1]==1){d[c][r]=1;break;}if((d[c-1][r]==1||d[c+1][r]==1)&&++g==2){d[c][r]=1;break;}}}for(int[] k:d){t=0;for(int i:k){if(i==0)t++;else{if(t>y)y=t;t=0;}}}return y;}