The Skyline Problem‍

Question

I’m just starting to learn J, so here goes my first attempt at golf:

~~103 62 49~~
46 characters

   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

although I’m sure someone who actually knows the language well could shorten this by quite a bit

An explanation of the code:

   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

Leave a Comment Cancel reply