Dies ist eine lose Fortsetzung meiner früheren Herausforderung beim Erstellen von Diagrammen .

Hintergrund

Ein exzentrischer Künstler hat Sie beauftragt, die strukturelle Integrität seiner Skulpturen einzuschätzen. Er erschafft seine Kunstwerke, indem er ein paar würfelförmige Magnete eins nach dem anderen auf einen riesigen Stapel wirft. Um seine Methode besser analysieren zu können, verwenden wir das folgende zweidimensionale Modell. Wir beginnen mit einem leeren Boden und lassen einen Magneten #an einer beliebigen Ganzzahlkoordinate fallen, sagen wir 0:

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

Wenn ein anderer Magnet fallen gelassen wird 0, landet er oben auf dem vorherigen:

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

Lassen Sie uns noch einen Magneten auf 0und dann einen auf fallen 1:

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

Wie oben zu sehen, haftet ein fallender Magnet am zweiten Magneten, den er passiert (der erste verlangsamt ihn lediglich). Der zweite Magnet muss nicht direkt unter dem ersten liegen, und ein Magnet auf beiden Seiten zählt immer noch als ein Magnet:

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

Der Künstler möchte, dass Sie die maximale vertikale Lücke in der endgültigen Skulptur berechnen, dh die maximale Anzahl von Leerstellen zwischen zwei Magneten auf derselben Säule oder einem Magneten und dem Boden darunter. Im obigen Bild wäre diese Zahl 3 (in der Spalte 2).

Eingang

Eine Liste von Ganzzahlen, die die Koordinaten darstellen, bei denen der Künstler seine Magnete fallen lässt, wird von links nach rechts gelesen. Sie können davon ausgehen, dass die Koordinaten übereinstimmen -1024 <= i < 1024und dass die Länge der Liste maximal ist 1024, wenn dies hilft.

Ausgabe

Die maximale vertikale Lücke in der endgültigen Skulptur. Die leere Skulptur hat eine Lücke -1, und dieser Fall muss eingeschlossen werden, da unser Bildhauer ein Dadaist ist.

Zusätzliche Regeln

Sie können eine Funktion oder ein vollständiges Programm angeben. Die kürzeste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig. Code mit Erläuterungen wird bevorzugt.

Testfälle

[] -> -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 Zeichen

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

Verwendung:

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

Diese Funktion erstellt eine weitere Funktion, die eine Liste der Magnet-Y-Positionen für eine bestimmte X-Position zurückgibt. Damit berechnet es die Lücken für alle x-Positionen -1024 .. 1024 und nimmt das Maximum (Edit: jetzt nehme ich das Minimum, weil die Lücken negativ sind: je niedriger die Zahl, desto größer die Lücke).

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

Oder lesbare Version

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

Vor dem White Space Golfen sieht es so aus:

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

Hier ist eine Erklärung der komplexeren Zeilen, hauptsächlich zu meinem eigenen Vorteil.

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

Dadurch wird ein Array von leeren Listen mit der Länge max (drops) -min (drops) +1 plus einem Platzhalter auf beiden Seiten erstellt. Ich möchte immer [[]] * K schreiben, um ein Array von leeren Listen zu erstellen, aber dadurch werden K-Zeiger auf dieselbe leere Liste gesetzt.

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

Die Funktion izip_longest von itertools ähnelt zip, füllt jedoch die kürzere Liste mit None, um die Listen zusammen zu komprimieren. Das Schneiden [:: - 1] kehrt die Liste der Nullen und Einsen aus dem "oder" -Vergleich um. Die Liste wird umgekehrt, um die Indexmethode in der nächsten Zeile zu verwenden, die die erste Instanz eines Elements findet. Da das letzte Element einer nicht leeren Spalte 1 sein muss, ist dies das erste Element in der umgekehrten Liste und wird über das Slice [1:] ignoriert.

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

Berechnen Sie zunächst die Differenz zwischen der Länge der Spalte i und der Position der zweiten 1 in den benachbarten Spalten. Wenn die Differenz positiv ist, fügen Sie der Spalte i so viele Nullen hinzu, bevor Sie eine 1 hinzufügen. Alle nicht positiven Zahlen, die mit [0] angegeben sind, sind leere Listen.

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

Die Funktionsgruppe von itertools teilt eine Liste in Teilfolgen aufeinanderfolgender Elemente auf. Diese Zeile ermittelt die maximale Länge aller Teilsequenzen von Nullen in allen Spalten. Es ist notwendig, jede Teilsequenz q in eine Liste umzuwandeln, da groupby (wie alle itertools-Funktionen) einen Generator zurückgibt, der natürlich keine len-Methode unterstützt.

Java - 281 Bytes

Ziemlich einfach.

Zuerst baut es die Skulptur in einem Array auf

Dann findet es die größte Lücke.

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

klein -

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