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
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
Answer 2:
Python中，89个字符，也使用三联的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个字符。
修订记录：
挽救了两个字符，如约翰·皮里的评论描述
保存一个字符为MahlerFive建议
Answer 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,
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。
Answer 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])
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
share
edited Jul 3 '09 at 3:23
answered Jul 2 '09 at 22:02
ephemientephemient
157k31233361
like the tacit, very nice explanation too
– cobbal
Jul 3 '09 at 4:33
add a comment |
5
votes
2 C# answers - way too long, but I'd love to see better?
LINQ approach (135 chars excluding array line):
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)+", ");}
Or a non-LINQ answer (179 185 chars excluding array line):
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])+", ");
share
edited Jul 23 '09 at 10:49
ShuggyCoUk
32.7k66797
answered Jul 3 '09 at 9:27
Marc Gravell♦Marc Gravell
803k20121792584
if((y=a.Where(c=>c[0]<=x&&c[2]>x).Max(c=>(int?)c[1])??0)!=l) saves you a few characters
– Jimmy
Jul 6 '09 at 22:20
"Console.Write" c#'s achilles heal of golf :) You have 3 references to [x,y] in the latter solution. replacing with [x*3+y] costs 6 characters but a.GetLength(0) becomes a.Length. the first [i*3+0] can lose th plus zero though so you net save ywo characters. you can lift the definition of j to where you define z.
– ShuggyCoUk
Jul 18 '09 at 2:46
not sure if you allow yourself var in the non Linq version, shaves one character of the declaration of b.
– ShuggyCoUk
Jul 18 '09 at 2:51
Nice; feel free to hack either/both in ;-p
– Marc Gravell♦Jul 18 '09 at 7:05
add a comment |
3
votes
Code is condensed (few lines to code) which is good for the tournament (time is the scarcest resource), and seems correct (I don't know python, but I think I understand the code).
Your solution basically paints the city skyline in a buffer and then outputs the contents of the buffer in the required format.
The extra info you ommited from the problem is that there will be at most 5000 buildings and the horizontal positions will smaller than 10.000. That implies that memory does not seem a problem in your case (40kb for the skyline assuming 32bit architecture, plus 45kb for the building description - optional, you could paint the skyline in the read loop). The algorithm is linear in the number of buildings so it is fast.
With toughter memory constraints you could go for a one-pass algorithm, but I believe that in this case it would perform slower and be much more complex to implement (more of your time, more CPU time)
Now you should consider really reading the input in the given format and using that data for your computations instead of a prestored data array.
BTW, is python a valid language now in ACM contests?
share
answered Jun 30 '09 at 22:30
David Rodríguez - dribeasDavid Rodríguez - dribeas
176k16240439
it wasn't last year.
– Victor
Jun 30 '09 at 23:15
1
Valid Languages = Java, C, C++, C#. As of 2008, problems may not have a judge-written C# solution.
– glasnt
Jul 1 '09 at 3:02
2
TomatoSandwich is right - Python is not a supported language for ACM contests - I just used it, because with it, I could write condensed code. I also omitted information about test cases, because SO doesn't have means of providing them automatically, so I assumed, that algorithm written for test data will work for all data
– zeroDivisible
Jul 1 '09 at 4:05
2
The info about test data is important. If your skyline coordinates instead of ranging to 10.000 could range to 2^32-1 (max 32bit integer) then your algorithm would be flawed as it would require 2^34 bytes or 16Gb of memory to store the v variable (array from 0 to 2^32-1 of 32bit integers). The same goes for buildings, if the number was big enough you would have to refactor into a one-pass algorithm. Those are really important items to evaluate an algorithm, not only correctness but viability of the implementation.
– David Rodríguez - dribeas
Jul 1 '09 at 5:29
what happened with Pascal? have they dropped it?
– fortran
Jul 9 '09 at 9:42
|
show 3 more comments
3
votes
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)=@$s;
for$x($l..$r){$c=$p[$x];$p[$x]=$c>$y?$c:$y;}}
for($x=1;$x<=@p;$x++){$y=$p[$x]||0;
if(!defined$z){$l=$x;$z=$y;
}elsif($y!=$z){push@n,[$l,$z,$x-1];$z=$y;$l=$x;}}
push@n,[$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;
my@s=map{[split',',$_]}grep{$_}split/\)\s*(?:$|,\s*\()|^\s*\(/,<>; #/
my@p;
{
no strict; no warnings 'uninitialized';
for$s(@s){
($l,$y,$r)=@$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<=@p;$x++){
$y=$p[$x]||0;
if(!defined$z){
$l=$x;
$z=$y;
}elsif($y!=$z){
push@n,[$l,$z,$x-1];
$z=$y;
$l=$x;
}
}
push@n,[$l,$z];
}
say Dump \@s, \@p, \@n;
say join', ',map{($_->[0],$_->[1])}@n;
I used YAML to make sure I was getting the right data, and that the different versions worked the same way.
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)]
String formatting seems to be where Haskell falls behind the Python solutions. Having to use an extra 5 characters to write 'main=' doesn't help either, but perhaps it shouldn't be included, the C#/Java solutions would be massive if their code had to demonstrate the complete program :)
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)]
Looking back at the original problem it requires that you to read the input from a file, so I thought it would be interesting to see how many characters that adds.
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
Below is what the full solution looks like with more descriptive variable names and type signatures where possible.
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
It's even shorter than mine :P How long did this take you to create?
– Brad Gilbert
Jul 9 '09 at 22:25
About 30 minutes.
– Eric
Jul 10 '09 at 7:16
add a comment |
2
votes
Rereading the UVA rules, we're not limited to a max X of 5000, but rather 5000 buildings. X and Y values up to (and including) 9999 are allowed.
Also, apparently only C, C++, C#, and Java are officially recognized languages, so I did mine up in Java. The numbers are only space separated, but commas could be put back in (at a cost of two more total chars). Totalling 153 chars (excluding the array line):
The logic is pretty straightforward. The only things that make the flow a little wonky are variable reuse and nonstandard placement of post-increment. Generates:
1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0
share
answered Jul 6 '09 at 21:47
Matt PoushMatt Poush
1,307811
add a comment |
2
votes
Apart from the challenge.
Is the result set correct?
At position 22 the highest point is 18 and at 23 is 13, so 3 is not the highest point.
I also tried to make a php version and it gives me a diferent final vector. It is not optimized for speed.
{var%20f='http://v.t.sina.com.cn/share/share.php?appkey=1515056452',u=z||d.location,p=['&url=',e(u),'&title=',e(t||d.title),'&source=',e(r),'&sourceUrl=',e(l),'&content=',c||'gb2312','&pic=',e(p||'')].join('');function%20a(){if(!window.open([f,p].join(''),'mb',['toolbar=0,status=0,resizable=1,width=440,height=430,left=',(s.width-440)/2,',top=',(s.height-430)/2].join('')))u.href=[f,p].join('');};if(/Firefox/.test(navigator.userAgent))setTimeout(a,0);else%20a();})(screen,document,encodeURIComponent,'','','https://imgur.com/SnSjn.gif', '推荐 闹够了就滚 的文章《地平线问题(The Skyline Problem)》','https://www.manongdao.com/article-1013187.html','页面编码gb2312|utf-8默认gb2312'));){kind=link}