Skyline problem

I just stumbled upon this little problem at UVA Online Judge and thought it might be a good candidate for a little code golf.

Problem:

You must develop a program that helps the architect draw the city skyline based on the location of the buildings in the city. To make the problem acceptable, all buildings have a rectangular shape and have a common bottom (the city in which they are built is very flat). The city is also regarded as two-dimensional. The structure is defined by an ordered triple (Li, Hi, Ri) , where Li and Ri are the left and right coordinates of the building, and Hi is the height of the building.

alt text

In the diagram below, the 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 horizon 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 a vector that describes the horizon line, as shown in the example above. In the vector horizon (v1, v2, v3, ... vn) vi , so that I an even number represents a horizontal line (height). vi so i am an odd number is a vertical line (x-coordinate). The horizon vector should be a “path” taken, for example, by an error starting at the minimum x coordinate and moving horizontally and vertically along all the lines that define the horizon. Thus, the last record in the horizon vector must be 0. The coordinates must be separated by a space.

Unless I read the declaration of the provided (test) buildings and including all spaces and tabs, my solution in Python lasts 223 .

Here is the compressed 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 I was not mistaken, but if so, feel free to criticize me.

I don’t have a great reputation, so I’ll pay only 100 for generosity - I’m curious if anyone can try to solve this in less than ... say 80 characters. The solution submitted by cobbal is 101 characters long and is currently the best.

I thought that 80 characters is a sore point for this problem. cobbal , with its 46-character solution, struck me, although I have to admit that I read his explanation for a while before I partially understood what he wrote.

+51
code-golf rosetta-stone
Jun 30 '09 at 21:41
source share
17 answers

I'm just starting to learn J , so here is 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)Is~:_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 that someone who really knows the language can cut it a little

Code Explanation:

    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 0 3 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 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 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 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
+25
Jul 02 '09 at 9:15
source share

Python, 89 characters, also using the Triptych 5001 chip:

 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 no:print x,n, o=n;x+=1 

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

Change History:

  • two characters are stored, as described in a comment by John Peary.
  • one char saved as suggested by MahlerFive
+17
Jul 02 '09 at 18:33
source share

Python: 115 characters

Like the OP, I do not include the data declaration, but I consider spaces.

 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, 

Please note that I am using the link provided by OP as an exact definition of the problem. For example, I am fooling a little, suggesting that no coordinate greater than 5000 has been built, and that all coordinates are positive integers. The original post is not tough enough to be fun in my opinion.

edit : thanks to John Peary for the tip about folding the list design into the print loop. How did I miss this ?!

edit : I changed range(1+max(zip(*D)[2])) to range(5001) after determining whether to use the exact definition specified in the original task. The first version would process buildings with arbitrary positive integers (assuming that they all fit into memory).

edit . It was realized that I was too complicated. Check out my changes.

By the way. I have a hunch about a much more elegant and possibly shorter way to do this. Someone beat me!

+10
Jul 01 '09 at 2:58
source share

A 176 bytes 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 . Decoding to a .com file. The program reads stdin before EOF, which is Ctrl-Z when reading from the console, and then displays the result on stdout.

EDIT: 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.

+9
Jul 07 '09 at 15:24
source share

Python with 133 characters , memory and time efficient, no data entry restrictions

 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 height at position x.

Now let's move on to the sorted list of coordinates compiled by sorted(zip(*D)[0]+zip(*D)[2]) and print if the height changes.

the second version is not as effective as above, and has a coordinate limit, but uses only 115 characters :

 for x in range(100): E=[max([y for a,y,b in D if a<=(xi)<b]+[0])for i in(0,1)] if E[0]-E[1]:print x,E[0], 
+5
Jul 02 '09 at 15:21
source share

98 J characters, implicitly 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
    sb
 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 leftmost coordinate is always 1.

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

Only 76 with the additional assumption that the rightmost coordinate is not more than 99.

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

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

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

A close definition simply cannot compete using s=:… to eliminate redundancy.




Whenever I answer a question with J , I try not to rush to explain what is happening, because I think that others may like the work 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 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 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
+5
Jul 02 '09 at 22:02
source share

2 answers C # - the method is too long, but I would like to see better?

LINQ approach (135 characters without an array string):

 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 the answer is not LINQ (179 185 , except for the array string):

 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])+", "); 
+5
Jul 03 '09 at 9:27
source share

The code is compressed (a few lines for the code), which is good for a tournament (time is a discontinuous resource) and seems to be correct (I don't know python, but I think I understand the code).

Your solution basically draws the city skyline in a buffer, and then displays the contents of the buffer in the required format.

The additional information that you are saddened with from the problem is that there will be no more than 5,000 buildings, and horizontal positions will be less than 10,000. This means that memory does not seem to be a problem in your case (40kb for the horizon, which assumes a 32-bit architecture, plus 45kb for the description of the building - optional, you can draw a horizon line in the reading cycle). The algorithm is linear in the number of buildings, so it is fast.

With tight memory limits, you can go for a one-pass algorithm, but I believe that in this case it will work slower and be much more difficult to implement (more of your time, more CPU time)

Now you should think about really reading the input in this format and using this data for your calculations, and not for a pre-configured data array.

BTW, is python a valid language in ACM competitions?

+3
Jun 30 '09 at 10:30
source share

Here quick in perl

(by quick, I mean less than two hours)

Perl total 327 characters

(excluding " #/ " to improve selection)

 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; 

The original version for testing 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 mini version 621 characters

(excluding " #/ " to improve selection)

 #! /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 get the right data and that different versions work the same.

+3
Jul 08 '09 at 4:25
source share

Assuming 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

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

String formatting looks like Haskell lags behind Python solutions. The need to use an additional 5 characters for writing "main =" does not help either, but perhaps it should not be included, C # / Java solutions will be massive if their code was to demonstrate the complete program :)

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

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



Looking back at the original problem , you need to read the input from the file, so I thought it would be interesting to see how many characters are added.

Haskell: 149 characters (complete solution)

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

The following shows what the complete solution looks like with more descriptive variable names and signature types, 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 
+3
May 15 '10 at 11:26 a.m.
source share

Here is my attempt at Perl. 137 characters, of which 33 are for finding the end of the horizon.

 @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;} 
+2
Jul 6 '09 at 15:11
source share

Rereading the UVA rules, we are not limited to the maximum X 5000, but only 5000 buildings. Values ​​of X and Y are allowed up to (including) 9999.

Also, apparently, only C, C ++, C #, and Java are officially recognized languages, so I did it in Java. Numbers are separated by spaces, but commas can be returned (at the cost of two more common characters). Total number of 153 characters (excluding array string):

 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 simple. The only thing that makes the thread a little depressing is reuse and non-standard post-increment placement. Forms:

 1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0 
+2
Jul 06 '09 at 21:47
source share

Beyond the problem.

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

I also tried making a php version and this gives me a great 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 inflection points and the maximum height.

+2
Jul 08 '09 at 22:21
source share

ruby, 80 characters

 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)} 
+2
Apr 09 '11 at 18:30
source share

FROM

 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 (yo) printf("%d %d ", x, y); } } 
+2
Apr 09 2018-11-11T00:
source share
 #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"); } 

A really simple C ... 540 character solution.

+1
Jul 04 '11 at 3:25
source share

Despite the fact that this is an old post, it seemed to me that I would split my implementation of the gnu octave into 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; 

Skip any triples matrix as b

+1
May 30 '13 at 19:40
source share



All Articles