天际线问题‍​​

Question

我刚刚在UVA在线法官上遇到了这个小问题，我想，它可能是一个很好的候选代码-高尔夫。

问题：

你要设计一个程序，帮助建筑师绘制城市的天际线，给出城市中建筑物的位置。为了使这个问题易于处理，所有的建筑物都是矩形的，它们有一个共同的底部(它们所建的城市非常平坦)。这座城市也被看作是二维的.建筑物由有序的三重(Li，Hi，Ri)指定，其中Li和Ri分别是建筑物I的左坐标和右坐标，Hi是建筑物的高度。

​

​

在下面的图表中，建筑物以三倍的形式显示在左边。

(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 

输出应该由描述天际线的向量组成，如上面的例子所示。在天际线矢量(v1，v2，v3，.，使i是偶数的vi表示一条水平线(高度)。I为奇数的vi表示一条垂直线(x-坐标)。天际线向量应该表示“路径”，例如，一个bug从最小x坐标开始，在定义天际线的所有线上水平和垂直地移动。因此，天际线矢量中的最后一个条目将是0。坐标必须用空格分隔。

如果我不计算提供的(测试)建筑物的声明并包括所有空格和制表符，我的解决方案是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发布的解决方案是101个字符长，目前它是最好的解决方案。

我想，80个角色对于这种问题来说是一个病态的限制。cobbal的46个角色解决方案让我大吃一惊--尽管我必须承认，我花了一段时间阅读他的解释，然后我才部分理解了他写了什么。

Answer 1

Python，89个字符，也使用Triptych的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 n-o:print x,n,
 o=n;x+=1

将5001替换为max(map(max,B))+1以允许(几乎)任意大城市留下102个字符。

修订历史：

• 保存了两个字符，如约翰·皮里的评论所述
• 按照MahlerFive的建议保存一个字符

Answer 2

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的坐标，并且所有的坐标都是正整数，这就有点欺骗了。在我看来，最初的帖子并没有受到严格的限制，所以我认为这是一件有趣的事情。

编辑：感谢John关于将列表构造折叠为打印for循环的技巧。我怎么错过了？！

编辑：在决定使用原始问题中给出的确切定义之后，将range(1+max(zip(*D)[2]))更改为range(5001)。第一个版本将处理任意正整数的建筑物(假设它都符合内存)。

编辑：意识到我太复杂了。看看我的修改。

顺便说一下-我有个预感有人打我！

Answer 3

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编码，i 使用此站点对其进行编码。.解码为.com文件。程序读取stdin直到EOF，在从控制台读取时它是一个Ctrl，然后将结果输出到stdout。

编辑:源代码：

    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编译。