Version plus courte de Skyscrapers Challenge

Tâche

Étant donné un tableau de hauteurs de bâtiment et un entier positif k, trouvez toutes les permutations (sans doublons) des hauteurs de telle sorte que les kbâtiments soient exactement visibles.

Tout bâtiment cachera tous les bâtiments plus courts ou de hauteur égale derrière lui.

Tout format d'entrée et de sortie est valide.

Le tableau d'entrée ne sera jamais vide.

Dans le cas où il n'est pas possible de voir exactement autant de bâtiments, sortez tout ce qui ne peut pas être une réponse mais pas d'erreur.

Exemples:

(La longueur de sortie est indiquée pour les sorties très longues, mais votre sortie doit être toutes les permutations possibles)

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

C'est le code-golf donc le code le plus court gagne

Facultatif: si possible, pouvez-vous ajouter quelque chose comme if length is greater than 20: print length else print answer. Dans le pied de page, pas dans le code.

05AB1E , 10 9 octets

œÙʒη€àÙgQ

Essayez-le en ligne ou vérifiez (presque) tous les cas de test (le cas de test expire [1,2,3,4,5,6,7,8,9],4).
Le pied de page du TIO fait ce que OP a demandé en bas:

Facultatif: si possible, pouvez-vous ajouter quelque chose comme if length is greater than 20: print length else print answer. Dans le pied de page, pas dans le code.

Explication:

œ            # 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)

Haskell, 73 octets

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

Essayez-le en ligne!

Gelée , 12 10 octets

Œ!Q»\QL=ʋƇ

Essayez-le en ligne!

-2 octets par @Erik the Outgolfer

Il s'agit d'une fonction dyadique prenant les hauteurs du bâtiment et kdans cet ordre.

Œ!                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 octets

fqvzl{meSd._T{.p

Essayez-le ici .

Notez que la version en ligne de l'interpréteur Pyth génère une erreur de mémoire sur le plus grand scénario de test.

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)

Perl 6 , 81 63 octets

-18 octets grâce à nwellnhof!

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

Essayez-le en ligne!

Bloc de code anonyme qui prend les entrées au curry, par exemple f(n)(list). C'est .unique(:with(*eqv*))énormément long cependant:(

Explication:

{;                                                            }  # Anonymous code block
  *.permutations.unique(:with(*eqv*))  # From all distinct permutations
                                     .grep:{                 }  # Filter where
                                                set [\max] @_   # Visible buildings
                                            $_==      # Equals num

Japt , 11 octets

á f_åÔâ Ê¥V

Essayez-le en ligne!

Pour les sorties plus longues, l'ajout } là la fin produira la longueur à la place. L'interprète en ligne arrive à expiration pour le [1,2,3,4,5,6,7,8,9],4scénario de test, indépendamment de la sortie de la longueur ou de la liste.

Explication:

á              :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 octets

Prend l'entrée comme (k)(array). Imprime les résultats avec 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)

Essayez-le en ligne!

Commenté

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 octets

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*

Essayez-le en ligne!

_{-1 octet, grâce aux ovs}

Python 3 , 113 octets

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*

Essayez-le en ligne!

J, 43 38 octets

-5 octets après avoir incorporé une optimisation à partir de la réponse O5AB13 de Kevin

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

Essayez-le en ligne!

non golfé

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

explication

nous listons simplement toutes les perms possibles i.@!@#@] A. ], en prenant leurs éléments uniq avec ~., puis en les filtrant par le nombre de bâtiments visibles, qui doit être égal à l'entrée gauche.

la logique clé est dans le verbe entre parenthèses qui calcule le nombre de bâtiments visibles:

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

Ici, nous utilisons un scan maximum >./\pour garder un décompte du plus haut bâtiment vu jusqu'à présent. Ensuite, nous prenons simplement les éléments uniques de l'analyse maximale, et c'est le nombre de bâtiments visibles.