51

私は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, ... vn)において、i が偶数のviは水平線 (高さ) を表します。ｉが奇数のｖｉは縦線（ｘ座標）を表す。スカイライン ベクトルは、たとえばバグが最小の 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 文字の解決策には完全に驚かされました。認めざるを得ませんが、彼が書いた内容を部分的に理解する前に、彼の説明を読むのに時間がかかりました。

4

17 に答える 17

25

私はJを学び始めたばかりなので、ゴルフの最初の試みは次のとおりです。

103 624946
文字

   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

実際に言語をよく知っている人なら、これをかなり短縮できると思いますが

コードの説明：

   NB。建物の右端までの番号を一覧表示します
   （[：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。建物の左境界と比較してから、高さを掛けます
   （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。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
   NB。すべての違いのインデックスを見つける
   I. s〜：_1|。s
1 3 9 12 16 19 22 23 29
   NB。各インデックスをそこの建物の高さとペアにします
   （、。{＆s）I. s〜：_1|。s
 1 11
 3 13
 9 0
..。
   NB。そして最後にリストをフラット化します
   、（、。{＆s）I. s〜：_1|。s
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
于 2009-07-02T09:15:10.280 に答える
17

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

(ほぼ) 任意の大都市を許可するために5001byを置き換えると、102 文字が残ります。max(map(max,B))+1

改訂履歴:

  • ジョン・ピリーのコメントで説明されているように、2文字を保存しました
  • MahlerFiveが提案したように1文字を保存しました
于 2009-07-02T18:33:34.630 に答える
10

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 を超える建物の座標はなく、すべての座標が正の整数であると仮定して、少しごまかしています。私の意見では、元の投稿は、これが楽しいほど厳密に制限されていません。

編集：リスト構造を印刷用ループに折りたたむことについてのヒントをくれたジョン・ピリーに感謝します。どうしてそれを逃したのですか？

編集：元の問題で指定された正確な定義を使用することを決定した後、に変更range(1+max(zip(*D)[2]))しました。最初のバージョンは、任意の正の整数の建物を処理します (すべてがメモリに収まると仮定)。range(5001)

編集：物事を複雑にしすぎていることに気づきました。私のリビジョンを確認してください。

ところで-これを行うには、はるかにエレガントで、おそらく短い方法があると思います。誰か私を殴って！

于 2009-07-01T02:58:25.900 に答える
9

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ファイルにデコードします。プログラムは、コンソールから読み取るときにCtrl-ZであるEOFまでstdinを読み取り、その結果を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を使用してコンパイルしました。

于 2009-07-07T15:24:03.973 に答える
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])次に、によってコンパイルされ、高さが変更された場合に出力される、ソートされた座標リストをループします。

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],
于 2009-07-02T15:21:31.507 に答える
5

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以外の回答（配列行を除く179 185文字）：

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])+", ");
于 2009-07-03T09:27:16.517 に答える
5
于 2009-07-02T22:02:57.130 に答える
3

入力を想定すると：

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文字

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

文字列のフォーマットは、HaskellがPythonソリューションに遅れをとっているところのようです。'main ='を書くために余分な5文字を使用する必要もありませんが、おそらくそれを含めるべきではありません。コードが完全なプログラムを実証する必要がある場合、C＃/Javaソリューションは大規模になります:)

Haskell：76文字 （文字列フォーマットなし、メインなし）

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

元の問題を振り返ると、ファイルから入力を読み取る必要があるので、追加される文字数を確認するのは興味深いと思いました。

Haskell：149文字（完全なソリューション）

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

以下は、可能な場合はより説明的な変数名と型署名を使用した完全なソリューションの外観です。

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
于 2010-05-15T11:26:51.337 に答える
3

これがPerlの簡単なものです

（迅速に私は2時間未満を意味します）

わずか327文字のPerl

 #/（強調表示を改善するために「」を除く）

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;

元のテストバージョン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を使用して、正しいデータを取得していること、および異なるバージョンが同じように機能することを確認しました。

于 2009-07-08T04:25:04.110 に答える
3

コードは凝縮されており (コードの行数が少ない)、トーナメントに適しています (時間が最も少ないリソースです)。

あなたのソリューションは、基本的に都市のスカイラインをバッファーに描画し、バッファーの内容を必要な形式で出力します。

問題から省略した追加情報は、最大で 5000 の建物があり、水平位置が 10.000 より小さいということです。これは、メモリが問題にならないように見えることを意味します (32 ビット アーキテクチャを想定したスカイライン用に 40kb、さらに建物の説明用に 45kb - オプションで、読み取りループでスカイラインをペイントできます)。アルゴリズムは建物の数に線形であるため、高速です。

メモリの制約が厳しい場合は、ワンパスアルゴリズムを使用できますが、この場合、パフォーマンスが低下し、実装がはるかに複雑になると思います (より多くの時間、より多くの CPU 時間)。

次に、指定された形式で入力を実際に読み取り、事前に保存されたデータ配列の代わりにそのデータを計算に使用することを検討する必要があります。

ところで、Python は現在 ACM コンテストで有効な言語ですか?

于 2009-06-30T22:30:30.073 に答える
2

これがPerlでの私の試みです。137文字、そのうち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;}
于 2009-07-06T15:11:23.053 に答える
2

チャレンジは別として。

結果セットは正しいですか? 位置 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
)

これは変曲点と最大高さです。

于 2009-07-08T22:21:26.367 に答える
2

ルビー、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)}
于 2011-04-09T18:30:11.973 に答える
2

ハ

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);
  }
}
于 2011-04-09T20:03:08.567 に答える
1 
#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 ソリューション... 540 文字。

于 2011-07-04T03:25:01.580 に答える