The Nonary Game adalah gim fiksi yang dimainkan dalam trilogi video game dengan nama yang sama. Tujuan Anda adalah untuk menemukan berapa banyak pemain (yang terbaik) yang dapat lolos dari permainan yang diberikan, dalam kode sesedikit mungkin.

Aturan mainnya

• Ada 9 pemain, bernomor 1 hingga 9.
• Semua pemain mulai di ruangan yang sama.
• Ada sejumlah pintu, masing-masing dengan nomor 1 hingga 9. Mungkin ada nomor pintu rangkap atau hilang.
• Pintu adalah koneksi satu arah antara kamar. Setiap pintu hanya bisa digunakan satu kali .
• Hanya grup dengan 3 hingga 5 pemain yang bisa melewati satu pintu.
• Suatu kelompok hanya dapat melewati pintu jika jumlah dari angka-angka mereka modulo 9 cocok dengan nomor pintu modulo 9.
• Setiap pemain yang melewati pintu 9 lolos (menang).

Contohnya

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

<mewakili titik awal. Semua pemain mulai dari sana.

Dalam pengaturan ini, semua orang bisa melarikan diri. Ada berbagai cara untuk mencapai hal ini, salah satunya adalah:

• [1, 2, 3, 4, 5] menuju pintu 6 ((1 + 2 + 3 + 4 + 5)% 9 = 6), sementara [6, 7, 8, 9] melewati pintu 3 ((6 + 7 + 8 + 9)% 9 = 3). Semua orang bertemu di kamar kedua.
• [1, 2, 3, 7] melewati pintu 4, sementara [4, 5, 6, 8, 9] melewati pintu 5.
• [1, 2, 3, 4, 8] melewati salah satu dari 9 pintu, [5, 6, 7, 9] melewati yang lain.

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

Kali ini, paling banyak 4 orang dapat melarikan diri:

• [1, 3, 5, 8, 9] melewati pintu 8.
• [1, 3, 5, 9] melewati pintu 9.

Daftar selamat lainnya dimungkinkan, seperti [2, 3, 4] atau [1, 4, 6, 7], tetapi tidak ada cara bagi lebih dari 4 orang untuk melarikan diri.

Tantangan

Diberi peta, hasilkan jumlah maksimum pemain yang dapat melarikan diri.

• Jangan khawatir, Anda tidak perlu menguraikan diagram mengerikan saya! Input adalah grafik terarah berlabel, yang dapat Anda wakili dalam format apa pun yang nyaman (edge ​​set, adjacency matrix ...).
• Jika representasi Anda memerlukan label untuk kamar, Anda dapat menggunakan serangkaian nilai yang konsisten. Namun, pintu harus diwakili oleh bilangan bulat 1 hingga 9.
• Input akan selalu memiliki setidaknya satu pintu 9. Semua 9 pintu selalu mengarah ke pintu keluar, sementara pintu lainnya tidak pernah melakukannya.
• Kiriman Anda dapat berupa fungsi atau program lengkap.
• Celah standar dilarang.

Uji kasus

Input ditampilkan sebagai daftar triplet [nomor pintu, dari kamar, ke kamar], dengan 0 sebagai ruang awal dan -1 sebagai pintu keluar. Jika Anda memilih untuk menggunakan format lain, Anda harus mengonversinya dengan tepat.

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

Versi yang lebih lambat namun jauh lebih singkat menggunakan bitmask alih-alih string.

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

Cobalah online!

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

JavaScript (ES7),  293 272  271 byte

Mengambil input dalam format yang dijelaskan dalam tantangan. Ini adalah pencarian brute force.

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

Cobalah online! (kasus uji pertama kali habis pada TIO)

Bagaimana?

Array P[]menyimpan daftar string yang menggambarkan pemain di setiap kamar.

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

Untuk setiap kamar Xdi posisi r, kami menghitung rangkaian X:

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

Untuk setiap grup pemain pdi sana dan untuk setiap pintu [d,s,t]di indeks j, kami menguji jika grup tidak dapat melewati pintu:

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

Jika grup dapat lewat, kami melakukan panggilan rekursif:

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

Kami melacak jumlah maksimum pemain yang lolos mdan akhirnya mengembalikannya.

Jelly , 76 byte

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

Cobalah online!

Program lengkap yang mengambil argumen tunggal, grafik berarah menggunakan kamar 1, 2, ... dan 0 sebagai keluar. Mengembalikan bilangan bulat yang merupakan jumlah maksimum yang dapat melarikan diri. Penjelasan lengkap untuk diikuti.

Harus dijalankan tanpa Ṣ€€Quntuk penghematan 4-byte tetapi lambat untuk beristirahat.