The Skyline Problem
I just came across this little problem on UVA's Online Judge and thought, that it may be a good candidate for a little code-golf.
The problem:
You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. To make the problem tractable, all buildings are rectangular in shape and they share a common bottom (the city they are built in is very flat). The city is also viewed as two-dimensional. A building is specified by an ordered triple (Li, Hi, Ri) where Li and Ri are left and right coordinates, respectively, of building i and Hi is the height of the building.
In the diagram below buildings are shown on the left with triples
(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)
and the skyline, shown on the right, is represented by the sequence:
1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0
The output should consist of the vector that describes the skyline as shown in the example above. In the skyline vector (v1, v2, v3, ... vn) , the vi such that i is an even number represent a horizontal line (height). The vi such that i is an odd number represent a vertical line (x-coordinate). The skyline vector should represent the "path" taken, for example, by a bug starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines that define the skyline. Thus the last entry in the skyline vector will be a 0. The coordinates must be separated by a blank space.
If I will not count declaration of provided (test) buildings and including all spaces and tab characters, my solution, in Python, is 223 characters long.
Here is the condensed version:
B=[[1,11,5],[2,6,7],[3,13,9],[12,7,16],[14,3,25],[19,18,22],[23,13,29],[24,4,28]]
# Solution.
R=range
v=[0 for e in R(max([y[2] for y in B])+1)]
for b in B:
for x in R(b[0], b[2]):
if b[1]>v[x]:
v[x]=b[1]
p=1
k=0
for x in R(len(v)):
V=v[x]
if p and V==0:
continue
elif V!=k:
p=0
print "%s %s" % (str(x), str(V)),
k=V
I think that I didn't made any mistake but if so - feel free to criticize me.
I don't have much reputation, so I will pay only 100 for a bounty - I am curious, if anyone could try to solve this in less than .. lets say, 80 characters. Solution posted by cobbal is 101 characters long and currently it is the best one.
I thought, that 80 characters is a sick limit for this kind of problem. cobbal, with his 46 character solution totaly amazed me - though I must admit, that I spent some time reading his explanation before I partially understood what he had written.
Answer
I'm just starting to learn J, so here goes my first attempt at golf:
103 62 49
46 characters
b =: 8 3 $ 1 11 5 2 6 7 3 13 9 12 7 16 14 3 25 19 18 22 23 13 29 24 4 28
,(,.{&s)I.s~:_1|.s=:0,~>./(1&{*{.<:[:i.{:)"1 b
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
although I'm sure someone who actually knows the language well could shorten this by quite a bit
An explanation of the code:
NB. list numbers up to right bound of the building
([: i. {:) 14 3 25
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
NB. compare to left bound of building and then multiply by height
(1&{ * {. <: [: i. {:) 14 3 25
0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 3 3 3 3 3 3 3 3 3 3
NB. apply to each row of b, note how shorter entries are padded with 0s
(1&{ * {. <: [: i. {:)"1 b
0 11 11 11 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 6 6 6 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
...
NB. collapse to find max, add a 0 to the end for rotate later, assign to s
] s =: 0 ,~ >./ (1&{ * {. <: [: i. {:)"1 b
0 11 11 13 13 13 13 13 13 0 0 0 7 7 7 7 3 3 3 18 18 18 3 13 13 13 13 13 13 0
NB. rotate s right 1 and then compare to s to find where height changes
s ~: _1 |. s
0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 1
NB. find indices of all differences
I. s ~: _1 |. s
1 3 9 12 16 19 22 23 29
NB. pair each index with the height of the building there
(,. {&s) I. s ~: _1 |. s
1 11
3 13
9 0
...
NB. and finally flatten the list
, (,. {&s) I. s ~: _1 |. s
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0