Ini adalah kelanjutan longgar dari tantangan saya sebelumnya pada pembuatan grafik .

Latar Belakang

Seorang seniman eksentrik telah mempekerjakan Anda untuk memperkirakan integritas struktural pahatannya. Dia menciptakan karya seninya dengan mengambil banyak magnet berbentuk kubus, dan menjatuhkannya satu per satu ke tumpukan besar. Untuk menganalisis metodenya dengan lebih baik, kami menggunakan model dua dimensi berikut. Kami mulai dengan lantai kosong, dan menjatuhkan magnet #pada koordinat bilangan bulat apa pun, katakan 0:

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

Jika magnet lain jatuh 0, itu berakhir di atas yang sebelumnya:

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

Sekarang, mari kita jatuhkan satu magnet lagi 0, dan kemudian satu lagi di 1:

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

Seperti yang terlihat di atas, magnet jatuh menempel pada magnet kedua yang dilewatinya (magnet pertama hanya memperlambatnya). Magnet kedua tidak harus langsung di bawah yang pertama, dan magnet di kedua sisi masih dianggap sebagai satu magnet:

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

Para seniman ingin Anda menghitung celah vertikal maksimal di patung terakhir, yaitu, jumlah maksimum ruang kosong antara dua magnet pada kolom yang sama, atau magnet dan tanah di bawahnya. Pada gambar di atas, angka ini adalah 3 (pada kolom 2).

Memasukkan

Daftar bilangan bulat, mewakili koordinat di mana artis menjatuhkan magnetnya, baca dari kiri ke kanan. Anda dapat mengasumsikan bahwa koordinat memuaskan -1024 <= i < 1024dan bahwa panjang daftar paling banyak 1024, jika itu membantu.

Keluaran

Kesenjangan vertikal maksimal di patung terakhir. Patung yang kosong memiliki celah -1, dan kasing ini harus dimasukkan, karena pematung kami adalah seorang petapa.

Aturan tambahan

Anda dapat memberikan fungsi atau program lengkap. Hitungan byte terpendek menang, dan celah standar tidak diizinkan. Kode dengan penjelasan lebih disukai.

Uji kasus

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

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

Pemakaian:

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

Fungsi ini membangun fungsi lain yang mengembalikan daftar posisi magnet y untuk posisi x yang diberikan. Dengan itu, ia menghitung kesenjangan untuk semua x-posisi -1024 .. 1024 dan mengambil maksimum (Edit: sekarang saya mengambil minimum, karena kesenjangan negatif: semakin rendah angkanya semakin besar kesenjangan).

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

Atau versi yang mudah dibaca

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

Sebelum bermain golf di ruang putih, tampilannya seperti ini:

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

Inilah penjelasan tentang garis-garis yang lebih kompleks, sebagian besar untuk keuntungan saya sendiri.

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

Ini membangun susunan daftar kosong panjang maks (tetes) -min (tetes) +1 plus pengganti di kedua sisi. Saya selalu ingin menulis [[]] * K untuk membangun array daftar kosong, tetapi itu membuat K pointer ke daftar kosong yang sama.

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

Fungsi izip_longest dari itertools seperti zip, tetapi mengisi daftar yang lebih pendek dengan None untuk menggabungkan daftar tersebut. Pengiris [:: - 1] membalik daftar 0 dan 1 dari perbandingan "atau". Daftar ini dibalik untuk menggunakan metode indeks di baris berikutnya, yang menemukan contoh elemen pertama. Karena elemen terakhir dari kolom kosong adalah 1, ini adalah elemen pertama dalam daftar terbalik dan diabaikan melalui slice [1:].

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

Pertama hitung perbedaan antara panjang kolom i dan posisi 1 kedua di kolom yang berdekatan. Jika perbedaannya positif, tambahkan banyak angka nol ke kolom i sebelum menambahkan angka 1. Setiap kali angka nonpositif [0] adalah daftar kosong.

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

Grup fungsi oleh itertools membagi daftar menjadi beberapa elemen berikutnya. Baris ini menemukan maks dari panjang semua urutan nol di semua kolom. Sangat penting untuk melemparkan setiap urutan q ke daftar, karena groupby mengembalikan generator (seperti semua fungsi itertools) yang secara alami tidak mendukung metode len.

Java - 281 byte

Cukup lurus ke depan.

Pertama membangun patung dalam sebuah array

Kemudian ia menemukan celah terbesar.

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

kecil -

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