Versão mais curta do Skyscrapers Challenge

Tarefa

Dada uma variedade de alturas de construção e um número inteiro positivo k, encontre todas as permutações (sem duplicatas) das alturas de modo que exatamentek construções sejam visíveis.

Qualquer edifício ocultará todos os edifícios de altura menor ou igual atrás dele.

Qualquer formato para entrada e saída é válido.

A matriz de entrada nunca estará vazia.

Caso não seja possível ver exatamente o mesmo número de prédios, produza algo que não possa ser uma resposta, mas que não exista erro.

Exemplos:

(O comprimento da saída é mostrado para saídas muito longas, mas sua saída deve ser todas as permutações possíveis)

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

Isso é código-golfe, então o código mais curto ganha

Opcional: Se possível, você pode adicionar algo como if length is greater than 20: print length else print answer. No rodapé, não no código.

05AB1E , 10 9 bytes

œÙʒη€àÙgQ

Experimente online ou verifique (quase) todos os casos de teste (o [1,2,3,4,5,6,7,8,9],4tempo limite do caso de teste expira).
O rodapé do TIO faz o que o OP pediu na parte inferior:

Opcional: Se possível, você pode adicionar algo como if length is greater than 20: print length else print answer. No rodapé, não no código.

Explicação:

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

Experimente online!

Gelatina , 12 10 bytes

Œ!Q»\QL=ʋƇ

Experimente online!

-2 bytes por @Erik the Outgolfer

Esta é uma função diádica, tendo as alturas do edifício e knessa ordem.

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

Pitão, 18 16 bytes

fqvzl{meSd._T{.p

Experimente aqui .

Observe que a versão online do interpretador Pyth gera um erro de memória no maior caso de teste.

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 graças a nwellnhof!

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

Experimente online!

Bloco de código anônimo que recebe entrada com curry, por exemplo f(n)(list). Isso .unique(:with(*eqv*))é irritantemente longo, embora:(

Explicação:

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

Japonês , 11 bytes

á f_åÔâ Ê¥V

Experimente online!

Para saídas mais longas, adicionar } lao final produzirá o comprimento. O intérprete online atinge o tempo limite para o [1,2,3,4,5,6,7,8,9],4caso de teste, independentemente da saída do comprimento ou da lista.

Explicação:

á              :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 os resultados com 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)

Experimente online!

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*

Experimente online!

_{-1 byte, graças a 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*

Experimente online!

J, 43 38 bytes

-5 bytes após incorporar uma otimização da resposta de Kevin O5AB13

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

Experimente online!

destroçado

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

explicação

estamos apenas listando todas as permissões possíveis i.@!@#@] A. ], levando itens uniq dos ~.e filtrando-as pelo número de construções visíveis, que devem ser iguais à entrada esquerda.

a lógica da chave está no verbo entre parênteses que calcula o número de construções visíveis:

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

Aqui, usamos uma verificação máxima >./\para manter um registro do edifício mais alto visto até agora. Depois, pegamos os elementos exclusivos da verificação máxima, e esse é o número de construções visíveis.