14
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Note: This is 122 bytes long (challenge is in bytes), assuming UTF-8. \$\endgroup\$ – MtnViewMark Jan 1 '15 at 4:40
  • 1
    \$\begingroup\$ See codegolf.stackexchange.com/questions/42536/… \$\endgroup\$ – ngn Jan 1 '15 at 11:21
  • \$\begingroup\$ I'm quite sympathetic: I've often been dinged for using non-ASCII characters in my golf'd Haskell. Since then I've been quite mindful if the Q specifies count by characters or bytes. \$\endgroup\$ – MtnViewMark Jan 1 '15 at 17:07
  • \$\begingroup\$ @MtnViewMark Scoring by bytes doesn't mean scoring by UTF-8 bytes. Doing so for APL is punishing it for being too old to recognise ASCII as an important standard. APL's character set fits easily within a single-byte codepage and that codepage exists. So using that codepage as the encoding each character is a byte. On the other hand, if you use non-ASCII characters in Haskell, you'll have to use an encoding which contains both the ASCII and the non-ASCII characters - and that's usually UTF-8. \$\endgroup\$ – Martin Ender Jan 2 '15 at 18:06
  • \$\begingroup\$ @ngn - having now read most of the meta posts on this, seems that things are, alas, still muddy. However, perhaps it would be best, when the challenge is scored in bytes, to score APL in bytes, but mention somewhere the encoding used. \$\endgroup\$ – MtnViewMark Jan 3 '15 at 2:53
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Clever approach! Hope you don't mind that I golf'd it down a bit. \$\endgroup\$ – MtnViewMark Dec 31 '14 at 20:18
  • \$\begingroup\$ @MtnViewMark: Not at all. I've found 3 further bytes to save: don't flip the -, go with negative numbers and take the minimum. \$\endgroup\$ – nimi Dec 31 '14 at 21:25
  • \$\begingroup\$ In my repo, you can find this code, 42997-Magnetic.hs which also includes a test harness for the test cases, and a visualizer that displays the sculptures. \$\endgroup\$ – MtnViewMark Jan 1 '15 at 17:19
3
\$\begingroup\$

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;
};
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;}
\$\endgroup\$
  • \$\begingroup\$ You can save a byte by replacing the first || with |. Also, returning y instead of printing it saves 9 bytes. \$\endgroup\$ – Ypnypn Dec 31 '14 at 3:40
  • \$\begingroup\$ @Ypnypn, Thanks! BTW, Your first statement seems to throw an ArrayIndexOutOfBounds exception (-1). (I don't have a lot of experience with bitwise operators) \$\endgroup\$ – Stretch Maniac Dec 31 '14 at 19:56
  • \$\begingroup\$ It's been about 1.5 years, but you can golf it some more: (272 bytes): int a(int[]b){int z=9999,d[][]=new int[z][z],g,r,t,y=-1;for(int c:b){c+=z/2;g=0;for(r=z;--r>-2;){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;}. Summary of the changes: z=9999 has been added and used; int and int[][] field initialization has been merged into one; second || is replaced by |; for(r=9998;r>=0;r--) has been changed to for(r=z;--r>-2;) \$\endgroup\$ – Kevin Cruijssen Aug 3 '16 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.