O jogo Nonary é um jogo fictício jogado na trilogia de videogame de mesmo nome. Seu objetivo é descobrir quantos jogadores (na melhor das hipóteses) podem escapar de um determinado jogo, com o mínimo de bytes de código possível.
Regras do jogo
- Existem 9 jogadores, numerados de 1 a 9.
- Todos os jogadores começam na mesma sala.
- Existem inúmeras portas, cada uma com um número de 1 a 9. Pode haver números de porta duplicados ou ausentes.
- Porta são conexões unidirecionais entre quartos. Cada porta pode ser usada apenas uma vez .
- Apenas grupos de 3 a 5 jogadores podem passar por uma porta.
- Um grupo só pode passar por uma porta se a soma dos seus números módulo 9 corresponder ao número da porta módulo 9.
- Qualquer jogador que passa por uma porta 9 escapa (ganha).
Exemplos
┌───┬───┬───┐
│ 6 4 9
│ < │ | |
│ 3 5 9
└───┴───┴───┘
<
representa o ponto de partida. Todos os jogadores começam por aí.
Nesse cenário, todos podem escapar. Existem várias maneiras de conseguir isso, uma das quais é:
- [1, 2, 3, 4, 5] passam pela porta 6 ((1 + 2 + 3 + 4 + 5)% 9 = 6), enquanto [6, 7, 8, 9] passam pela porta 3 ((6 + 7 + 8 + 9)% 9 = 3). Todo mundo se encontra na segunda sala.
- [1, 2, 3, 7] passam pela porta 4, enquanto [4, 5, 6, 8, 9] passam pela porta 5.
- [1, 2, 3, 4, 8] passam por uma das 9 portas, [5, 6, 7, 9] passam pela outra.
┌───┬───┐
│ │ |
│ < 8 9
│ │ |
└───┴───┘
Desta vez, no máximo 4 pessoas podem escapar:
- [1, 3, 5, 8, 9] passam pela porta 8.
- [1, 3, 5, 9] passam pela porta 9.
Outras listas de sobreviventes são possíveis, como [2, 3, 4] ou [1, 4, 6, 7], mas não há como escapar mais de quatro pessoas.
O desafio
Dado um mapa, produza o número máximo de jogadores que podem escapar.
- Não se preocupe, você não precisa analisar meus terríveis diagramas! A entrada é um gráfico direcionado rotulado, que você pode representar em qualquer formato conveniente (conjunto de arestas, matriz de adjacência ...).
- Se sua representação exigir rótulos para salas, você poderá usar qualquer conjunto consistente de valores. No entanto, as portas devem ser representadas pelos números inteiros 1 a 9.
- A entrada sempre terá pelo menos uma porta 9. Todas as 9 portas sempre levam à saída, enquanto outras nunca.
- Seu envio pode ser uma função ou um programa completo.
- As brechas padrão são proibidas.
Casos de teste
As entradas são mostradas como listas de trigêmeos [número da porta, de sala em sala], com 0 sendo a sala inicial e -1 sendo a saída. Se você optar por usar outro formato, precisará convertê-los adequadamente.
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
Respostas:
JavaScript (ES6), 219 bytes
Uma versão mais lenta, mas significativamente mais curta, usando máscaras de bits em vez de seqüências de caracteres.
Experimente online!
JavaScript (ES7),
293 272271 bytesRecebe entrada no formato descrito no desafio. Esta é uma pesquisa de força bruta.
Experimente online! (o primeiro caso de teste atinge o tempo limite no TIO)
Quão?
A matriz
P[]
contém uma lista de strings descrevendo os jogadores em cada sala.P=['241375698']
Para cada sala
X
na posiçãor
, calculamos o conjunto de potências deX
:Para cada grupo de jogadores
p
lá e para cada porta[d,s,t]
no índicej
, testamos se o grupo não consegue passar pela porta:Se o grupo puder passar, fazemos uma chamada recursiva:
Acompanhamos o número máximo de jogadores que escaparam
m
e, eventualmente, devolvemos.fonte
Geléia , 76 bytes
Experimente online!
Um programa completo usando um único argumento, um gráfico direcionado usando as salas 1, 2, ... e 0 como saída. Retorna um número inteiro que é o número máximo que pode escapar. Explicação completa a seguir.
Deve ser executado sem a
Ṣ€€Q
economia de 4 bytes, mas lento para descansar.fonte