The Nonary Game es un juego ficticio que se juega en la trilogía de videojuegos del mismo nombre. Tu objetivo es encontrar cuántos jugadores (en el mejor de los casos) pueden escapar de un juego determinado, en el menor número de bytes posible.

Reglas del juego

• Hay 9 jugadores, numerados del 1 al 9.
• Todos los jugadores comienzan en la misma habitación.
• Hay cualquier número de puertas, cada una con un número de 1 a 9. Puede haber números de puerta duplicados o faltantes.
• Las puertas son conexiones unidireccionales entre habitaciones. Cada puerta solo se puede usar una vez .
• Solo grupos de 3 a 5 jugadores pueden pasar por una puerta.
• Un grupo solo puede pasar por una puerta si la suma de sus números módulo 9 coincide con el número de puerta módulo 9.
• Cualquier jugador que atraviese 9 puertas escapa (gana).

Ejemplos

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

<representa el punto de partida. Todos los jugadores comienzan allí.

En este entorno, todos pueden escapar. Hay varias formas de lograr esto, una de las cuales es:

• [1, 2, 3, 4, 5] pasa por la puerta 6 ((1 + 2 + 3 + 4 + 5)% 9 = 6), mientras que [6, 7, 8, 9] pasa por la puerta 3 ((6 + 7 + 8 + 9)% 9 = 3). Todos se encuentran en la segunda sala.
• [1, 2, 3, 7] pasan por la puerta 4, mientras que [4, 5, 6, 8, 9] pasan por la puerta 5.
• [1, 2, 3, 4, 8] pasa por una de las 9 puertas, [5, 6, 7, 9] pasa por la otra.

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

Esta vez, como máximo 4 personas pueden escapar:

• [1, 3, 5, 8, 9] pasa por la puerta 8.
• [1, 3, 5, 9] pasa por la puerta 9.

Son posibles otras listas de sobrevivientes, como [2, 3, 4] o [1, 4, 6, 7], pero no hay forma de que escapen más de 4 personas.

El reto

Dado un mapa, muestra el número máximo de jugadores que pueden escapar.

• ¡No te preocupes, no necesitas analizar mis horribles diagramas! La entrada es un gráfico dirigido etiquetado, que puede representar en cualquier formato conveniente (conjunto de bordes, matriz de adyacencia ...).
• Si su representación requiere etiquetas para habitaciones, puede usar cualquier conjunto de valores coherente. Sin embargo, las puertas deben estar representadas por los enteros 1 a 9.
• La entrada siempre tendrá al menos una puerta 9. Las 9 puertas siempre conducen a la salida, mientras que otras puertas nunca lo hacen.
• Su envío puede ser una función o un programa completo.
• Las lagunas estándar están prohibidas.

Casos de prueba

Las entradas se muestran como listas de tripletes [número de puerta, de sala a sala], siendo 0 la sala de inicio y -1 la salida. Si elige usar otro formato, tendrá que convertirlos adecuadamente.

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 bytes

Una versión más lenta pero significativamente más corta que usa máscaras de bits en lugar de cadenas.

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

Pruébalo en línea!

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

JavaScript (ES7),  293 272  271 bytes

Toma información en el formato descrito en el desafío. Esta es una búsqueda de fuerza bruta.

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

Pruébalo en línea! (el primer caso de prueba expira en TIO)

¿Cómo?

La matriz P[]contiene una lista de cadenas que describe a los jugadores en cada habitación.

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

Para cada habitación Xen la posición r, calculamos el conjunto de potencia de X:

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

Para cada grupo de jugadores pallí y para cada puerta [d,s,t]en el índice j, probamos si el grupo no puede pasar por la puerta:

                         // 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

Si el grupo puede pasar, hacemos una llamada recursiva:

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]
)                        //

Llevamos un registro del número máximo de jugadores escapados my eventualmente lo devolvemos.

Jalea , 76 bytes

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

Pruébalo en línea!

Un programa completo que toma un solo argumento, un gráfico dirigido que usa las habitaciones 1, 2, ... y 0 como salida. Devuelve un número entero que es el número máximo que puede escapar. Explicación completa a seguir.

Debe ejecutarse sin Ṣ€€Qun ahorro de 4 bytes pero lento para descansar.