14
1
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
Note: This is 122 bytes long (challenge is in bytes), assuming UTF-8. – MtnViewMark – 2015-01-01T04:40:37.407
1
See https://codegolf.stackexchange.com/questions/42536/create-an-array-with-repeated-numbers/42571?noredirect=1#comment100808_42571
– ngn – 2015-01-01T11:21:36.313I'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. – MtnViewMark – 2015-01-01T17:07:39.530
@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.
– Martin Ender – 2015-01-02T18:06:33.983@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. – MtnViewMark – 2015-01-03T02:53:13.020
@MtnViewMark I'd be happy to discuss any particular concerns you have. I don't think there would be much value in mentioning the encoding here, as this pertains to all APL posts. – ngn – 2015-01-03T15:58:27.013