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

Question

已锁定。这个问题及其答案是 locked因为这个问题是题外话，但却具有历史意义。目前不接受新的答案或互动。

我刚刚在 UVA's Online Judge 上遇到了这个小问题并认为它可能是进行一些 Code Golf 的良好候选者。

问题:

您将设计一个程序来协助建筑师根据城市中建筑物的位置绘制城市的天际线。为了使问题易于处理，所有建筑物的形状都是矩形的，并且它们共享一个公共(public)底部(它们所在的城市非常平坦)。城市也被视为二维的。建筑物由有序三元组 (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 characters long目前它是最好的一个。

我认为，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

尽管我确信真正熟悉该语言的人可以大大缩短这个时间

代码说明:

   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 b0 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  00  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 b0 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 |. s0 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 |. s1 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 |. s1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0