天际线问题
我刚刚在UVA的在线裁判遇到这个小问题，并认为它可能是一个小代码高尔夫球的一个很好的候选人。
问题：
您将devise一个计划来帮助build筑师根据城市build筑物的位置绘制城市的天际线。 为了解决问题，所有的build筑物都是矩形的，并且共有一个共同的底部（他们build造的城市非常平坦）。 这个城市也被视为二维的。 build筑物由有序三元组（Li，Hi，Ri）指定 ，其中Li和Ri分别是build筑物i的左侧和右侧坐标，而Hi是build筑物的高度。
在下图中，build筑物左侧显示三元组
(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, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0
输出应该由描述天际线的vector组成，如上例所示。 在天际线vector（v1，v2，v3，… vn）中 ， vi使得i是偶数，表示水平线（高度）。 vi使得我是一个奇数，表示一个垂直线（x坐标）。 天际线向量应该代表所采取的“path”，例如，从最小x坐标开始的错误，并在所有定义天际线的行上水平和垂直行进。 因此天际线vector中的最后一个条目将是0.坐标必须用空格分隔。
如果我不计算所提供的（testing）build筑物的声明，并且包括所有空格和制表符，我的解决scheme是Python，长度为223个字符。
这里是浓缩的版本：
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
我想我没有犯任何错误，但如果是这样 – 随时批评我。
我没有太多的名声，所以我只付100美元的奖金 – 我很好奇，如果有人能够用不到80字的话来解决这个问题的话。 由cobbal张贴的解决scheme是101个字符长 ，目前是最好的一个。
我想，这80个字符是这种问题的病态限制。 他的46个字符的解答总让我吃惊 – 尽pipe我必须承认，我花了一些时间阅读他的解释，然后才部分地理解了他写的东西。
我刚刚开始学习J ，所以这里是我第一次尝试打高尔夫：
103 62 49
46个字符
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
尽pipe我确信有人真正熟悉这门语言可以把这个缩短很多
代码解释：
NB。 列出build筑物右边的数字
（[：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。 比较build筑物的左边界，然后乘以高度
（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。 应用于b的每一行，注意如何用0填充较短的条目
（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。 折叠查找最大值，稍后添加一个0到最后旋转，分配给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。 向右旋转1，然后与s进行比较以find高度变化的位置
s〜：_1 |。 小号
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所有差异的指标
I. s〜：_1 |。 小号
1 3 9 12 16 19 22 23 29
NB。 将每个指标与build筑物的高度进行配对
（，。{＆s）I. s〜：_1 |。 小号
1 11
3 13
9 0
...
NB。 最后把名单弄平
，（，。{＆s）I. s〜：_1 |。 小号
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
Python，89个字符，也使用三联的5001作弊：
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
用max(map(max,B))+1代替5001以允许（几乎）任意大的城市留下102个字符。
修订logging：
- John Pirie的评论中描述了两个字符
- 像MahlerFivebuild议的那样保存了一个字符
Python：115个字符
像OP一样，我不包括数据的声明，但是我正在计算空白。
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,
请注意，我使用OP提供的链接作为问题的确切定义。 例如，假设没有超过5000的build筑物坐标，并且所有的坐标都是正整数，我会作弊。 原来的post没有太严格的限制，在我看来这很有趣。
编辑 ：感谢John Pirie关于将列表构造折叠为打印循环的提示。 我怎么想那个？
编辑 ：我决定使用原始问题中给出的确切定义后，将range(1+max(zip(*D)[2]))更改为range(5001) 。 第一个版本将处理任意正整数的build筑物（假设它们都适合于记忆）。
编辑 ：意识到我是过于复杂的事情。 检查我的修订。
顺便说一句 – 我有一个预感，有一个更优雅，可能更短的方式来做到这一点。 有人打我！
一个176字节的WinXP .COM可执行文件：
vQoAgMYQjsKO2jPAM / + 5AIDzq7QLzSE8 / 751AXQDvoQB6DkAi / noNACL2egvACn5A / 87HXYCiR2D xwLi9eviM8mZ9 / VSQQvAdfeI + rQCzSG3LFqAwjC0As0h4vbD / 9Y8CnP6D7bI / 9Y8CnPwtACR9 + UD yOvxtAvNITz / dRO0CM0hLDDDtAHNITwadfW + kAHDM / YZ / 7cgrTn4dA + L + I1E / tHo6Jr / i8folf8L 9nXozSA =
Base64编码，我用这个网站来编码它 。 解码为.com文件。 程序读取标准input直到一个EOF（从控制台读取时是Ctrl-Z），然后将结果输出到标准输出。
编辑：源代码：
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
像往常一样编译，使用A86。
Python有133个字符 ，内存和时间效率高，对数据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
说明：
lambda x:(x,max([y for a,y,b in D if a<=x<b]or[0])
返回位置x的位置和高度。
现在遍历按sorted(zip(*D)[0]+zip(*D)[2])编译的sorting后的坐标列表，并在高度改变时输出。
第二个版本不如上述那样高效，并且有一个坐标限制，但是只使用115个字符 ：
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],
J的 98个字符，默认定义（无variables名！）：
,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0(([:<./{."1)}.[:i.@>:[:>./{:"1))
在行动：
$ jconsole
s：:, @（（[:( 1：，{：1）}。〜：}：）＃]）@（（]，[：> ./（1＆{@ [*（]>： （[：<./ {。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
假定最左边的坐标总是1，只有86个字符。
,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0([:>:[:i.[:>./{:"1))
只有76，另外假定最右边的坐标最多为99。
,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0&(>:i.99))
借用cobbal一些技巧，我可以得到它68。
[:,@({:"1#>:@i.@#,.{."1)[:1&|.[:(,.(~:_1&|.))[:>./(1&{*{.<:[:i.{:)"1
然而，默认的定义不能与使用s=:…来消除冗余。
每当我回答J的问题时，我都会花点时间来解释发生了什么事情，因为我认为其他人可能会喜欢看外语的运作。
NB。 vector的第一个，第二个和最后一个元素
（{.0 {b），（1 {0（b），（{：0 {b）
1 11 5
NB。 从0到（向量的最后一个元素）-1计数
一世。 {：0 {b
0 1 2 3 4
NB。 布尔：vector的第一个元素小于或等于（上面）？
（{。<：[：i。{:) 0 {b
0 1 1 1 1
NB。 vector的第二个元素相乘
（1＆{* {。<：[：i。{:) 0 {b
0 11 11 11 11
NB。 为每个vector叠加结果，然后按列查找最大值
> ./（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。 确定领导者并制作表格
|：（，。（〜：_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。 向左旋转
|：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的索引和第一个元素，当最后一个元素为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。 弄平
，（{：1＃>：@ i。@＃，。{。1）1＆|。（，。（〜：_1＆|。））> ./（1＆ {:)“1 b
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
NB。 为默认动词重新排列
（[：@（{： “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
2 C＃答案 – 太长了，但我希望看到更好？
LINQ方法（不包括数组行的135个字符）：
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)+", ");}
或者是一个非LINQ的答案（179185字符，不包括数组行）：
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])+", ");
代码是精简的（几行代码），这是比赛的好时间（时间是最稀缺的资源），似乎是正确的（我不知道python，但我想我明白了代码）。
您的解决scheme基本上绘制缓冲区中的城市天际线，然后以所需的格式输出缓冲区的内容。
你从这个问题中得到的额外信息是最多有5000个build筑物，水平位置将会小于10.000。 这意味着内存在你的情况下似乎不是一个问题（假设32位体系结构为40kb，build筑描述为45kb），可选地，可以在读取循环中绘制天际线。 该algorithm在build筑物数量上是线性的，因此速度很快。
有了更为严格的内存限制，您可以select单通道algorithm，但是我相信在这种情况下，执行速度会更慢，实现起来要复杂得多（更多的时间，更多的CPU时间）
现在，您应该考虑真正以给定的格式读取input，并将该数据用于计算，而不是预先存储的数据数组。
顺便说一句，python是一个有效的语言现在在ACM竞赛？
这是Perl中的一个简单的例子
（快点我的意思是不到两个小时）
Perl只有327个字符
（不包括“ #/ ”以改善突出显示）
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;
原始testing版本853个字符
#! /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;
初始缩小版本621个字符
（不包括“ #/ ”以改善突出显示）
#! /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来确保我获得了正确的数据，而且不同版本的工作方式也是一样的。
假设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)]
哈斯克尔：105个字符
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格式似乎是Haskell落后Python解决scheme的地方。 不得不使用额外的5个字符来写'main ='也没有帮助，但也许不应该包含它，如果C＃/ Java解决scheme的代码必须演示完整的程序，那么C＃/ Java解决scheme将是巨大的:)
Haskell：76个字符 （没有string格式化和没有主要）
hx=maximum$0:[y|(l,y,r)<-b,l<=x,x<r] print[(x,hx)|x<-[1..9999],hx/=h(x-1)]
回想一下原来的问题，它需要你从一个文件中读取input，所以我认为看看有多less个字符增加是很有趣的。
哈斯克尔：149个字符（完整的解决scheme）
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
以下是完整解决scheme的样子，尽可能使用更多的描述性variables名称和types签名。
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
这是我在Perl中的尝试。 其中有33个人物正在寻找天际线的尽头。
@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;}
重读UVA规则，我们不限于5000的最大X，而是5000个build筑物 。 允许X和Y值（包括）9999。
另外，显然只有C，C ++，C＃和Java是官方认可的语言，所以我在Java中进行了挖掘。 这些数字只有空格分开，但逗号可以放回去（总共需要两个字符）。 总共153个字符（不包括arrays行）：
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]+" ");
逻辑非常简单。 唯一让stream程变得有点不可思议的是variables重用和后置增量的非标准放置。 产生：
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
除了挑战。
结果集是否正确？ 在22号位置，最高点是18号，23号是13号，所以3号不是最高点。
我也试图做一个PHP版本，它给了我一个不同的最终载体。 它没有针对速度进行优化。
<?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 ); ?>
这返回：
Array ( [0] => 11 [2] => 13 [9] => 0 [11] => 7 [16] => 3 [18] => 18 [22] => 13 [29] => 0 )
这是拐点和最大高度。
ruby，80个字符
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)}
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 (yo) printf("%d %d ", x, y); } }
#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"); }
真正直截了当的C解决scheme… 540个字符。
即使这是一个旧的post，我想我会分享我的GNU八度实现137个字符：
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;
将三元组的任意大小matrix作为b
