Nonary Game to fikcyjna gra rozgrywana w trylogii gier wideo o tej samej nazwie. Twoim celem jest ustalenie, ilu graczy (w najlepszym wypadku) może uciec z danej gry, przy jak najmniejszej liczbie bajtów kodu.

Zasady gry

• Jest 9 graczy, ponumerowanych od 1 do 9.
• Wszyscy gracze zaczynają w tym samym pokoju.
• Istnieje dowolna liczba drzwi, każda z liczbą od 1 do 9. Mogą istnieć duplikaty lub brakujące numery drzwi.
• Drzwi stanowią jednokierunkowe połączenia między pokojami. Każdych drzwi można użyć tylko raz .
• Tylko grupy od 3 do 5 graczy mogą przejść przez drzwi.
• Grupa może przejść przez drzwi tylko wtedy, gdy suma ich liczb modulo 9 odpowiada liczbie drzwi modulo 9.
• Każdy gracz, który przejdzie przez 9 drzwi, ucieka (wygrywa).

Przykłady

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

<reprezentuje punkt początkowy. Wszyscy gracze zaczynają od tego miejsca.

W tym otoczeniu każdy może uciec. Istnieją różne sposoby osiągnięcia tego celu, z których jeden to:

• [1, 2, 3, 4, 5] przechodzą przez drzwi 6 ((1 + 2 + 3 + 4 + 5)% 9 = 6), podczas gdy [6, 7, 8, 9] przechodzą przez drzwi 3 ((6 + 7 + 8 + 9)% 9 = 3). Wszyscy spotykają się w drugim pokoju.
• [1, 2, 3, 7] przechodzą przez drzwi 4, a [4, 5, 6, 8, 9] przechodzą przez drzwi 5.
• [1, 2, 3, 4, 8] przejdź przez jedne z 9 drzwi, [5, 6, 7, 9] przejdź przez drugie.

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

Tym razem maksymalnie 4 osoby mogą uciec:

• [1, 3, 5, 8, 9] przejdź przez drzwi 8.
• [1, 3, 5, 9] przejdź przez drzwi 9.

Możliwe są inne listy ocalałych, takie jak [2, 3, 4] lub [1, 4, 6, 7], ale nie ma możliwości ucieczki więcej niż 4 osób.

Wyzwanie

Podając mapę, wypisz maksymalną liczbę graczy, którzy mogą uciec.

• Nie martw się, nie musisz analizować moich okropnych diagramów! Dane wejściowe to nakierowany wykres, który można przedstawić w dowolnym dogodnym formacie (zestaw krawędzi, macierz przylegania ...).
• Jeśli Twoja reprezentacja wymaga etykiet dla pomieszczeń, możesz użyć dowolnego spójnego zestawu wartości. Jednak drzwi muszą być reprezentowane przez liczby całkowite od 1 do 9.
• Wejście zawsze będzie miało co najmniej jedne 9 drzwi. Wszystkie 9 drzwi zawsze prowadzą do wyjścia, podczas gdy inne drzwi nigdy nie.
• Twoje zgłoszenie może być funkcją lub pełnym programem.
• Standardowe luki są zabronione.

Przypadki testowe

Wejścia są pokazane jako listy trojetów [numer drzwi, z pokoju do pokoju], przy czym 0 oznacza pokój początkowy, a -1 wyjście. Jeśli zdecydujesz się użyć innego formatu, będziesz musiał odpowiednio je przekonwertować.

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 bajtów

Wolniejsza, ale znacznie krótsza wersja wykorzystująca maski bitowe zamiast łańcuchów.

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

Wypróbuj online!

Uwaga: Powodem, dla którego jest wolniejszy, jest to, że nie obliczamy zestawów mocy graczy. Biorąc pod uwagę maskę bitową graczy , iterujemy na wszystkich nazwa dla bez deduplikacji.$X$$(X \operatorname{AND} p)$$0\le p\le X$

JavaScript (ES7),  293 272  271 bajtów

Pobiera dane wejściowe w formacie opisanym w wyzwaniu. To jest poszukiwanie brutalnej siły.

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

Wypróbuj online! (limit czasu pierwszego przypadku testowego w TIO)

W jaki sposób?

Tablica P[]zawiera listę ciągów znaków opisujących graczy w każdym pokoju.

Zaczynamy od P=['241375698'](używając ), co oznacza, że ​​wszyscy gracze początkowo znajdują się w pokoju .$17^6=24137569$$0$

Dla każdego pomieszczenia Xna miejscu robliczamy zestaw mocy X:

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

Dla każdej grupy graczy ptam i dla każdych drzwi [d,s,t]o indeksie jsprawdzamy, czy grupa nie jest w stanie przejść przez drzwi:

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

Jeśli grupa może przejść, wykonujemy połączenie rekurencyjne:

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

Śledzimy maksymalną liczbę uciekających graczy mi ostatecznie ją zwracamy.

Galaretka , 76 bajtów

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

Wypróbuj online!

Pełny program przyjmujący pojedynczy argument, ukierunkowany wykres wykorzystujący pokoje 1, 2, ... i 0 jako wyjście. Zwraca liczbę całkowitą, która jest maksymalną liczbą, jaką można uciec. Pełne wyjaśnienie do naśladowania.

Powinien biec bez Ṣ€€Qoszczędzania 4 bajtów, ale wolno odpoczywa.