Проблема горизонта‍

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

The problem:

Вы должны разработать программу, чтобы помочь архитектору нарисовать горизонт города с учетом расположения зданий в городе. Чтобы решить проблему, все здания имеют прямоугольную форму и имеют общее дно (город, в котором они построены, очень плоский). Город также рассматривается как двухмерный. Здание обозначено упорядоченной тройкой(Li, Hi, Ri) гдеLi а такжеRi левая и правая координаты, соответственно, здания I и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-координаты и проходящая по горизонтали и вертикали по всем линиям, которые определяют горизонт. Таким образом, последняя запись в векторе горизонта будет равна 0. Координаты должны быть отделены пробелом.

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

Вот сокращенная версия:

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

 MatrixFrog01 июл. 2009 г., 06:03
Мне нравится пытаться понять, как это работает. Одно небольшое наблюдение. От второй до последней строки можно написать: print & quot;% s% s & quot; % (x, V),
 Victor30 июн. 2009 г., 23:49
это должно быть вики?
 artificialidiot01 июл. 2009 г., 00:09
Это было мое первое годовое задание, которое должно быть реализовано в схеме.
 Brad Gilbert08 июл. 2009 г., 05:33
Точки данных для двух изображений не совпадают.( They do however match the image that it goes along with. )
 J-16 SDiZ03 июл. 2009 г., 06:15
Привет! Вы портите удовольствие от игры в UVa Judge!

Ответы на вопрос(17)

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

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

возвращает позицию и высоту в позиции х.

Теперь переберите отсортированный список координат, составленныйsorted(zip(*D)[0]+zip(*D)[2]) и вывод, если высота меняется.

вторая версия не так эффективна, как предыдущая, и имеет предел координат, но использует только115 chars:

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],
 02 июл. 2009 г., 17:42
спасибо триптих, только что заметил
 02 июл. 2009 г., 17:38
Вы можете связать операторы неравенства в Python. Изменить "a & lt; = x и x & lt; b" to "a & lt; = x & lt; b".
 02 июл. 2009 г., 17:52
Извините - мне пришлось пересмотреть мое решение после того, как вы меня избили!

Apart from the challenge.

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

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

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

vQoAgMYQjsKO2jPAM/+5AIDzq7QLzSE8/751AXQDvoQB6DkAi/noNACL2egvACn5A/87HXYCiR2D xwLi9eviM8mZ9/VSQQvAdfeI+rQCzSG3LFqAwjC0As0h4vbD/9Y8CnP6D7bI/9Y8CnPwtACR9+UD yOvxtAvNITz/dRO0CM0hLDDDtAHNITwadfW+kAHDM/Yz/7cgrTn4dA+L+I1E/tHo6Jr/i8folf8L 9nXozSA=

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

 09 июл. 2009 г., 00:38
Откуда я знаю, что это не троян ;-)
 09 июл. 2009 г., 17:50
Вы получили чертовски акулы с уродом лазеры на головах ... это так круто
 09 июл. 2009 г., 09:57
Ах, мой злой план захватить мир был сорван. Время высвобождать акул с помощью лазеров!

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
 03 июл. 2009 г., 06:33
как молчаливое, очень хорошее объяснение тоже
Решение Вопроса

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
 03 июл. 2009 г., 06:47
@Zifre: если есть требование, я могу написать подробное объяснение этого, как я сделал для своего решения J. Как только вы привыкнете к словарю J, это не так уж и плохо ... проблема в том, что они унаследовали APL ", для каждого возможного действия должен быть символ"; и заклинило его в ASCII.
 03 июл. 2009 г., 12:32
Я в восторге от того, насколько коротким является ваше решение (но я еще не прочитал объяснение). Стыдно, что J не является подходящим языком для подачи вашего решения; Интересно, как бы вы заняли место в списке для решения этой проблемы?
 03 июл. 2009 г., 03:05
Есть ли какой-нибудь неэзотерический язык, который менее читабелен, чем этот? ;-)
 03 июл. 2009 г., 08:47
Я действительно хотел бы получить подробное объяснение. После того как я увидел вашу первую версию, я скачал J и попытался создать свою собственную версию, но через две минуты у меня заболела голова ;-)
 03 июл. 2009 г., 00:09
Ах, если бы я видел ваши улучшения, я бы не написал свой ответ. Я не думал об использовании автозаполнения 0, это довольно умно ...

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

из которых 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;}
 10 июл. 2009 г., 09:16
Около 30 минут.
 10 июл. 2009 г., 00:25
Он даже короче моего: P Сколько времени у тебя ушло на создание?

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

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

Кроме того, по-видимому, только C, C ++, 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 

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

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

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

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

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

Кстати, является ли Python допустимым языком в конкурсах ACM?

 01 июл. 2009 г., 01:15
это не было в прошлом году.
 09 июл. 2009 г., 11:42
что случилось с Паскалем? они бросили это?
 01 июл. 2009 г., 07:29
Информация о данных испытаний важна. Если ваши координаты горизонта вместо 10 000 могут варьироваться до 2 ^ 32-1 (макс. 32-битное целое), тогда ваш алгоритм будет некорректным, так как для хранения переменной v потребуется 2 ^ 34 байта или 16 ГБ памяти (массив от 0 до 2 ^ 32-1 из 32-битных целых). То же самое относится и к зданиям, если бы число было достаточно большим, вам пришлось бы перестроить алгоритм в один проход. Это действительно важные элементы для оценки алгоритма, не только правильность, но и жизнеспособность реализации.
 01 июл. 2009 г., 05:02
Допустимые языки = Java, C, C ++, C #. Начиная с 2008 года, проблемы могут не иметь решения C #, написанного судьей.
 zeroDivisible01 июл. 2009 г., 06:05
TomatoSandwich прав - Python не является поддерживаемым языком для конкурсов ACM - я просто использовал его, потому что с его помощью я мог писать сжатый код. Я также пропустил информацию о тестовых примерах, потому что у SO нет средств для их автоматического предоставления, поэтому я предположил, что алгоритм, написанный для тестовых данных, будет работать для всех данных.

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

Лист регистраций изменений:

saved two chars as described in John Pirie's comment saved one char as MahlerFive suggested
 03 июл. 2009 г., 12:16
используйте точку с запятой, чтобы o = n и x + = 1 в одной строке, сохраняя 1 символ
 02 июл. 2009 г., 20:56
О да, спасибо. Это пережиток более ранней попытки, где у меня была для этого какая-то причина.
 02 июл. 2009 г., 20:53
Я в восторге. Изменить "L & lt; x + .5 & lt; R" to "L & lt; = x & lt; R" сохранить 2 символа?
 03 июл. 2009 г., 12:49
@MahlerFive: Круто. Честно говоря, я никогда раньше не использовал точку с запятой в Python. Если бы вы спросили меня, законно ли это, я бы точно не знал. Спасибо!
 02 июл. 2009 г., 21:51
большой поклонник (н-о). И я смеялся над собой за использование отступов трех пробелов. Прекрасная работа!

way слишком долго, но я бы хотел видеть лучше?

Подход 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])+", ");
 18 июл. 2009 г., 09:05
Ницца; не стесняйтесь взломать либо / оба в ;-p
 07 июл. 2009 г., 00:20
если ((у = a.Where (с = & ° С [0] & л; = х & Amp; & Amp; с [2] & GT; х) .MAX (с = & GT;? (целое) с [1]) ?? 0)! = L) экономит несколько символов
 18 июл. 2009 г., 04:46
& Quot; Console.Write & Quot; ахилловое исцеление от c # 'у вас есть 3 ссылки на [x, y] в последнем решении. замена на [x * 3 + y] стоит 6 символов, но a.GetLength (0) становится a.Length. первый [i * 3 + 0] может потерять th плюс ноль, поэтому вы можете сохранить только два символа. Вы можете поднять определение j туда, где вы определяете z.
 18 июл. 2009 г., 04:51
не уверен, если вы позволите себе var в не Linq версии, бреет один символ объявления b.
#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");
}

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

[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 чтобы убедиться, что я получаю правильные данные, и что разные версии работают одинаково.

Python: 115 characters

Как и 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,

Обратите внимание, что я использую ссылку, предоставленную ФП, в качестве точного определения проблемы. Например, я немного обманываю, предполагая, что координата здания не превышает 5000, и что все координаты являются положительными целыми числами. На мой взгляд, оригинальный пост недостаточно ограничен, чтобы быть веселым.

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

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

edit: Понял, что я усложнял вещи. Проверьте мои ревизии.

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

 01 июл. 2009 г., 08:42
Я не предполагаю, что здания будут перечислены в любом порядке.
 01 июл. 2009 г., 21:37
@Pirie, ссылка на исходную задачу, предоставленную OP, указывает, что все координаты здания являются положительными целыми числами. Я побежал с этим. Эта проблема будет намного менее интересной, если она не имеет четкого определения.
 01 июл. 2009 г., 07:52
я не так хорош в Python ... Вы предполагаете, что ввод будет в порядке, что они находятся в городской черте, или мне придется иметь дело с этим в моем коде?
 zeroDivisible01 июл. 2009 г., 06:10
Триптих, хороший ... действительно хороший.
 01 июл. 2009 г., 21:51
@Triptych: правильно, спасибо. Будучи студентом Python, изучающим тонну из вашего решения, я надеюсь, что вы простите меня, если я буду продолжать с ним связываться

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

Похоже, что форматирование строк - это то, где Haskell отстает от решений Python. Необходимость использовать дополнительные 5 символов, чтобы написать «main =» это тоже не поможет, но, возможно, его не следует включать, решения C # / Java были бы огромными, если бы их код должен был демонстрировать полную программу :)

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

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

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

Ниже показано, как выглядит полное решение с более описательными именами переменных и сигнатурами типов, где это возможно.

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

Ваш ответ на вопрос