code-golf - problema - teoria inflacionaria
El problema del horizonte (17)
Aquí hay uno rápido en Perl
(rápido me refiero a menos de dos horas)
Perl en solo 327 caracteres
(sin incluir " #/ " para mejorar el resaltado)
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;
Prueba original versión 853 caracteres
#! /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;
Caracteres iniciales de la versión 621 minificados
(sin incluir " #/ " para mejorar el resaltado)
#! /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;
YAML para asegurarme de que estaba obteniendo los datos correctos, y que las diferentes versiones funcionaban de la misma manera.
Acabo de enterarme de este pequeño problema en el juez en línea de UVA y pensé que podría ser un buen candidato para un pequeño golf de código.
El problema:
Debe diseñar un programa para ayudar a un arquitecto a dibujar el horizonte de una ciudad dadas las ubicaciones de los edificios en la ciudad. Para que el problema sea manejable, todos los edificios tienen forma rectangular y comparten un fondo común (la ciudad en la que están construidos es muy plana). La ciudad también se ve como bidimensional. Un edificio está especificado por un triple ordenado (Li, Hi, Ri) donde Li y Ri son las coordenadas izquierda y derecha, respectivamente, del edificio iy Hi es la altura del edificio.
En el diagrama a continuación, los edificios se muestran a la izquierda con 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)
y el horizonte, que se muestra a la derecha, está representado por la secuencia:
1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0
La salida debe consistir en el vector que describe el horizonte como se muestra en el ejemplo anterior. En el vector de horizonte (v1, v2, v3, ... vn) , el vi tal que i es un número par representa una línea horizontal (altura). El vi tal que i es un número impar representa una línea vertical (coordenada x). El vector del horizonte debe representar el "camino" tomado, por ejemplo, por un error que comienza en la coordenada x mínima y viaja horizontal y verticalmente sobre todas las líneas que definen el horizonte. Por lo tanto, la última entrada en el vector del horizonte será un 0. Las coordenadas deben estar separadas por un espacio en blanco.
Si no contaré la declaración de los edificios proporcionados (de prueba) e incluiré todos los espacios y tabuladores, mi solución, en Python, tiene 223 caracteres.
Aquí está la versión condensada:
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
Creo que no cometí ningún error, pero si es así, siéntete libre de criticarme.
No tengo mucha reputación, así que pagaré solo 100 por una recompensa. Tengo curiosidad, si alguien pudiera tratar de resolver esto en menos de ... digamos, 80 caracteres. La solución publicada por cobbal tiene 101 caracteres y actualmente es la mejor.
Pensé que los 80 caracteres son un límite de enfermedad para este tipo de problema. cobbal , con su solución de 46 caracteres me asombró por completo , aunque debo admitir que pasé un tiempo leyendo su explicación antes de entender parcialmente lo que había escrito.
2 respuestas C # - demasiado tiempo, pero me gustaría ver mejor?
Enfoque LINQ (135 caracteres excluyendo la línea de matriz):
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)+", ");}
O una respuesta que no sea LINQ (179 185 caracteres excluyendo la línea de matriz):
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])+", ");
98 caracteres de J , tácitamente definidos (¡sin nombres de variables!):
,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0(([:<./{."1)}.[:i.@>:[:>./{:"1))
En acción:
$ 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
Solo 86 caracteres con la suposición de que la coordenada más a la izquierda siempre es 1.
,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0([:>:[:i.[:>./{:"1))
Solo 76 con la suposición adicional de que la coordenada más a la derecha es como mucho 99.
,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0&(>:i.99))
Tomando prestados algunos trucos de cobbal, puedo llevarlo a 68.
[:,@({:"1#>:@i.@#,.{."1)[:1&|.[:(,.(~:_1&|.))[:>./(1&{*{.<:[:i.{:)"1
Sin embargo, la definición tácita simplemente no puede competir con el uso de s=:… para eliminar la redundancia.
Cada vez que respondo una pregunta con J , intento tomarme el tiempo para explicar lo que está sucediendo, porque creo que otros pueden disfrutar de una mirada sobre el funcionamiento de un idioma extraño.
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
Al releer las reglas de UVA, no estamos limitados a una X máxima de 5000, sino a 5000 edificios . Se permiten los valores X e Y hasta (e incluyendo) 9999.
Además, aparentemente solo C, C ++, C # y Java son lenguajes oficialmente reconocidos, así que hice mío en Java. Los números solo están separados por espacios, pero las comas podrían volver a colocarse (a un costo de dos caracteres más). Sumando 153 caracteres (excluyendo la línea de matriz):
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]+" ");
La lógica es bastante simple. Las únicas cosas que hacen que el flujo sea un poco inestable son la reutilización variable y la colocación no estándar del incremento posterior. Genera:
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
Aquí está mi intento en Perl. 137 caracteres, de los cuales 33 están dedicados a encontrar el final del horizonte.
@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;}
Asumiendo la entrada:
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 caracteres
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)]
El formato de cadena parece ser donde Haskell queda atrás de las soluciones de Python. Tener que usar 5 caracteres adicionales para escribir ''main ='' tampoco ayuda, pero quizás no debería incluirse, las soluciones C # / Java serían masivas si su código tuviera que mostrar el programa completo :)
Haskell: 76 caracteres (sin formato de cadena y sin principal)
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)]
Mirando hacia atrás en el problema original , requiere que lea la entrada de un archivo, por lo que pensé que sería interesante ver cuántos caracteres agrega.
Haskell: 149 caracteres (solución completa)
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
A continuación se muestra cómo se ve la solución completa con nombres de variables más descriptivos y firmas de tipos, siempre que sea posible.
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
Aunque esta es una publicación anterior, pensé que compartiría mi implementación de octava gnu en 137 caracteres:
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;
Pasar cualquier matriz de tamaño de triples como b
El código está condensado (pocas líneas para codificar) lo cual es bueno para el torneo (el tiempo es el recurso más escaso), y parece correcto (no conozco Python, pero creo que entiendo el código).
Su solución básicamente pinta el horizonte de la ciudad en un buffer y luego muestra el contenido del buffer en el formato requerido.
La información adicional que omite del problema es que habrá como máximo 5000 edificios y las posiciones horizontales serán más pequeñas que 10.000. Eso implica que la memoria no parece ser un problema en su caso (40kb para el horizonte asumiendo una arquitectura de 32 bits, más 45kb para la descripción del edificio; opcional, podría pintar el horizonte en el ciclo de lectura). El algoritmo es lineal en el número de edificios, por lo que es rápido.
Con restricciones de memoria más duras, podría optar por un algoritmo de una sola pasada, pero creo que en este caso sería más lento y mucho más complejo de implementar (más tiempo, más tiempo de CPU)
Ahora debería considerar leer realmente la entrada en el formato dado y usar esa información para sus cálculos en lugar de una matriz de datos prealmacenada.
Por cierto, ¿es python un lenguaje válido ahora en los concursos de ACM?
Estoy empezando a aprender J , así que aquí va mi primer intento de golf:
103 62 49
46 caracteres
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
aunque estoy seguro de que alguien que realmente conozca bien el lenguaje podría acortar esto un poco
Una explicación del código:
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
Python, 89 caracteres, también usando trucos 5001 de Triptych:
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
Reemplazar 5001 por max(map(max,B))+1 para permitir (casi) ciudades arbitrariamente grandes deja 102 caracteres.
Revisión histórica:
- salvó dos caracteres como se describe en el comentario de John Pirie
- guardado un carácter como sugirió MahlerFive
Un ejecutable WinXP .COM de 176 bytes:
vQoAgMYQjsKO2jPAM / + 5AIDzq7QLzSE8 / 751AXQDvoQB6DkAi / noNACL2egvACn5A / 87HXYCiR2D xwLi9eviM8mZ9 / VSQQvAdfeI + rQCzSG3LFqAwjC0As0h4vbD / 9Y8CnP6D7bI / 9Y8CnPwtACR9 + UD yOvxtAvNITz / dRO0CM0hLDDDtAHNITwadfW + kAHDM / Yz / 7cgrTn4dA + L + I1e / tHo6Jr / i8folf8L 9nXozSA =
Base64 codificado, utilicé este sitio para codificarlo . Decodificar a un archivo .com. El programa lee stdin hasta un EOF, que es Ctrl-Z cuando lee desde la consola, y luego envía el resultado a stdout.
EDITAR: El código fuente:
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
Compilado, como es habitual para mí, usando A86.
do
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);
}
}
rubí, 80 caracteres
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)}
Aparte del desafío.
¿El resultado es correcto? En la posición 22, el punto más alto es 18 y en 23 es 13, por lo que 3 no es el punto más alto.
También traté de hacer una versión de php y me da un vector final diferente. No está optimizado para la velocidad.
<?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 );
?>
esto vuelve:
Array
(
[0] => 11
[2] => 13
[9] => 0
[11] => 7
[16] => 3
[18] => 18
[22] => 13
[29] => 0
)
cuáles son los puntos de inflexión y la altura máxima.
Python con 133 caracteres , memoria y tiempo eficiente, sin restricciones en la entrada de datos
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
explicación:
lambda x:(x,max([y for a,y,b in D if a<=x<b]or[0])
devuelve la posición y la altura en la posición x.
Ahora recorra la lista ordenada de coordenadas compiladas por orden sorted(zip(*D)[0]+zip(*D)[2]) y publíquelas si la altura cambia.
la segunda versión no es tan eficiente como la anterior y tiene un límite de coordenadas, pero solo usa 115 caracteres :
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],
Python: 115 caracteres
Al igual que el OP, no incluyo la declaración de los datos, pero estoy contando los espacios en blanco.
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,
Tenga en cuenta que estoy utilizando el enlace proporcionado por el OP como la definición exacta del problema. Por ejemplo, hago trampa un poco al asumir que no hay coordenadas de construcción por encima de 5000, y que todas las coordenadas son números enteros positivos. La publicación original no está lo suficientemente restringida como para que sea divertida, en mi opinión.
editar : gracias a John Pirie por el consejo sobre el colapso de la construcción de la lista en el ciclo de impresión. ¿Cómo lo extrañé?
edit : Cambié el range(1+max(zip(*D)[2])) al range(5001) después de decidir el uso de la definición exacta dada en el problema original. La primera versión maneja edificios de enteros positivos arbitrarios (suponiendo que todo encaja en la memoria).
editar : me di cuenta de que estaba complicando las cosas. Revisa mis revisiones
Por cierto, tengo la corazonada de que hay una forma mucho más elegante y posiblemente más corta de hacerlo. ¡Alguien me ha vencido!
#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");
}
Solución C realmente sencilla ... 540 caracteres.