# Who can escape the Nonary Game?

The Nonary Game is a fictional game played in the video game trilogy of the same name. Your goal is to find how many players (at best) can escape a given game, in as few bytes of code as possible.

## Rules of the game

• There are 9 players, numbered 1 to 9.
• All players start in the same room.
• There are any number of doors, each one with a 1 to 9 number. There may be duplicate or missing door numbers.
• Door are one-way connections between rooms. Each door can only be used once.
• Only groups of 3 to 5 players can go through a door.
• A group can only go through a door if the sum of their numbers modulo 9 matches the door’s number modulo 9.
• Any player who goes through a 9 door escapes (wins).

## Examples

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


< represents the starting point. All players start there.

In this setting, everybody can escape. There are various ways to achieve this, one of which is:

• [1, 2, 3, 4, 5] go though door 6 ((1+2+3+4+5) % 9 = 6), while [6, 7, 8, 9] go through door 3 ((6+7+8+9) % 9 = 3). Everybody meets up in the second room.
• [1, 2, 3, 7] go through door 4, while [4, 5, 6, 8, 9] go through door 5.
• [1, 2, 3, 4, 8] go through one of the 9 doors, [5, 6, 7, 9] go through the other one.
┌───┬───┐
│   │   |
│ < 8   9
│   │   |
└───┴───┘


This time, at most 4 people can escape:

• [1, 3, 5, 8, 9] go through door 8.
• [1, 3, 5, 9] go through door 9.

Other lists of survivors are possible, such as [2, 3, 4] or [1, 4, 6, 7], but there's no way for more than 4 people to escape.

## The challenge

Given a map, output the maximum numbers of player who can escape.

• Don’t worry, you don’t need to parse my awful diagrams! Input is a labeled directed graph, which you can represent in any convenient format (edge set, adjacency matrix...).
• If your representation requires labels for rooms, you can use any consistent set of values. However, doors must be represented by the integers 1 to 9.
• The input will always have at least one 9 door. All 9 doors always lead to the exit, while other doors never do.
• Your submission can be a function or full program.
• Standard loopholes are banned.

## Test cases

Inputs are shown as lists of [door number, from room, to room] triplets, with 0 being the starting room and -1 being the exit. If you choose to use another format, you’ll have to convert them appropriately.

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

• I know it's a relic of the game being 999, but it bugs me that you need to mod the door number by 9 because they don't want to escape through Door 0. – Veskah Jun 11 '19 at 16:23
• It might be worth making clearer in the description and pictorial examples that some doors bypass rooms. Also can doors ever go backwards? I.e. some people might go 0->1->exit and others go 0->2->1->exit? – Nick Kennedy Jun 12 '19 at 12:10
• @NickKennedy not sure what you mean by “bypass”. Doors can connect any room to any other room. It’s a directed graph. – Grimmy Jun 12 '19 at 12:16
• If you think this series of rules could be made more interesting with the threat of spontaneous explosion as soon as anyone makes a mistake, please give the game a try. It's great. – scatter Jun 12 '19 at 13:14
• @Grimy sure, but the pictorial examples and the first 5 actual examples have all of the doors leading from one room to the next one to the right. – Nick Kennedy Jun 12 '19 at 13:36

# JavaScript (ES6), 219 bytes

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


Try it online!

NB: The reason why it's slower is that we do not compute the powersets of the players. Given a bitmask of players $$\X\$$, we iterate on all $$\(X \operatorname{AND} p)\$$ for $$\0\le p\le X\$$ without deduplicating.

# JavaScript (ES7),  293 272  271 bytes

Takes input in the format described in the challenge. This is a brute force search.

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  Try it online! (the first test case times out on TIO) ### How? The array P[] holds a list of strings describing the players in each room. We start with P=['241375698'] (using $$\17^6=24137569\$$), which means that all players are initially located in room $$\0\$$. For each room X at position r, we compute the powerset of X: [...X].reduce((a, x) => [...a, ...a.map(y => y + x)], [''])  For each group of players p in there and for each door [d,s,t] at index j, we test if the group is unable to pass through the door:  // 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  If the group can pass, we do a recursive call: 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]
)                        //


We keep track of the maximum number of escaped players in m and eventually return it.

• Are you just trying all possibilities? – Jonah Jun 11 '19 at 17:27
• @Jonah Yes. It may be either very fast or very slow depending on the constraints implied by the input. – Arnauld Jun 11 '19 at 17:29

# Jelly, 76 bytes

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


Try it online!

A full program taking a single argument, a directed graph using rooms 1, 2, ... and 0 as exit. Returns an integer which is the maximum number that can escape. Full explanation to follow.

Should run without the Ṣ€€Q for a 4-byte saving but slow to rest.