Versión más corta de Skyscrapers Challenge

Tarea

Dada una variedad de alturas de edificios y un número entero positivo k, encuentre todas las permutaciones (sin duplicados) de las alturas de modo que se vean exactamente los kedificios.

Cualquier edificio ocultará todos los edificios más cortos o de igual altura detrás de él.

Cualquier formato para entrada y salida es válido.

La matriz de entrada nunca estará vacía.

En caso de que no sea posible ver exactamente tantos edificios, envíe cualquier cosa que no pueda ser una respuesta pero no un error.

Ejemplos:

(La longitud de salida se muestra para salidas muy largas, pero su salida debe ser todas las permutaciones posibles)

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

Este es el código de golf, por lo que el código más corto gana

Opcional: si es posible, ¿puede agregar algo como if length is greater than 20: print length else print answer? En el pie de página, no en el código.

05AB1E , 10 9 bytes

œÙʒη€àÙgQ

Pruébelo en línea o verifique (casi) todos los casos de prueba (se [1,2,3,4,5,6,7,8,9],4agota el tiempo de espera).
El pie de página del TIO hace lo que OP pidió en la parte inferior:

Opcional: si es posible, ¿puede agregar algo como if length is greater than 20: print length else print answer? En el pie de página, no en el código.

Explicación:

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

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

Pruébalo en línea!

Jalea , 12 10 bytes

Œ!Q»\QL=ʋƇ

Pruébalo en línea!

-2 bytes por @Erik the Outgolfer

Esta es una función diádica que toma las alturas del edificio y ken ese orden.

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

Pruébalo aquí .

Tenga en cuenta que la versión en línea del intérprete Pyth arroja un error de memoria en el caso de prueba más grande.

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 bytes

-18 bytes gracias a nwellnhof!

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

Pruébalo en línea!

Bloque de código anónimo que toma la entrada al curry, por ejemplo f(n)(list). .unique(:with(*eqv*))Aunque eso es molestamente largo:(

Explicación:

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

Japt , 11 bytes

á f_åÔâ Ê¥V

Pruébalo en línea!

Para las salidas más largas, agregar } lal final generará la longitud en su lugar. El intérprete en línea agota el tiempo de espera para el [1,2,3,4,5,6,7,8,9],4caso de prueba, independientemente de la salida de la longitud o la lista.

Explicación:

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

Toma entrada como (k)(array). Imprime los resultados con 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)

Pruébalo en línea!

Comentado

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*

Pruébalo en línea!

_{-1 byte, gracias a los 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*

Pruébalo en línea!

J, 43 38 bytes

-5 bytes después de incorporar una optimización de la respuesta O5AB13 de Kevin

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

Pruébalo en línea!

sin golf

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

explicación

simplemente enumeramos todos los permisos posibles i.@!@#@] A. ], tomamos elementos únicos de los mismos ~.y luego los filtramos por el número de edificios visibles, que deben ser iguales a la entrada izquierda.

La lógica clave está en el verbo entre paréntesis que calcula el número de edificios visibles:

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

Aquí usamos un escaneo máximo >./\para mantener una cuenta del edificio más alto visto hasta ahora. Luego solo tomamos los elementos únicos del escaneo máximo, y esa es la cantidad de edificios visibles.