The Nonary Game ist ein fiktives Spiel, das in der gleichnamigen Videospiel-Trilogie gespielt wird. Ihr Ziel ist es, in möglichst wenigen Byte Code herauszufinden, wie viele Spieler (bestenfalls) einem bestimmten Spiel entkommen können.

Spielregeln

• Es gibt 9 Spieler, nummeriert von 1 bis 9.
• Alle Spieler beginnen im selben Raum.
• Es gibt eine beliebige Anzahl von Türen mit einer Zahl von 1 bis 9. Möglicherweise sind doppelte oder fehlende Türnummern vorhanden.
• Tür sind Einweg Verbindungen zwischen den Räumen. Jede Tür kann nur einmal benutzt werden .
• Nur Gruppen von 3 bis 5 Spielern können eine Tür passieren.
• Eine Gruppe kann nur durch eine Tür gehen, wenn die Summe ihrer Zahlen modulo 9 mit der Zahl modulo 9 der Tür übereinstimmt.
• Jeder Spieler, der durch eine 9 Tür geht, entkommt (gewinnt).

Beispiele

┌───┬───┬───┐
│   6   4   9
│ < │   |   |
│   3   5   9
└───┴───┴───┘ 

<stellt den Ausgangspunkt dar. Alle Spieler beginnen dort.

In dieser Einstellung kann jeder entkommen. Es gibt verschiedene Möglichkeiten, dies zu erreichen. Eine davon ist:

• [1, 2, 3, 4, 5] gehen durch Tür 6 ((1 + 2 + 3 + 4 + 5)% 9 = 6), während [6, 7, 8, 9] durch Tür 3 ((6 + 7 + 8 + 9)% 9 = 3). Alle treffen sich im zweiten Raum.
• [1, 2, 3, 7] gehen durch Tür 4, während [4, 5, 6, 8, 9] durch Tür 5 gehen.
• [1, 2, 3, 4, 8] gehen durch eine der 9 Türen, [5, 6, 7, 9] gehen durch die andere.

┌───┬───┐
│   │   |
│ < 8   9
│   │   |
└───┴───┘ 

Diesmal können höchstens 4 Personen entkommen:

• [1, 3, 5, 8, 9] gehen durch Tür 8.
• [1, 3, 5, 9] durch Tür 9 gehen.

Andere Listen von Überlebenden wie [2, 3, 4] oder [1, 4, 6, 7] sind möglich, aber mehr als 4 Personen können nicht entkommen.

Die Herausforderung

Gib bei einer gegebenen Karte die maximale Anzahl von Spielern aus, die entkommen können.

• Keine Sorge, Sie müssen meine schrecklichen Diagramme nicht analysieren! Die Eingabe ist eine beschriftete gerichtete Grafik, die Sie in jedem geeigneten Format (Kantensatz, Adjazenzmatrix ...) darstellen können.
• Wenn für Ihre Darstellung Beschriftungen für Räume erforderlich sind, können Sie einen beliebigen Satz von Werten verwenden. Türen müssen jedoch durch die ganzen Zahlen 1 bis 9 dargestellt werden.
• Der Eingang hat immer mindestens eine 9 Tür. Alle 9 Türen führen immer zum Ausgang, während andere Türen dies niemals tun.
• Ihre Einreichung kann eine Funktion oder ein vollständiges Programm sein.
• Standardlücken sind verboten.

Testfälle

Eingänge werden als Listen von [Türnummer, von Raum zu Raum] Drillingen angezeigt, wobei 0 der Startraum und -1 der Ausgang ist. Wenn Sie sich für ein anderes Format entscheiden, müssen Sie diese entsprechend konvertieren.

Input                                                                      Output
[[6, 0, 1], [3, 0, 1], [4, 1, 2], [5, 1, 2], [9, 2, -1], [9, 2, -1]]       9
[[8, 0, 1], [9, 1, -1]]                                                    4
[[9, 0, -1]]                                                               5
[[2, 0, 1], [1, 1, 2], [9, 2, -1]]                                         0
[[2, 0, 1], [3, 1, 2], [9, 2, -1]]                                         3
[[1, 0, 1], [9, 1, -1], [1, 0, 2], [9, 2, -1]]                             4
[[2, 0, 1], [3, 0, 1], [5, 1, 2], [4, 0, 2], [9, 2, -1], [9, 2, -1]]       8
[[3, 0, 1], [4, 0, 1], [5, 0, 1], [9, 1, -1], [7, 1, 2], [9, 2, -1]]       7
[[1, 0, 1], [2, 0, 1], [4, 0, 1], [9, 1, -1], [8, 1, 2], [9, 2, -1]]       6
[[6, 0, 1], [7, 0, 1], [9, 1, -1], [9, 1, -1]]                             7

JavaScript (ES6), 219 Byte

Eine langsamere, aber deutlich kürzere Version, bei der Bitmasken anstelle von Zeichenfolgen verwendet werden.

f=(D,P=[511],e=m=0)=>P.map((X,r)=>[...Array(-~X)].map((_,p)=>D.map(([d,s,t],j)=>(N=(g=(n,k)=>n&&n%2+g(n>>1,++k,x+=n%2*k))(p&=X,x=0))<3|N>5|r-s|x%9^d%9||f(D.filter(_=>j--),A=[...P],e+!~t*N,A[r]^=p,A[t]^=p))),m=m>e?m:e)|m

Probieren Sie es online!

$X$$(X \operatorname{AND} p)$$0\le p\le X$

JavaScript (ES7),  293 272  271 Byte

Nimmt Eingaben in dem in der Challenge beschriebenen Format vor. Dies ist eine Brute-Force-Suche.

f=(D,P=[17**6+'8'],e=m=0)=>P.map((X,r)=>X&&[...X].reduce((a,x)=>[...a,...a.map(y=>y+x)],['']).map(p=>D.map(([d,s,t],j)=>p<99|p[5]|r-s|eval([...p].join`+`)%9^d%9||f(D.filter(_=>j--),A=[...P],e+!~t*p.length,A[r]=X.replace(eval(`/[${p}]/g`),''),A[t]=[A[t]]+p))),m=m>e?m:e)|m

Probieren Sie es online! (der erste Testfall läuft bei TIO ab)

Wie?

Das Array P[]enthält eine Liste von Zeichenfolgen, die die Spieler in jedem Raum beschreiben.

P=['241375698']$17^6=24137569$$0$

Für jeden Raum Xan der Position rberechnen wir die Potenz von X:

[...X].reduce((a, x) => [...a, ...a.map(y => y + x)], [''])

Für jede Gruppe von Spielern pdort und für jede Tür [d,s,t]am Index jtesten wir, ob die Gruppe nicht durch die Tür gehen kann:

                         // we can't pass if:
p < 99 |                 // there are less than 3 players
p[5] |                   // or there are more than 5 players
r - s |                  // or the source room s is not equal to the current room
eval([...p].join`+`) % 9 // or the sum of the players modulo 9
^ d % 9                  // does not match the ID of the door modulo 9

Wenn die Gruppe bestehen kann, führen wir einen rekursiven Aufruf durch:

f(                       //
  D.filter(_ => j--),    // remove the door that has just been used from D[]
  A = [...P],            // use a copy A[] of P[]
  e + !~t * p.length,    // if t = -1, add the length of p to e (number of escaped guys)
  A[r] = X.replace(      // remove the players from the source room A[r]
    eval(`/[${p}]/g`),   //
    ''                   //
  ),                     //
  A[t] = [A[t]] + p      // and append them to the target room A[t]
)                        //

Wir verfolgen die maximale Anzahl von entkommenen Spielern mund geben sie schließlich zurück.

Jelly , 76 Bytes

2ịịœc3r5¤ẎS,%9EʋƇ1ị${ḟ@;ƭⱮ€Ḋị¥ż€Ḋ{ṛṪ}¦ƒ€
ç@€Ẏ;ḷṢ€€Q
“”WẋḊ€FṀƊ9RW¤;Wçƒ@⁸ẈṪ$€Ṁ

Probieren Sie es online!

Ein vollständiges Programm, das ein einzelnes Argument verwendet, ein gerichteter Graph mit den Räumen 1, 2, ... und 0 als Ausgang. Gibt eine Ganzzahl zurück, bei der es sich um die maximale Anzahl handelt, die entweichen kann. Vollständige Erklärung folgt.

Sollte ohne die Ṣ€€Q4-Byte-Speicherung laufen , aber langsam ruhen.