20

Das Videospiel Transistor verfügt über ein sehr interessantes Fähigkeitssystem. Sie sammeln 16 "Funktionen", die Sie in 16 verschiedenen Slots verwenden können. Interessant ist, dass es drei Arten von Slots gibt und sich jede Funktion anders verhält, je nachdem, in welchem Slot Sie sie verwenden:

Es gibt 4 Passive Slots .
Es gibt 4 aktive Slots .
Jeder aktive Steckplatz verfügt über 2 Upgrade-Steckplätze .

Wir möchten herausfinden, wie viele verschiedene Fähigkeiten uns zur Verfügung stehen.

Einige Kombinationen sind jedoch äquivalent. Insbesondere spielt die spezifische Position einer Funktion innerhalb jeder dieser Gruppen von Slots keine Rolle. Auf der anderen Seite, die Wirkung einer Funktion in einem Upgrade Slot ist , hängt von der spezifischen Funktion in dem übergeordneten aktiven Schlitz verwendet.

Daher sind die folgenden Kombinationen gleichbedeutend, wenn hexadezimale Ziffern verwendet werden, um für die Funktionen zu stehen:

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    2     0     1     3    # Permutation of passive slots.
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    0     1     2     3
Active Slots:     5     6     4     7    # Permutation of active slots together
Upgrade Slots:   A B   C D   8 9   E F   # with their upgrade slots.

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 9   B A   C D   F E   # Permutation within upgrade slots.

sowie eine beliebige Kombination dieser Umlagerungen. Beachten Sie, dass im dritten Fall die Upgrade-Slots zusammen mit den aktiven Slots ausgetauscht wurden, um den gleichen Gesamteffekt beizubehalten.

Andererseits unterscheiden sich die folgenden Kombinationen von der obigen Menge:

Passive Slots:    4     5     6     7    # Passive slots swapped
Active Slots:     0     1     2     3    # with active slots.
Upgrade Slots:   8 9   A B   C D   E F

Passive Slots:    0     1     2     3
Active Slots:     5     4     6     7    # Permutation of active slots without
Upgrade Slots:   8 9   A B   C D   E F   # changing upgrade slots.

Passive Slots:    0     1     2     3
Active Slots:     4     5     6     7
Upgrade Slots:   8 A   9 B   C D   E F   # Permutation between different upgrade slots.

Nach meiner Zählung ergeben sich 2.270.268.000 mögliche (funktional unterschiedliche) Kombinationen, sofern alle Funktionen verwendet werden.

Wenn Sie weniger als 16 Funktionen zur Verfügung haben, bleiben einige der Steckplätze leer. Beachten Sie jedoch, dass Sie keine Funktion in einem Upgrade-Slot platzieren können, wenn der übergeordnete aktive Slot leer ist.

Die Herausforderung

Sie müssen die Anzahl der möglichen Konfigurationen in Abhängigkeit von der Anzahl Ihrer Funktionen bestimmen. Darüber hinaus verallgemeinere ich das Problem ein wenig, indem ich die Anzahl der Slots variabel mache, um triviale Hardcoding-Lösungen zu vermeiden.

Schreiben Sie ein Programm oder eine Funktion, die mit zwei positiven ganzen Zahlen M ≥ 1und 1 ≤ N ≤ 4Munter der Annahme, dass genau Nunterschiedliche Funktionen verwendet werden , die Anzahl der möglichen (funktional unterschiedlichen) Fähigkeiten bestimmt , um so viele MPassiv-, MAktiv- und 2MUpgrade-Slots wie möglich zu füllen .

Sie können ein Programm oder eine Funktion schreiben, indem Sie eine Eingabe über STDIN (oder die nächstgelegene Alternative), ein Befehlszeilenargument oder ein Funktionsargument vornehmen und das Ergebnis über STDOUT (oder die nächstgelegene Alternative), einen Funktionsrückgabewert oder einen Funktionsparameter (out) ausgeben.

Ihr Code muss in der Lage sein, Eingaben bis einschließlich M = 8einer Minute auf einem vernünftigen Desktop-Computer zu verarbeiten. Dies hat zwar einen gewissen Spielraum, sollte aber Brute-Force-Lösungen ausschließen. Grundsätzlich sollte es kein Problem sein, diese Eingaben in weniger als einer Sekunde zu lösen.

Dies ist Code Golf, die kürzeste Antwort (in Bytes) gewinnt.

Testfälle

Jeder Testfall liegt im Formular vor M N => Result.

1 1 => 2
1 2 => 4
1 3 => 9
1 4 => 12
2 1 => 2
2 2 => 6
2 3 => 21
2 4 => 78
2 5 => 270
2 6 => 810
2 7 => 1890
2 8 => 2520
3 1 => 2
3 2 => 6
3 3 => 23
3 4 => 98
3 5 => 460
3 6 => 2210
3 7 => 10290
3 8 => 44520
3 9 => 168840
3 10 => 529200
3 11 => 1247400
3 12 => 1663200
4 1 => 2
4 2 => 6
4 3 => 23
4 4 => 100
4 5 => 490
4 6 => 2630
4 7 => 14875
4 8 => 86030
4 9 => 490140
4 10 => 2652300
4 11 => 13236300
4 12 => 59043600
4 13 => 227026800
4 14 => 718918200
4 15 => 1702701000
4 16 => 2270268000
5 1 => 2
5 2 => 6
5 3 => 23
5 4 => 100
5 5 => 492
5 6 => 2672
5 7 => 15694
5 8 => 98406
5 9 => 644868
5 10 => 4306932
5 11 => 28544670
5 12 => 182702520
5 13 => 1101620520
5 14 => 6122156040
5 15 => 30739428720
5 16 => 136670133600
5 17 => 524885961600
5 18 => 1667284819200
5 19 => 3959801445600
5 20 => 5279735260800
6 1 => 2
6 2 => 6
6 3 => 23
6 4 => 100
6 5 => 492
6 6 => 2674
6 7 => 15750
6 8 => 99862
6 9 => 674016
6 10 => 4787412
6 11 => 35304654
6 12 => 265314588
6 13 => 1989295308
6 14 => 14559228684
6 15 => 101830348620
6 16 => 667943115840
6 17 => 4042651092480
6 18 => 22264427465280
6 19 => 110258471363040
6 20 => 484855688116800
6 21 => 1854067032417600
6 22 => 5894824418683200
6 23 => 14025616720315200
6 24 => 18700822293753600
7 1 => 2
7 2 => 6
7 3 => 23
7 4 => 100
7 5 => 492
7 6 => 2674
7 7 => 15752
7 8 => 99934
7 9 => 676428
7 10 => 4849212
7 11 => 36601554
7 12 => 288486132
7 13 => 2349550632
7 14 => 19504692636
7 15 => 162272450340
7 16 => 1328431104000
7 17 => 10507447510560
7 18 => 78942848624640
7 19 => 554967220167360
7 20 => 3604592589998400
7 21 => 21411337810262400
7 22 => 115428212139240000
7 23 => 561247297649438400
7 24 => 2439121536313862400
7 25 => 9283622495827680000
7 26 => 29520583763711040000
7 27 => 70328449554723360000
7 28 => 93771266072964480000
8 1 => 2
8 2 => 6
8 3 => 23
8 4 => 100
8 5 => 492
8 6 => 2674
8 7 => 15752
8 8 => 99936
8 9 => 676518
8 10 => 4852992
8 11 => 36722169
8 12 => 291621462
8 13 => 2418755196
8 14 => 20834571186
8 15 => 184894557705
8 16 => 1672561326150
8 17 => 15217247948760
8 18 => 137122338089880
8 19 => 1204392465876600
8 20 => 10153538495100000
8 21 => 81007229522419200
8 22 => 604136189949692400
8 23 => 4168645459350372000
8 24 => 26403795950145213600
8 25 => 152700324078982680000
8 26 => 803784718213396920000
8 27 => 3838761204861983400000
8 28 => 16503742828841748480000
8 29 => 62545434470667308160000
8 30 => 198853691115980300400000
8 31 => 474189571122722254800000
8 32 => 632252761496963006400000

Dies sind alle Eingaben, die Ihr Code innerhalb von einer Minute (jeweils) verarbeiten muss, sie sollten jedoch im Prinzip für größere Eingaben funktionieren. Sie können einige der folgenden M = 10Testfälle verwenden, um dies zu überprüfen:

10 1 => 2
10 2 => 6
10 3 => 23
10 4 => 100
10 5 => 492
10 6 => 2674
10 7 => 15752
10 8 => 99936
10 9 => 676520
10 10 => 4853104
10 11 => 36727966
10 12 => 291849866
10 13 => 2426074222
10 14 => 21033972388
10 15 => 189645995396
10 16 => 1773525588406
10 17 => 17155884420532
10 18 => 171073929494468
10 19 => 1750412561088334
10 20 => 18258387148774916
10 21 => 192475976310317700
10 22 => 2028834600633220380
10 23 => 21127206177119902860
10 24 => 214639961631544809360
10 25 => 2101478398293813739200
10 26 => 19602967930531817832000
10 27 => 172444768103233181556000
10 28 => 1417975382888905296456000
10 29 => 10820259026484304813416000
10 30 => 76213534343700480310584000
10 31 => 493916052421168703366040000
10 32 => 2941900199368102067135040000
10 33 => 16113144277547868007416960000
10 34 => 81222252655277786422930560000
10 35 => 376309102059179385262246080000
10 36 => 1589579966324953534441910400000
10 37 => 5981477408861097281112374400000
10 38 => 19005991357166148698688124800000
10 39 => 45381652832417130566255318400000
10 40 => 60508870443222840755007091200000

code-golf game combinatorics permutations Martin Ender
quelle

Müssen so viele Slots wie möglich ausgefüllt werden?

Feersum

7

Ich schätze, ich sollte lieber auf meine warten, turn()bevor ich help()dir get()eine Antwort load()ping()void()spark()crash()

gebe

@feersum Ja, alle NFunktionen werden verwendet.

Martin Ender

18

CJam (56 Bytes)

q~4@:Nm*:$_&{:+1$\-N),&},f{1$1$:+-\0-:(_e`0f=+++:m!:/}:+

Online-Demo

N $n$ $k$ mn $M$ $N$

$X$ $0 \le X \le M$ $N-X$ $\frac{N!}{X!(N-X)!}$ $N-X$ $M$ $3$

Partition nehmen $λ_0, λ_1, \ldots, λ_k$ $λ_0$ $λ_1$ $\frac{(N-X)!}{λ_0! λ_1! ... λ_k!}$ $λ_i = λ_j$ $μ_i$ 3 2 2 1 $μ_3 = 1$ $μ_2 = 2$ $μ_1 = 1$ $λ_i$ $λ_i$

Für jede Partition beträgt die Anzahl der Funktionsverteilungen

\frac{N!}{X! (λ_{0} - 1)! \dots (λ_{k} - 1)! μ_{1}! μ_{2}! μ_{3}!}

$\frac{N!}{X! (λ_0-1)! \ldots (λ_k-1)! μ_1! μ_2! μ_3!}$

Der obige Code berechnet die Partitionen nach dem gleichen Ansatz wie Dennis (offensichtlich und kurz, obwohl nicht sehr skalierbar) und verarbeitet dann jede Partition in ein Array, [N X λ_0-1 ... λ_k-1 μ_1 μ_2 μ_3]über das die Fakultätsfunktion angehoben und dann die Division gefaltet werden kann.

Peter Taylor
quelle

9

CJam, 74 67 Bytes

q~4@:Mm*:$L|{:+W$\-M),&},f{0-:F1@@{_m!\I-:Nm!/I(m!/*N}fI;Fm!Fe=/}:+

Ich habe alle Testfälle auf meinem Desktop-Computer mit dem Java-Interpreter überprüft . Dies dauerte 2,2 Sekunden für 1 ≤ M ≤ 8 und 3,5 Minuten für M = 10 .

Probieren Sie diese Geige im CJam-Interpreter aus oder überprüfen Sie die ersten 84 Testfälle gleichzeitig .

Idee

Grundsätzlich können wir jeden aktiven Steckplatz und die zugehörigen Upgrade-Steckplätze mit 0 , 1 , 2 oder 3 Funktionen belegen. Für 4M Slots insgesamt nehmen wir alle Vektoren V von {0, 1, 2, 3} ^M und filtern diejenigen heraus, für die Summe (V)> N (mehr Funktionen in nicht passiven Slots als Gesamtfunktionen verfügbar) oder Summe ( V) + M <N (nicht genügend passive Steckplätze für nicht aktive Funktionen). Wir sortieren und deduplizieren alle gehaltenen Vektoren, da die Reihenfolge der Slotfamilien nicht wichtig ist.

Mit N Funktionen und V = (x ₁ ,…, x _M ) Funktionen in den nicht passiven Teilen der Slotfamilien berechnen wir die Anzahl der Kombinationen wie folgt:

Wenn x ₁ = 0 ist , gibt es nur eine Möglichkeit für diese Steckplatzfamilie.

Wenn x ₁ = 1 , gibt es N Möglichkeiten, da wir N Funktionen haben und die Funktion in den aktiven Steckplatz gehen muss.

Wenn x ₁ = 2 ist , müssen wir eine Funktion im aktiven Slot und eine andere in einem Upgrade-Slot platzieren (es spielt keine Rolle, welche). Es gibt N Optionen für den aktiven Steckplatz und N-1 verbleibende Optionen für den Upgrade-Steckplatz, was insgesamt N (N-1) Kombinationen ergibt .

Wenn x ₁ = 3 , gibt es N Auswahlmöglichkeiten für den aktiven Steckplatz, N - 1 verbleibende Auswahlmöglichkeiten für den ersten Upgrade-Steckplatz und N - 2 für den zweiten Upgrade-Steckplatz. Da die Upgrade-Slots keine Reihenfolge haben, wird jede Kombination zweimal gezählt, sodass es N (N - 1) (N - 2) eindeutige Kombinationen gibt.

In jedem Fall gibt es N! / ((N - x ₁ )! × (x ₁ - 1)! Kombinationen für diese Familie.
Wir haben x ₁ Funktionen verbraucht , setzen Sie also N: = N - x ₁ und wiederholen Sie Schritt 1 für x ₂ , dann x ₃ usw.
Wenn V Duplikate enthält, hat das Produkt der obigen Ergebnisse alle Kombinationen mehrfach gezählt. Für jedes einzelne Element von V , wenn sie auftritt r mal in V gibt es r! äquivalente Arten, diese Slotfamilien anzuordnen, daher muss das Ergebnis von oben durch r geteilt werden! .
Das Endergebnis ist die Anzahl der eindeutigen Kombinationen für diesen V .

Um die Gesamtzahl der eindeutigen Kombinationen zu berechnen, müssen Sie nur die Summe der Ergebnisse für jedes V berechnen .

Code

q~        e# Read an evaluate all input from STDIN. Pushes M and N.
4@:M      e# Push 4, rotate the M, and formally save it in M.
m*        e# Push {0, 1, 2, 3}^M.
:$        e# Sort each vector.
L|        e# Perform set union with the empty list (deduplicates).
{         e# For each sorted vector:
  :+      e#   Compute the sum of its coordinates.
  W$\-    e#   Subtract the sum from N (bottom of the stack).
  M),&    e#   Push [0 ... M] and intersect.
},        e# If the intersection was not empty, keep the vector.
f{        e# For each kept vector, push N and V; then:
  0-:F    e#   Save the non-zero elements of V in F.
  1@@     e#   Push 1 (accumulator), and rotate N and F on top of it.
  {       e#   For each I in F:
    _m!   e#     Push I and push factorial(I).
    \I-:N e#     Subtract I from N and update N.
    m!/   e#     Divide factorial(N) (original N) by factorial(N) (updated N).
    I(m!/ e#     Divide the quotient by factorial(I - 1).
    *     e#    Multiply the accumulator by the resulting quotient.
    N     e#    Push N for the next iteration.
  }fI     e#
  ;       e#   Pop N.
  Fm!     e#   Push all non-unique permutations of F.
  Fe=     e#   Count the number of times F appears.
  /       e#   Divide the accumulator by the result.
}         e#
:+        e# Add all resulting quotients.

Dennis
quelle

Die Kombinatorik des Transistors