code-golf - 天际线问题​​​

Question

我刚刚在UVA 的 Online Judge上遇到了这个小问题，并认为它可能是一个小代码高尔夫的好候选人。

问题：

你要设计一个程序来帮助建筑师在给定城市建筑物位置的情况下绘制城市的天际线。为了使问题易于处理，所有建筑物都是矩形的，并且它们共享一个共同的底部（它们所在的城市非常平坦）。这座城市也被视为二维的。建筑物由有序三元组(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, ... vn)中，使 i 为偶数的vi表示水平线（高度）。使 i 为奇数的vi表示垂直线（x 坐标）。天际线矢量应该代表“路径”，例如，一个从最小 x 坐标开始并水平和垂直穿过定义天际线的所有线的错误。因此，天际线向量中的最后一个条目将是 0。坐标必须用空格分隔。

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

我想，对于这类问题，80 个字符是一个病态的限制。cobbal，他的 46 个字符的解决方案让我非常惊讶——尽管我必须承认，在我部分理解他所写的内容之前，我花了一些时间阅读他的解释。

Answer 1

我刚开始学习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)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

尽管我敢肯定，真正了解该语言的人可以将其缩短很多

代码说明：

   注意。列出建筑物右边界的数字
   ([: 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
   注意。比较建筑物的左边界，然后乘以高度
   (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
   注意。适用于 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
...
   注意。折叠找到最大值，在末尾添加一个 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
   注意。将 s 向右旋转 1，然后与 s 比较以查找高度变化的位置
   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
   注意。查找所有差异的索引
   I.s ~：_1 |。s
1 3 9 12 16 19 22 23 29
   注意。将每个索引与那里的建筑物高度配对
   (,. {&s) I. s ~: _1 |. s
 1 11
 3 13
 9 0
...
   注意。最后将列表展平
   , (,. {&s) I. s ~: _1 |. s
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Answer 2

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 3

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 Pirie 关于将列表构造折叠到打印 for 循环中的提示。我怎么会错过？！

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

编辑：意识到我把事情复杂化了。检查我的修订。

顺便说一句 - 我有一种预感，有一种更优雅，可能更短的方法来做到这一点。有人打我！

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.

Answer 5

133个字符的Python，内存和时间效率高，对数据输入没有限制

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])，如果高度发生变化则输出。

第二个版本不如上面那个高效，并且有坐标限制，但只使用115 个字符：

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

Answer 6

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])+", ");

Answer 8

代码很简洁（代码几行），这对比赛很有好处（时间是最稀缺的资源），而且看起来是正确的（我不知道 python，但我想我理解代码）。

您的解决方案基本上是在缓冲区中绘制城市天际线，然后以所需格式输出缓冲区的内容。

您从问题中省略的额外信息是最多有 5000 个建筑物，并且水平位置将小于 10.000。这意味着在您的情况下内存似乎不是问题（假设 32 位架构的天际线为 40kb，建筑描述为 45kb - 可选，您可以在读取循环中绘制天际线）。该算法在建筑物数量上是线性的，因此速度很快。

使用更严格的内存限制，您可以使用一次性算法，但我相信在这种情况下它会执行得更慢并且实现起来更复杂（更多的时间，更多的 CPU 时间）

现在您应该考虑真正以给定格式读取输入，并使用该数据进行计算，而不是使用预存储的数据数组。

顺便说一句，python 现在在 ACM 比赛中是一种有效的语言吗？

Answer 9

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.

Answer 10

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

Answer 11

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;}

Answer 12

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 

Answer 13

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.

Answer 14

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

Answer 15

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);
  }
}

Answer 16

#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.

Answer 17

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