Kürzere Version von Skyscrapers Challenge

Aufgabe

Suchen Sie bei einer Reihe von Gebäudehöhen und einer positiven Ganzzahl kalle Permutationen (ohne Duplikate) der Höhen so, dass genau kGebäude sichtbar sind.

Jedes Gebäude wird alle kürzeren oder gleich hohen Gebäude dahinter verstecken.

Jedes Format für Ein- und Ausgabe ist gültig.

Das Eingabearray wird niemals leer sein.

Falls es nicht möglich ist, genau so viele Gebäude zu sehen, geben Sie alles aus, was keine Antwort, aber keinen Fehler darstellen kann.

Beispiele:

(Die Länge der Ausgabe wird für sehr lange Ausgaben angezeigt, Ihre Ausgabe sollte jedoch alle möglichen Permutationen enthalten.)

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

Das ist Code-Golf, also gewinnt der kürzeste Code

Optional: Wenn möglich, können Sie so etwas hinzufügen if length is greater than 20: print length else print answer. In der Fußzeile, nicht im Code.

05AB1E , 10 9 Bytes

œÙʒη€àÙgQ

Probieren Sie es online aus oder überprüfen Sie (fast) alle Testfälle (Timeout des Testfalls [1,2,3,4,5,6,7,8,9],4).
Fußzeile der TIO macht was OP unten gefragt hat:

Optional: Wenn möglich, können Sie so etwas hinzufügen if length is greater than 20: print length else print answer. In der Fußzeile, nicht im Code.

Erläuterung:

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

Probieren Sie es online!

Gelee , 12 10 Bytes

Œ!Q»\QL=ʋƇ

Probieren Sie es online!

-2 Bytes von @Erik the Outgolfer

Dies ist eine dyadische Funktion, die die Gebäudehöhen und kdie Reihenfolge einhält.

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

Probieren Sie es hier aus .

Beachten Sie, dass die Online-Version des Pyth-Interpreters beim größten Testfall einen Speicherfehler auslöst.

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 dank nwellnhof!

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

Probieren Sie es online!

Anonymer Codeblock, der eingegangene Curry-Daten entgegennimmt, z f(n)(list). Das .unique(:with(*eqv*))ist aber ärgerlich lang:(

Erläuterung:

{;                                                            }  # 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

Probieren Sie es online!

Für die längeren Ausgaben addieren } l wird stattdessen die Länge ausgegeben am Ende wird. Der Online-Interpreter läuft für den [1,2,3,4,5,6,7,8,9],4Testfall aus, unabhängig von der Ausgabe der Länge oder der Liste.

Erläuterung:

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

Übernimmt die Eingabe als (k)(array). Druckt die Ergebnisse mit 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)

Probieren Sie es online!

Kommentiert

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*

Probieren Sie es online!

_{-1 Byte, danke an 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*

Probieren Sie es online!

J 43 38 Bytes

-5 Bytes nach Einbeziehung einer Optimierung aus Kevins O5AB13-Antwort

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

Probieren Sie es online!

ungolfed

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

Erläuterung

Wir i.@!@#@] A. ]listen lediglich alle möglichen Dauerwellen auf und nehmen Unikate davon mit~. und filtern diese nach der Anzahl der sichtbaren Gebäude, die der linken Eingabe entsprechen müssen.

Die Schlüssellogik befindet sich im Klammerverb, das die Anzahl der sichtbaren Gebäude berechnet:

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

Hier verwenden wir einen Max-Scan >./\, um eine Übersicht über das höchste Gebäude zu erhalten, das bisher gesehen wurde. Dann nehmen wir nur die einzigartigen Elemente des Max-Scans, und das ist die Anzahl der sichtbaren Gebäude.