Magnetic Sculptures

Question

This is a loose continuation of my earlier challenge on constructing graphs.

Background

An eccentric artist has hired you to estimate the structural integrity of his sculptures. He creates his works of art by taking a bunch of cube-shaped magnets, and dropping them one by one into a huge pile. To better analyze his method, we use the following two-dimensional model. We start with an empty floor, and drop a magnet # at any integer coordinate, say 0:

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

If another magnet is dropped at 0, it ends up on top of the previous one:

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

Now, let us drop one more magnet at 0, and then one at 1:

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

As seen above, a falling magnet sticks to the second magnet it passes (the first one merely slows it down). The second magnet need not be directly below the first one, and a magnet on both sides still counts as one magnet:

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

The artists wants you to calculate the maximal vertical gap in the final sculpture, that is, the maximum number of empty spaces between two magnets on the same column, or a magnet and the ground below it. In the above picture, this number would be 3 (on column 2).

Input

A list of integers, representing the coordinates where the artist drops his magnets, read from left to right. You may assume that the coordinates satisfy -1024 <= i < 1024 and that the length of the list is at most 1024, if that helps.

Output

The maximal vertical gap in the final sculpture. The empty sculpture has gap -1, and this case has to be included, since our sculptor is a dadaist.

Additional rules

You may give a function or a full program. The shortest byte count wins, and standard loopholes are disallowed. Code with explanations is preferred.

Test cases

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

Answer 1

Dyalog APL, 73 70 characters

{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

Answer 2

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

Usage:

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

This function builds up another function that returns a list of magnet y-positions for a given x-position. With it, it calculates the gaps for all x-positions -1024 .. 1024 and takes the maximum (Edit: now I'm taking the minimum, because gaps are negative: the lower the number the larger the gap).

Answer 3

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

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

Answer 4

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

Before white space golfing, it looks like this:

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

Here's an explanation of the more complex lines, mostly for my own benefit.

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

This constructs an array of empty lists of length max(drops)-min(drops)+1 plus a placeholder on either side. I always want to write [ [ ] ]*K to construct an array of empty lists, but that makes K pointers to the same empty list.

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

The function izip_longest from itertools is like zip, but infills the shorter list with None in order to zip the lists together. The slicing [::-1] reverses the list of 0's and 1's from the "or" comparison. The list is reversed in order to use the index method in the next line, which finds the first instance of an element. Since the last element of a nonempty column must be 1, this is the first element in the reversed list and is ignored via the slice [1:].

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

First calculate the difference between the length of column i and the position of the second 1 in the adjacent columns. If the difference is positive, add that many zeros to column i before adding a 1. Any nonpositive number times [0] is the empty list.

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

The function groupby from itertools splits a list into subsequences of consecutive elements. This line finds the max of the lengths of all the subsequences of zeros in all of the columns. It's necessary to cast each subsequence q to a list, because groupby returns a generator (like all the itertools functions) which naturally doesn't support a len method.

Answer 5

Java - 281 bytes

Pretty straight forward.

First it constructs the sculpture in an array

Then it finds the greatest gap.

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

small -

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