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

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

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

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