Il s'agit d'une continuation lâche de mon défi précédent sur la construction de graphiques .

Contexte

Un artiste excentrique vous a engagé pour estimer l'intégrité structurelle de ses sculptures. Il crée ses œuvres d'art en prenant un tas d'aimants en forme de cube et en les déposant un par un dans un énorme tas. Pour mieux analyser sa méthode, nous utilisons le modèle bidimensionnel suivant. Nous commençons avec un sol vide et déposons un aimant #à n'importe quelle coordonnée entière, disons 0:

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

Si un autre aimant tombe 0, il se retrouve au-dessus du précédent:

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

Maintenant, laissons tomber un aimant de plus à 0, puis un à 1:

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

Comme vu ci-dessus, un aimant qui tombe colle au deuxième aimant qu'il passe (le premier le ralentit simplement). Le deuxième aimant n'a pas besoin d'être directement en dessous du premier, et un aimant des deux côtés compte toujours comme un aimant:

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

Les artistes veulent que vous calculiez l'écart vertical maximal dans la sculpture finale, c'est-à-dire le nombre maximal d'espaces vides entre deux aimants sur la même colonne, ou un aimant et le sol en dessous. Dans l'image ci-dessus, ce nombre serait 3 (sur la colonne 2).

Contribution

Une liste d'entiers, représentant les coordonnées où l'artiste laisse tomber ses aimants, lue de gauche à droite. Vous pouvez supposer que les coordonnées satisfont -1024 <= i < 1024et que la longueur de la liste est au maximum 1024, si cela vous aide.

Production

L'écart vertical maximal dans la sculpture finale. La sculpture vide a un écart -1, et ce cas doit être inclus, car notre sculpteur est un dadaïste.

Règles supplémentaires

Vous pouvez donner une fonction ou un programme complet. Le nombre d'octets le plus court l'emporte et les failles standard sont interdites. Un code avec des explications est préférable.

Cas de test

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

{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 octets

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

Usage:

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

Cette fonction crée une autre fonction qui renvoie une liste de positions y magnétiques pour une position x donnée. Avec lui, il calcule les écarts pour toutes les positions x -1024 .. 1024 et prend le maximum (Edit: maintenant je prends le minimum, car les écarts sont négatifs: plus le nombre est faible, plus l'écart est grand).

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

Ou version lisible

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

Avant de jouer au golf en espace blanc, cela ressemble à ceci:

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

Voici une explication des lignes plus complexes, principalement pour mon propre bénéfice.

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

Cela construit un tableau de listes vides de longueur max (gouttes) -min (gouttes) +1 plus un espace réservé de chaque côté. Je veux toujours écrire [[]] * K pour construire un tableau de listes vides, mais cela fait K pointeurs vers la même liste vide.

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

La fonction izip_longest d'itertools est comme zip, mais remplit la liste plus courte avec None afin de compresser les listes ensemble. Le découpage [:: - 1] inverse la liste des 0 et des 1 de la comparaison "ou". La liste est inversée afin d'utiliser la méthode index dans la ligne suivante, qui trouve la première instance d'un élément. Étant donné que le dernier élément d'une colonne non vide doit être 1, il s'agit du premier élément de la liste inversée et est ignoré via la tranche [1:].

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

Calculez d'abord la différence entre la longueur de la colonne i et la position du second 1 dans les colonnes adjacentes. Si la différence est positive, ajoutez autant de zéros à la colonne i avant d'ajouter un 1. Tout nombre non positif multiplié par [0] est la liste vide.

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

La fonction groupby d'itertools divise une liste en sous-séquences d'éléments consécutifs. Cette ligne trouve le maximum des longueurs de toutes les sous-séquences de zéros dans toutes les colonnes. Il est nécessaire de transtyper chaque sous-séquence q dans une liste, car groupby renvoie un générateur (comme toutes les fonctions itertools) qui, naturellement, ne prend pas en charge une méthode len.

Java - 281 octets

Assez simple.

Il construit d'abord la sculpture en réseau

Ensuite, il trouve le plus grand écart.

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

petit -

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