The Skyline Problem‍​​

Question

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.

Prominent

should this be wiki? – Moslem

This was my first year assignment to be implemented in scheme. – Simferopol

I'm enjoying trying to figure out how this works. One small observation, though. The second to last line can be written: print "%s %s" % (x, V), – Sulph

Hey! you are spoiling the whole fun of playing UVa Judge! – Egin

This question is seriously misleading, I thought you were asking about actual skyline algorithms... maybe you could add a (Not database related) comment somewhere ;) Here's a couple random websearch's if your not current in the field... portal.acm.org/citation.cfm?id=1369020 danupon.googlepages.com/randomizedsequentialskylinealgorithms – Tympanites

The data points for the two images don't match. ( They do however match the image that it goes along with. ) – Algology

Answer 1

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

Helwig

Ah, if I had seen your improvements I wouldn't have written up my answer. I didn't think of using the 0 autofill, that's pretty clever... – Jaguar

Is there any non-esoteric language that's less readable than this? ;-) – Vertebra

@Zifre: If there's demand, I can write a detailed explanation for this just as I did for my J solution. Once you get used to J's vocabulary, it's not too bad... the problem is that they inherited APL's "there must be a symbol for every possible action" and jammed it into ASCII. – Jaguar

I would really like to have a detailed explanation. After I saw your first version, I downloaded J and tried to create my own version but my head hurt after two minutes ;-) – Jidda

community wiki now, anyone who wants to shorten it or add an explanation are welcome to – Helwig

I am in awe at how short your solution is (but I haven't read the explanation yet). It's a shame that J isn't a qualified language to submit your solution in; I wonder how you would have placed on the ranking list for that problem. – Unnecessary

Unless they have changed the rules quite a bit, the rank is first number of correct answers and secondly to resolve ties the time spent in solving it (from the beginning of the contest) – Kahaleel

Answer 2

Python, 89 characters, also using Triptych's 5001 cheat:

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

x=o=0
while x<5001:
 n=max([H for L,H,R in B if L<=x<R]+[0])
 if n-o:print x,n,
 o=n;x+=1

Replacing 5001 by max(map(max,B))+1 to allow (almost) arbitrarily large cities leaves 102 characters.

Revision History:

• saved two chars as described in John Pirie's comment
• saved one char as MahlerFive suggested

Biotope

I am in awe. Change "L<x+.5<R" to "L<=x<R" to save 2 chars? – Laticialaticiferous

Oh, yeah, thanks. That's a leftover from an earlier try where I had some reason for that. – Biotope

big fan of the (n-o). And I laughed at myself for using three-space indents. Great job! – Housebreaking

use a semicolon to have o=n and x+=1 on the same line saving 1 character – Bluebonnet

@MahlerFive: Cool. Honestly, I have never ever used a semicolon in Python before. If you had asked me whether that was legal, I wouldn't have known for sure. Thanks! – Biotope

Answer 3

Python: 115 characters

Like the OP, I'm not including the declaration of the data, but I am counting whitespace.

D = [(1,11,5), (2,6,7), (3,13,9), (12,7,16), 
 (14,3,25), (19,18,22), (23,13,29), (24,4,28)]

P=[max([0]+[h for s,h,e in D if s<=x<e])for x in range(5001)]
for i,x in enumerate(P[1:]):
   if x!=P[i]:print i+1,x,

Note that I am using the link provided by the OP as the exact definition of the problem. For instance, I cheat a bit by assuming there is not building coordinate over 5000, and that all coordinates are positive integers. The original post is not tightly constrained enough for this to be fun, in my opinion.

edit: thanks to John Pirie for the tip about collapsing the list construction into the printing for loop. How'd I miss that?!

edit: I changed range(1+max(zip(*D)[2])) to range(5001) after deciding the use the exact definition given in the original problem. The first version would handle buildings of arbitrary positive integers (assuming it all fit into memory).

edit: Realized I was overcomplicating things. Check my revisions.

BTW - I have a hunch there's a much more elegant, and possibly shorter, way to do this. Somebody beat me!

Housebreaking

Triptych, nice one...really nice. – Prominent

i'm not so good at python... are you assuming the input to be in order that they are in the city scape or will I have to deal with that in my code? – Moslem

I do not assume the buildings to be listed in any order. – Housebreaking

Triptych: amazing. You can shorten by collapsing calculation of L into the for i,h statement, I think down to 156 chars. – Laticialaticiferous

Hmm, except I don't think it works for cases including a (0,h,e) – Laticialaticiferous

But "range(-1,1+...)" and "print i-1,h," might – Laticialaticiferous

@Pirie, the link to the original problem provided by the OP does specify that all building coordinates are positive integers. I ran with that. This problem is a lot less fun if it's not tightly defined. – Housebreaking

@Triptych: right you are, thanks. As a Python student learning a ton from your solution, I hope you'll forgive me if I keep messing with it – Laticialaticiferous

Answer 4

A 176 byte WinXP .COM executable:

vQoAgMYQjsKO2jPAM/+5AIDzq7QLzSE8/751AXQDvoQB6DkAi/noNACL2egvACn5A/87HXYCiR2D xwLi9eviM8mZ9/VSQQvAdfeI+rQCzSG3LFqAwjC0As0h4vbD/9Y8CnP6D7bI/9Y8CnPwtACR9+UD yOvxtAvNITz/dRO0CM0hLDDDtAHNITwadfW+kAHDM/Yz/7cgrTn4dA+L+I1E/tHo6Jr/i8folf8L 9nXozSA=

Base64 encoded, I used this site to encode it. Decode to a .com file. The program reads stdin until an EOF, which is a Ctrl-Z when reading from the console, and then outputs the result to stdout.

EDIT: The source code:

    mov bp,10
    add dh,10h
    mov es,dx
    mov ds,dx
    xor ax,ax
    xor di,di
    mov cx,8000h
    rep stosw
    mov ah,0bh
    int 21h
    cmp al,255
    mov si,offset l9
    je l1
    mov si,offset l11
l1:
    call l7
    mov di,cx
    call l7
    mov bx,cx
    call l7
    sub cx,di
    add di,di
l2:
    cmp bx,[di]
    jbe l3
    mov [di],bx
l3:
    add di,2
    loop l2
    jmp l1
l4:
    xor cx,cx
l5:
    cwd
    div bp
    push dx
    inc cx
    or ax,ax
    jnz l5
    mov dl,bh
    mov ah,2
    int 21h
    mov bh,44
l6:
    pop dx
    add dl,48
    mov ah,2
    int 21h
    loop l6
    ret
l7:
    call si
    cmp al,10
    jae l7
    db 0fh, 0b6h, 0c8h
l8:
    call si
    cmp al,10
    jae ret
    mov ah,0
    xchg cx,ax
    mul bp
    add cx,ax
    jmp l8
l9:
    mov ah,0bh
    int 21h
    cmp al,255
    jne l12
    mov ah,8
    int 21h
l10:
    sub al,48
    ret
l11:
    mov ah,1
    int 21h
    cmp al,26
    jne l10
    mov si,offset l12
    ret
l12:
    xor si,si
    xor di,di
    mov bh,32
l13:
    lodsw
    cmp ax,di
    je l14
    mov di,ax
    lea ax,[si-2]
    shr ax,1
    call l4
    mov ax,di
    call l4
l14:
    or si,si
    jne l13
    int 20h

Compiled, as usual for me, using A86.

Claypan

How do I know this isn't a Trojan ;-) – Feingold

Ah, my evil plan to take over ze vorld has been foiled. Time to unleash the sharks vith lasers! – Claypan

You got freakin' sharks with freakin' lasers on their heads... that is so cool – Thenceforth

Answer 5

Python with 133 chars, memory and time efficient, no restrictions on data input

D = [(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28)]

l,T=0,zip(*D)
for x,h in map(lambda x:(x,max([y for a,y,b in D if a<=x<b]or[0])),sorted(T[0]+T[2])):
    if h!=l: print x,h,
    l=h

explanation:

lambda x:(x,max([y for a,y,b in D if a<=x<b]or[0])

returns the position and the height at position x.

Now loop over the sorted coordinate list compiled by sorted(zip(*D)[0]+zip(*D)[2]) and output if the height changes.

the second version isn't as efficient as the one above and has a coordinate limit but only uses 115 chars:

for x in range(100):
    E=[max([y for a,y,b in D if a<=(x-i)<b]+[0])for i in(0,1)]
    if E[0]-E[1]:print x,E[0],

Jidda

you can chain inequality operators in python. Change "a<=x and x<b" to "a<=x<b". – Housebreaking

Sorry - I had to revisit my solution after you beat me! – Housebreaking

Answer 6

98 characters of J, tacitly defined (no variable names!):

,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0(([:<./{."1)}.[:i.@>:[:>./{:"1))

In action:

$ jconsole
   s =: ,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0(([:<./{."1)}.[:i.@>:[:>./{:"1))
   |: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
 1 2  3 12 14 19 23 24
11 6 13  7  3 18 13  4
 5 7  9 16 25 22 29 28
   s b
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Only 86 characters with the assumption that the left-most coordinate is always 1.

,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0([:>:[:i.[:>./{:"1))

Only 76 with the additional assumption that the right-most coordinate is at most 99.

,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0&(>:i.99))

Borrowing some tricks from cobbal, I can get it to 68.

[:,@({:"1#>:@i.@#,.{."1)[:1&|.[:(,.(~:_1&|.))[:>./(1&{*{.<:[:i.{:)"1

The tacit definition just can't compete with using s=:… to eliminate redundancy, though.

---

Whenever I answer a question with J, I try to take the time to explain what's going on, because I think others might enjoy a look into the workings of an alien language.

   NB. The first, second, and last element of a vector
   ({. 0{b), (1 { 0{b), ({: 0{b)
1 11 5
   NB. Count from 0 to (last element of vector)-1
   i. {: 0{b
0 1 2 3 4
   NB. Booleans: first element of vector less than or equal to (above)?
   ({. <: [:i.{:) 0{b
0 1 1 1 1
   NB. Multiply by second element of vector
   (1&{ * {.<:[:i.{:) 0{b
0 11 11 11 11
   NB. Stack up results for each vector, then find maximum by column
   >./ (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
   NB. Identify leaders and make table
   |: (,. (~: _1 & |.)) >./(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
1  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
   NB. Rotate left
   |: 1 |. (,.(~:_1&|.))>./(1&{*{.<:[:i.{:)"1 b
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
 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. 1-based index and first element, when last element is true
   |: ({:"1 # >: @ i. @ # ,. {."1) 1&|.(,.(~:_1&|.))>./(1&{*{.<:[:i.{:)"1 b
 1  3 9 12 16 19 22 23 29
11 13 0  7  3 18  3 13  0
   NB. Flatten
   , ({:"1#>:@i.@#,.{."1)1&|.(,.(~:_1&|.))>./(1&{*{.<:[:i.{:)"1 b
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
   NB. Rearrange for tacit verb
   ([:,@({:"1#>:@i.@#,.{."1)[:1&|.[:(,.(~:_1&|.))[:>./(1&{*{.<:[:i.{:)"1) b
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Jaguar

like the tacit, very nice explanation too – Helwig

Answer 7

2 C# answers - way too long, but I'd love to see better?

LINQ approach (135 chars excluding array line):

var a=new[]{new[]{1,11,5},new[]{2,6,7},new[]{3,13,9},new[]{12,7,16},new[]{14,3,25},new[]{19,18,22},new[]{23,13,29},new[]{24,4,28}};    
int l=0,y,x=-1;while(++x<5001){var b=a.Where(c=>c[0]<=x&&c[2]>x);if((y=b.Any()?b.Max(c=>c[1]):0)!=l)Console.Write(x+", "+(l=y)+", ");}

Or a non-LINQ answer (179 185 chars excluding array line):

var a={1,11,5,2,6,7,3,13,9,12,7,16,13,3,25,19,18,22,23,13,29,24,4,28};
var b=new int[5000];int i=-1,j,z;while(++i<a.Length)for(j=a[i*3];j<a[i*3+2];j++)if((z=a[i*3+1])>b[j])b[j]=z;i=-1;z=0;while(++i<5000)if(b[i]!=z)Console.Write(i+", "+(z=b[i])+", ");

Staciestack

if((y=a.Where(c=>c[0]<=x&&c[2]>x).Max(c=>(int?)c[1])??0)!=l) saves you a few characters – Odle

"Console.Write" c#'s achilles heal of golf :) You have 3 references to [x,y] in the latter solution. replacing with [x*3+y] costs 6 characters but a.GetLength(0) becomes a.Length. the first [i*3+0] can lose th plus zero though so you net save ywo characters. you can lift the definition of j to where you define z. – Wilt

not sure if you allow yourself var in the non Linq version, shaves one character of the declaration of b. – Wilt

Nice; feel free to hack either/both in ;-p – Staciestack

Answer 8

Assuming the input:

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

Haskell: 105 characters

h x=maximum$0:[y|(l,y,r)<-b,l<=x,x<r]
main=putStr$unwords[show x++" "++show(h x)|x<-[1..9999],h x/=h(x-1)]

String formatting seems to be where Haskell falls behind the Python solutions. Having to use an extra 5 characters to write 'main=' doesn't help either, but perhaps it shouldn't be included, the C#/Java solutions would be massive if their code had to demonstrate the complete program :)

Haskell: 76 characters (no string formatting & no main)

h x=maximum$0:[y|(l,y,r)<-b,l<=x,x<r]
print[(x,h x)|x<-[1..9999],h x/=h(x-1)]

---

Looking back at the original problem it requires that you to read the input from a file, so I thought it would be interesting to see how many characters that adds.

Haskell: 149 characters (full solution)

main=interact f
f i=unwords[show x++" "++show(h x)|x<-[1..9999],h x/=h(x-1)] where
 h x=maximum$0:[y|[l,y,r]<-b,l<=x,x<r]
 b=map(map read.words)$lines i

Below is what the full solution looks like with more descriptive variable names and type signatures where possible.

main :: IO ()
main = interact skyline

skyline :: String -> String
skyline input =

  unwords [show x ++ " " ++ show (heightAt x) |
           x <- [1..9999], heightAt x /= heightAt (x-1)]

  where heightAt :: Int -> Int
        heightAt x = maximum $ 0 : [h | [l,h,r] <- buildings, l <= x, x < r]

        buildings :: [[Int]]
        buildings = map (map read . words) $ lines input

Glassware

Answer 9

Code is condensed (few lines to code) which is good for the tournament (time is the scarcest resource), and seems correct (I don't know python, but I think I understand the code).

Your solution basically paints the city skyline in a buffer and then outputs the contents of the buffer in the required format.

The extra info you ommited from the problem is that there will be at most 5000 buildings and the horizontal positions will smaller than 10.000. That implies that memory does not seem a problem in your case (40kb for the skyline assuming 32bit architecture, plus 45kb for the building description - optional, you could paint the skyline in the read loop). The algorithm is linear in the number of buildings so it is fast.

With toughter memory constraints you could go for a one-pass algorithm, but I believe that in this case it would perform slower and be much more complex to implement (more of your time, more CPU time)

Now you should consider really reading the input in the given format and using that data for your computations instead of a prestored data array.

BTW, is python a valid language now in ACM contests?

Sanitarium

Valid Languages = Java, C, C++, C#. As of 2008, problems may not have a judge-written C# solution. – Ethic

TomatoSandwich is right - Python is not a supported language for ACM contests - I just used it, because with it, I could write condensed code. I also omitted information about test cases, because SO doesn't have means of providing them automatically, so I assumed, that algorithm written for test data will work for all data – Prominent

The info about test data is important. If your skyline coordinates instead of ranging to 10.000 could range to 2^32-1 (max 32bit integer) then your algorithm would be flawed as it would require 2^34 bytes or 16Gb of memory to store the v variable (array from 0 to 2^32-1 of 32bit integers). The same goes for buildings, if the number was big enough you would have to refactor into a one-pass algorithm. Those are really important items to evaluate an algorithm, not only correctness but viability of the implementation. – Kahaleel

what happened with Pascal? have they dropped it? – Amino

@fortran: Pascal has never been part of the ACM ICPC to the best of my knowledge. You're probably thinking of the IOI (International Olympiad in Informatics) (for high-school (pre-university) students), in which the languages allowed are Pascal, C and C++. (No Java yet, because as it happens it's too slow in that setting.) – Kingsley

@ShreevatsaR: pascal was in fact allowed in the ICPC contests long ago. I remember a time when pascal, C and C++ where the allowed languages. – Kahaleel

@dribeas: Oh you're right. It seems Pascal was dropped as recently as 2007-2008... sorry :-) I wonder how recently Java was added; it's been around since at least 2004. – Kingsley

Answer 10

Here's a quick one in Perl

( by quick I mean less than two hours )

Perl in only 327 characters

( excluding " #/" to improve highlighting )

use 5.010;
$/=undef;
@s=map{[split',',$_]}grep{$_}split/\)\s*(?:$|,\s*\()|^\s*\(/,<>; #/
for$s(@s){($l,$y,$r)=@$s;
for$x($l..$r){$c=$p[$x];$p[$x]=$c>$y?$c:$y;}}
for($x=1;$x<=@p;$x++){$y=$p[$x]||0;
if(!defined$z){$l=$x;$z=$y;
}elsif($y!=$z){push@n,[$l,$z,$x-1];$z=$y;$l=$x;}}
push@n,[$l,$z];
say join', ',map{($_->[0],$_->[1])}@n;

Original testing version 853 characters

#! /usr/bin/env perl
use strict;
use warnings;
use 5.010;
use YAML;
use List::Util 'max';


my $file;
{
  local $/ = undef;
  $file = <>;
}

my @sections = map { [split ',', $_] } grep {$_} split m'
  \)\s* (?:$|,\s*\() |
  ^ \s* \(
'x, $file;

#my $max_x = max map{ $_->[2] } @sections;
#say $max_x;

my @points;
for my $reg( @sections ){
  my($l,$y,$r) = @$reg;
  for my $x ( $l .. $r ){
    my $c = $points[$x] || 0;
    $points[$x] = max $c, $y;
  }
}


my @new;
my($l,$last_y);
for( my $x=1; $x <= @points; $x++ ){
  my $y = $points[$x] || 0;

  # start
  if( ! defined $last_y ){
    $l = $x;
    $last_y = $y;
    next;
  }

  if( $y != $last_y ){
    push @new, [$l,$last_y,$x-1];
    $last_y = $y;
    $l = $x;
    next;
  }
}
push @new, [$l,$last_y];


say Dump \@sections, \@points, \@new;

say join ', ', map { ($_->[0],$_->[1]) } @new;

Initial minified version 621 characters

( excluding " #/" to improve highlighting )

#! /usr/bin/env perl
use strict;
use warnings;
use YAML;
use 5.010;

$/=undef;

my@s=map{[split',',$_]}grep{$_}split/\)\s*(?:$|,\s*\()|^\s*\(/,<>; #/

my@p;
{
  no strict; no warnings 'uninitialized';

  for$s(@s){
    ($l,$y,$r)=@$s;
    for$x($l..$r){
      $c=$p[$x];
      $p[$x]=$c>$y?$c:$y;
    }
  }
}

# $last_y => $z
my @n;
{
  no strict;

  #my($l,$z);
  for($x=1;$x<=@p;$x++){
    $y=$p[$x]||0;
    if(!defined$z){
      $l=$x;
      $z=$y;
    }elsif($y!=$z){
      push@n,[$l,$z,$x-1];
      $z=$y;
      $l=$x;
    }
  }
  push@n,[$l,$z];
}

say Dump \@s, \@p, \@n;

say join', ',map{($_->[0],$_->[1])}@n;

I used YAML to make sure I was getting the right data, and that the different versions worked the same way.

Algology

Answer 11

C

int main(int arc, char **argv) {
  int B[][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}},o=0,y=0,x=0,blen=8,bs=0,b;
  for (;x<9001;x++,o=y,y=0) {
    for (b=bs;b<blen;b++) {
      if (x >= B[b][0] && x < B[b][2] && B[b][1] > y) y=B[b][1];
      if (x > B[b][2]) bs = b;
    }
    if (y-o) printf("%d %d ", x, y);
  }
}

Amsden

Answer 12

ruby, 80 chars

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]]
o=0;1.upto(5001){|x|y=(B.map{|b|x>=b[0]&&x<b[2]&&b[1]||0}.max);o!=(o=y)&&p(x,y)}

Eterne

Answer 13

Here's my attempt in Perl. 137 characters, of which 33 are dedicated to finding the end of the skyline.

@a = ([1,11,5],[2,6,7],[3,13,9],[12,7,16],[14,3,25],[19,18,22],[23,13,29],[24,4,28]);
($x)=sort{$b<=>$a}map{$$_[2]}@a;
for(;$c<=$x;$c++){$n=0;map{$n=$$_[1]if$c>=$$_[0]&&$c<$$_[2]&&$n<$$_[1]}@a;print"$c $n "if$n!=$h;$h=$n;}

Administrative

It's even shorter than mine :P How long did this take you to create? – Algology

Answer 14

Rereading the UVA rules, we're not limited to a max X of 5000, but rather 5000 buildings. X and Y values up to (and including) 9999 are allowed.

Also, apparently only C, C++, C#, and Java are officially recognized languages, so I did mine up in Java. The numbers are only space separated, but commas could be put back in (at a cost of two more total chars). Totalling 153 chars (excluding the array line):

int[][]b=new int[][]{{1,11,5},{2,6,7},{3,13,9},{12,7,16},{14,3,25},{19,18,22},{23,13,29},{24,4,28}};
int[]y=new int[10000];int i;for(int[]o:b)for(i=o[0];i<o[2];y[i]=Math.max(y[i++],o[1]));for(i=0;i<9999;)if(y[i++]!=y[i])System.out.print(i+" "+y[i]+" ");

The logic is pretty straightforward. The only things that make the flow a little wonky are variable reuse and nonstandard placement of post-increment. Generates:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0 

Evince

Answer 15

Apart from the challenge.

Is the result set correct? At position 22 the highest point is 18 and at 23 is 13, so 3 is not the highest point.

I also tried to make a php version and it gives me a diferent final vector. It is not optimized for speed.

<?php
$buildings = array(
    array(1,11,5), 
    array(2,6,7), 
    array(3,13,9), 
    array(12,7,16), 
    array(14,3,25), 
    array(19,18,22), 
    array(23,13,29), 
    array(24,4,28)
);

$preSkyline = array();
for( $i = 0; $i<= 30; $i++){
    foreach( $buildings as $k => $building){
        if( $i >= $building[0] && $i<= $building[2]){
            $preSkyline[$i][$k] = $building[1];
        } else{
            $preSkyline[$i][$k] = 0;
        }
    }
}
foreach( $preSkyline as $s =>$a){
    $skyline[$s] = max( $a );
}
$finalSkyline = array();
foreach( $skyline as $k => $v){
    if( $v !== $skyline[ $k-1]){
        $finalSkyline[$k] =  $v;
    }
}
echo "<pre>";
print_r( $finalSkyline );
?>

this returns:

Array
(
    [0] => 11
    [2] => 13
    [9] => 0
    [11] => 7
    [16] => 3
    [18] => 18
    [22] => 13
    [29] => 0
)

which are the inflexion points and the max height.

Recitation

Answer 16

Even though this is an old post, I thought I'd share my gnu octave implementation in 137 characters:

function[p]=sl(b)s=zeros(max(b)(:,2),max(b(:,3)));for i=b's(1:i(2),i(1):i(3)-1)=1;end;t=sum(s);u=find(shift(t,1)~=t);p=[u;t(u)](:)';end;

Pass any size matrix of triples as b

Spanishamerican

Answer 17

#include <stdio.h>
#define MAX_B   5000
static unsigned max_y[MAX_B];
main() {
    signed i, j;
    int max_x = 0, last_new = 0, curr_ht = 0;

    for (;!feof(stdin);) {
        int l, h, r;
        fscanf(stdin, "%d %d %d\n", &l, &h, &r);
        if (r > max_x)
            max_x = r;
        for (i = l; i <= r; i++)
            if (max_y[i] < h)
                max_y[i] = h;
    }
    max_x += 2;
    for (i = 0; i < max_x; i++) {
        j = max_y[i] - last_new;
        curr_ht += j;
        last_new = max_y[i];
        if (j > 0)
            printf("%d %d ", i, curr_ht);
        if (j < 0)
            printf("%d %d ", i - 1, curr_ht);
    }
    printf("\n");
}

Really straightforward C solution... 540 characters.

Reichard