Подтвердить что ты не робот

Проблема Skyline

Я только что наткнулся на эту небольшую проблему на UVA Online Judge и подумал, что это может быть хорошим кандидатом на небольшое кодовое гольф.

Проблема:

Вы должны разработать программу, помогающую архитектору рисовать горизонт города с учетом местоположения зданий в городе. Чтобы сделать проблему приемлемой, все здания имеют прямоугольную форму и имеют общую дно (город, в котором они построены, очень плоский). Город также рассматривается как двумерный. Строение задается упорядоченной тройкой (Li, Hi, Ri), где Li и Ri ​​ - это левая и правая координаты здания я и Hi - высота здания.

alt text

На приведенной ниже схеме здания показаны слева с тройками

(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) vi, так что я четное число представляет горизонтальную линию (высоту). 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-символьным решением меня поразило, хотя я должен признать, что я некоторое время читал его объяснение, прежде чем я частично понял, что он написал.

4b9b3361

ОТВЕТЫ

Ответ 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

хотя я уверен, что кто-то, кто действительно знает язык, может немного сократить его

Объяснение кода:

   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

Ответ 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 символа.

История изменений:

  • сохранено два символа, как описано в комментарии Джона Пири.
  • сохранен один char, как предложил MahlerFive

Ответ 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, и что все координаты - это целые положительные числа. Оригинальный пост не является достаточно жестким, чтобы это было весело, на мой взгляд.

edit: спасибо Джону Пири за подсказку о свертывании конструкции списка в цикл печати. Как я пропустил это?!

edit: я изменил range(1+max(zip(*D)[2])) на range(5001) после определения использования точного определения, указанного в исходной задаче. Первая версия обрабатывала бы здания с произвольными положительными целыми числами (предполагая, что все они вписываются в память).

edit. Реализовано, что я был слишком сложным. Проверьте мои изменения.

Кстати. У меня есть догадка о гораздо более элегантном и, возможно, более коротком способе сделать это. Кто-то избил меня!

Ответ 4

A 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 encoded, я использовал этот сайт для его кодирования. Декодирование в .com файл. Программа читает stdin до EOF, который является Ctrl-Z при чтении с консоли, а затем выводит результат на stdout.

EDIT: Исходный код:

    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.

Ответ 5

Python с 133 символами, память и время эффективны, никаких ограничений на ввод данных

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

Ответ 6

98 символов J, неявно определены (нет имен переменных!):

,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{[email protected][)*]<{:@[)"1)"2 0(([:<./{."1)}.[:[email protected]>:[:>./{:"1))

В действии:

$ jconsole
   s =: ,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{[email protected][)*]<{:@[)"1)"2 0(([:<./{."1)}.[:[email protected]>:[:>./{:"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

Только 86 символов с предположением, что самая левая координата всегда 1.

,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{[email protected][)*]<{:@[)"1)"2 0([:>:[:i.[:>./{:"1))

Только 76 с дополнительным допущением, что самая правая координата не более 99.

,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{[email protected][)*]<{:@[)"1)"2 0&(>:i.99))

Заимствуя некоторые трюки от коббала, я могу получить его до 68.

[:,@({:"1#>:@[email protected]#,.{."1)[:1&|.[:(,.(~:_1&|.))[:>./(1&{*{.<:[:i.{:)"1

Тесное определение просто не может конкурировать с использованием s=:…, чтобы устранить избыточность.

Всякий раз, когда я отвечаю на вопрос с J, я стараюсь не торопиться, чтобы объяснить, что происходит, потому что я думаю, что другим может понравиться работа инопланетного языка.

   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#>:@[email protected]#,.{."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#>:@[email protected]#,.{."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

Ответ 7

2 ответа С# - способ слишком длинный, но мне бы хотелось увидеть лучше?

Подход 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])+", ");

Ответ 8

Код сжимается (несколько строк для кода), что хорошо для турнира (время - это прерывный ресурс), и кажется правильным (я не знаю python, но я думаю, что понимаю код).

Ваше решение в основном рисует горизонт города в буфере, а затем выводит содержимое буфера в требуемом формате.

Дополнительная информация, которую вы опечалили из проблемы, состоит в том, что будет не более 5000 зданий, а горизонтальные позиции будут меньше 10.000. Это означает, что память не кажется проблемой в вашем случае (40kb для горизонта, предполагающей 32-битную архитектуру, плюс 45kb для описания здания - необязательно, вы можете рисовать линию горизонта в цикле чтения). Алгоритм является линейным по числу зданий, поэтому он быстро.

С жесткими ограничениями памяти вы можете пойти на однопроходный алгоритм, но я считаю, что в этом случае он будет работать медленнее и будет намного сложнее реализовать (больше вашего времени, больше времени процессора)

Теперь вам стоит подумать о том, чтобы действительно прочитать ввод в данном формате и использовать эти данные для ваших вычислений, а не для предварительно настроенного массива данных.

BTW, является ли python действующим языком в соревнованиях ACM?

Ответ 9

Здесь быстрый в Perl

(быстрым я имею в виду менее двух часов)

Perl всего 327 символов

(исключая " #/", чтобы улучшить выделение)

use 5.010;
$/=undef;
@s=map{[split',',$_]}grep{$_}split/\)\s*(?:$|,\s*\()|^\s*\(/,<>; #/
for$s(@s){($l,$y,$r)[email protected]$s;
for$x($l..$r){$c=$p[$x];$p[$x]=$c>$y?$c:$y;}}
for($x=1;$x<[email protected];$x++){$y=$p[$x]||0;
if(!defined$z){$l=$x;$z=$y;
}elsif($y!=$z){[email protected],[$l,$z,$x-1];$z=$y;$l=$x;}}
[email protected],[$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;

[email protected]=map{[split',',$_]}grep{$_}split/\)\s*(?:$|,\s*\()|^\s*\(/,<>; #/

[email protected];
{
  no strict; no warnings 'uninitialized';

  for$s(@s){
    ($l,$y,$r)[email protected]$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<[email protected];$x++){
    $y=$p[$x]||0;
    if(!defined$z){
      $l=$x;
      $z=$y;
    }elsif($y!=$z){
      [email protected],[$l,$z,$x-1];
      $z=$y;
      $l=$x;
    }
  }
  [email protected],[$l,$z];
}

say Dump \@s, \@p, \@n;

say join', ',map{($_->[0],$_->[1])}@n;

Я использовал YAML, чтобы убедиться, что получаю нужные данные и что разные версии работают одинаково.

Ответ 10

Предполагая ввод:

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. Необходимость использования дополнительных 5 символов для записи "main =" тоже не помогает, но, возможно, ее не следует включать, решения С#/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

Ответ 11

Здесь моя попытка в 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;}

Ответ 12

Перечитывая правила UVA, мы не ограничиваемся максимальным Х 5000, а всего 5000 зданий. Допускаются значения X и Y до (и в том числе) 9999.

Кроме того, по-видимому, только C, С++, С# и Java являются официально признанными языками, поэтому я сделал это на Java. Числа разделены пробелами, но запятые могут быть возвращены (при стоимости еще двух общих символов). Общее число 153 символов (исключая строку массива):

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

Логика довольно проста. Единственное, что делает поток немного удручающим, - это многократное повторное использование и нестандартное размещение пост-приращения. Формирует:

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

Ответ 13

Помимо проблемы.

Правильно ли установлен результат? В позиции 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
)

которые являются точками перегиба и максимальной высотой.

Ответ 14

рубин, 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)}

Ответ 15

С

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

Ответ 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");
}

Действительно простое решение C... 540 символов.

Ответ 17

Несмотря на то, что это старый пост, мне показалось, что я бы разделил свою реализацию октавы 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;

Пропустите любую матрицу размера троек как b