我刚刚在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表示水平线(高度).i是奇数的vi表示垂直线(x坐标).天际线矢量应该表示所采取的"路径",例如,从最小x坐标开始并在定义天际线的所有线上水平和垂直行进的bug.因此,天际线矢量中的最后一个条目将为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个角色解决方案让我感到惊讶 - 虽然我必须承认,我花了一些时间阅读他的解释,然后才部分理解他所写的内容.
1> cobbal..：
我刚刚开始学习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
是否有任何非深奥的语言不如此可读？;-)
我很敬畏你的解决方案有多短(但我还没有看到解释).很遗憾J不是提交解决方案的合格语言; 我想知道你将如何列入该问题的排名列表.
2> balpha..：
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
更换5001通过max(map(max,B))+1允许(几乎)任意大城市留下102个字符.
修订记录:
如John Pirie的评论所述,保存了两个字符
MahlerFive建议保存一个字符
我很敬畏.将"L 使用分号在保存1个字符的同一行上有o = n和x + = 1
3> Triptych..：
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
请注意,我使用OP提供的链接作为问题的确切定义.例如,假设没有建立超过5000的坐标,并且所有坐标都是正整数,我会作弊.在我看来,原始帖子没有足够严格的限制,因此这很有趣.
编辑:感谢John Pirie关于将列表构造折叠到打印循环中的提示.我怎么想念那个？!
编辑:我改变了range(1+max(zip(*D)[2]))对range(5001)决定使用后准确的原始问题给出定义.第一个版本将处理任意正整数的建筑物(假设它们都适合内存).
编辑:意识到我过度复杂了.检查我的修订版.
顺便说一句 - 我有一种预感,有一种更优雅,也可能更短的方式来做到这一点.有人打败了我!
4> Skizz..：
一个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文件.程序读取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进行编译.
啊,我接管ze vorld的邪恶计划被挫败了.是时候用激光释放鲨鱼了!
我怎么知道这不是特洛伊木马;-)
5> Otto Allmend..：
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
说明:
lambda x:(x,max([y for a,y,b in D if a<=x
返回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)
6> ephemient..：
J的 98个字符,默认定义(无变量名!):
,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0(([:<./{."1)}.[:i.@>:[:>./{:"1))
在行动:
$ jconsole
s =: ,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0(([:<./{."1)}.[:i.@>:[:>./{:"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
假设最左边的坐标始终为1,只有86个字符.
,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0([:>:[:i.[:>./{:"1))
只有76,另外假设最右边的坐标最多为99.
,@(([:(1:,{:"1)}.~:}:)#])@((],[:>./(1&{@[*(]>:{.@[)*]<{:@[)"1)"2 0&(>:i.99))
借用cobbal的一些技巧,我可以把它变成68.
[:,@({:"1#>:@i.@#,.{."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#>:@i.@#,.{."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#>:@i.@#,.{."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> Marc Gravell..：
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(++ib[j])b[j]=z;i=-1;z=0;while(++i<5000)if(b[i]!=z)Console.Write(i+", "+(z=b[i])+", ");
京公网安备 11010802040832号