Shorter version of Skyscrapers Challenge

Task

Given an array of building heights and a positive integer k, find all the permutations(without duplicates) of the heights such that exactly k buildings are visible.

Any building will hide all shorter or equal height buildings behind it.

Any format for input and output is valid.

Input array will never be empty.

In case it is not possible to see exactly as many buildings, output anything that cannot be an answer but no error.

Examples:

(Length of output is shown for very long outputs,but your output should be all possible permutations)

input:[1,2,3,4,5],2
output: 50

input:[5,5,5,5,5,5,5,5],2
output: []

input:[1,2,2],2
output:[(1,2,2)]
Seeing from the left, exactly 2 buildings are visible.

input:[1,7,4],2
output:[(4, 7, 1), (1, 7, 4), (4, 1, 7)]

input:[1,2,3,4,5,6,7,8,9],4
output:67284

input:[34,55,11,22],1
output:[(55, 34, 11, 22), (55, 22, 34, 11), (55, 34, 22, 11), (55, 11, 34, 22), (55, 22, 11, 34), (55, 11, 22, 34)]

input:[3,4,1,2,3],2
output:31

This is code-golf so shortest code wins

Optional: If possible, can you add something like if length is greater than 20: print length else print answer. In the footer, not in the code.

  • Should the output be all qualifying permutations, or the number thereof? – Luis Mendo Nov 15 at 6:49
  • It should be all qualifying permutations @LuisMendo – Vedant Kandoi Nov 15 at 6:54
  • Suggested test case: [1,2,3,4,5],5 -> [(1,2,3,4,5)]. None of the current test cases ensure that answers can support showing all buildings (though I don't know whether any actually have a problem with that). – Kamil Drakari Nov 15 at 15:27

05AB1E, 10 9 bytes

œÙʒη€àÙgQ

Try it online or verify (almost) all test cases (test case [1,2,3,4,5,6,7,8,9],4 times out).
Footer of the TIO does what OP asked at the bottom:

Optional: If possible, can you add something like if length is greater than 20: print length else print answer. In the footer, not in the code.

Explanation:

œ            # Permutations of the (implicit) input-list
             #  i.e. [1,2,2] → [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
 Ù           # Only leave the unique permutations
             #  i.e. [[1,2,2],[1,2,2],[2,1,2],[2,2,1],[2,1,2],[2,2,1]]
             #   → [[1,2,2],[2,1,2],[2,2,1]]
  ʒ          # Filter it by:
   η         #  Push the prefixes of the current permutation
             #   i.e. [1,2,2] → [[1],[1,2],[1,2,2]]
    ۈ       #  Calculate the maximum of each permutation
             #   i.e. [[1],[1,2],[1,2,2]] → [1,2,2]
      Ù      #  Only leave the unique maximums
             #   i.e. [1,2,2] → [1,2]
       g     #  And take the length
             #   i.e. [1,2] → 2
        Q    #  And only leave those equal to the second (implicit) input
             #   i.e. 2 and 2 → 1 (truthy)
  • 1
    Impressive, every single byte here is part of the function tree! – lirtosiast Nov 15 at 9:23
  • 1
    @lirtosiast Yeah, 05AB1E has some pretty short builtins sometimes, which were perfect in this challenge. :) It's actually very similar to your Pyth answer I see. Funny thing is, is that the footer for if length is greater than 20: print length; else print answer; is a̶ ̶b̶y̶t̶e̶ ̶l̶o̶n̶g̶e̶r̶ of equal length in comparison to the program itself. xD – Kevin Cruijssen Nov 15 at 9:25

Haskell, 73 bytes

import Data.List
f n=filter((n==).length.nub.scanl1 max).nub.permutations

Try it online!

Jelly, 12 10 bytes

Œ!Q»\QL=ʋƇ

Try it online!

-2 bytes by @Erik the Outgolfer

This is a dyadic function taking the building heights and k in that order.

Œ!                All permutations of first input
Œ!Q               Unique permutations of first input
   »\              Running maximum
     Q             Unique values
      L            Length of this array
       =           Equals k
        ʋ        Create a monad from these 4 links
   »\QL=ʋ        "Are exactly k buildings visible in arrangement x?"
         Ƈ     Filter if f(x)
Œ!Q»\QL=ʋƇ     All distinct perms of first input with k visible buildings.

Pyth, 18 16 bytes

fqvzl{meSd._T{.p

Try it here.

Note that the online version of the Pyth interpreter throws a memory error on the largest test case.

f                       Filter lambda T:
  q                       Are second input and # visible buildings equal?
    v z                     The second input value
    l {                     The number of unique elements in
        m                   the maximums
          e S d             ...
          ._ T              of prefixes of T
    { .p                  over unique permutations of (implicit first input)
  • Welcome back! :-) – Luis Mendo Nov 15 at 12:49

Perl 6, 81 63 bytes

-18 bytes thanks to nwellnhof!

{;*.permutations.unique(:with(*eqv*)).grep:{$_==set [\max] @_}}

Try it online!

Anonymous code block that takes input curried, e.g. f(n)(list). That .unique(:with(*eqv*)) is annoyingly long though :(

Explanation:

{;                                                            }  # Anonymous code block
  *.permutations.unique(:with(*eqv*))  # From all distinct permutations
                                     .grep:{                 }  # Filter where
                                                set [\max] @_   # Visible buildings
                                            $_==      # Equals num
  • 1
    FWIW, I just filed a Rakudo issue so we might get rid of that annoying ; eventually ;) – nwellnhof Nov 15 at 9:55

Japt, 11 bytes

á f_åÔâ Ê¥V

Try it online!

For the longer outputs, adding } l to the end will output the length instead. The online interpreter times out for the [1,2,3,4,5,6,7,8,9],4 test case, regardless of outputting the length or the list.

Explanation:

á              :Get all permutations
  f_           :Keep only ones where:
    åÔ         : Get the cumulative maximums (i.e. the visible buildings)
      â Ê      : Count the number of unique items
         ¥V    : True if it's the requested number

JavaScript (ES6), 108 107 bytes

Takes input as (k)(array). Prints the results with alert().

k=>P=(a,p=[],n=k,h=0)=>a.map((v,i)=>P(a.filter(_=>i--),[...p,v],n-(v>h),v>h?v:h))+a||n||P[p]||alert(P[p]=p)

Try it online!

Commented

k =>                        // k = target number of visible buildings
  P = (                     // P = recursive function taking:
    a,                      //   a[] = list of building heights
    p = [],                 //   p[] = current permutation
    n = k,                  //   n = counter initialized to k
    h = 0                   //   h = height of the highest building so far
  ) =>                      //
    a.map((v, i) =>         // for each value v at position i in a[]:
      P(                    //   do a recursive call:
        a.filter(_ => i--), //     using a copy of a[] without the i-th element
        [...p, v],          //     append v to p[]
        n - (v > h),        //     decrement n if v is greater than h
        v > h ? v : h       //     update h to max(h, v)
      )                     //   end of recursive call
    )                       // end of map()
    + a ||                  // unless a[] was not empty,
    n ||                    // or n is not equal to 0,
    P[p] ||                 // or p[] was already printed,
    alert(P[p] = p)         // print p[] and store it in P

Python 2, 114 113 bytes

lambda a,n:{p for p in permutations(a)if-~sum(p[i]>max(p[:i])for i in range(1,len(p)))==n}
from itertools import*

Try it online!

-1 byte, thanks to ovs


Python 3, 113 bytes

lambda a,n:{p for p in permutations(a)if sum(v>max(p[:p.index(v)]+(v-1,))for v in{*p})==n}
from itertools import*

Try it online!

J, 43 38 bytes

-5 bytes after incorporating an optimization from Kevin's O5AB13 answer

(]#~[=([:#@~.>./\)"1@])[:~.i.@!@#@]A.]

Try it online!

ungolfed

(] #~ [ = ([: #@~. >./\)"1@]) ([: ~. i.@!@#@] A. ])

explanation

we're merely listing all possible perms i.@!@#@] A. ], taking uniq items thereof with ~., then filtering those by the number of visible building, which must equal the left input.

the key logic is in the parenthetical verb which calcs the number of visible buildings:

([: #@~. >./\)

Here we use a max scan >./\ to keep a tally of the tallest building seen so far. Then we just take the unique elements of the max scan, and that's the number of visible buildings.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.