12
\$\begingroup\$

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
\$\endgroup\$
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Veskah Jun 11 at 16:23
  • \$\begingroup\$ 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? \$\endgroup\$ – Nick Kennedy Jun 12 at 12:10
  • \$\begingroup\$ @NickKennedy not sure what you mean by “bypass”. Doors can connect any room to any other room. It’s a directed graph. \$\endgroup\$ – Grimmy Jun 12 at 12:16
  • \$\begingroup\$ 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. \$\endgroup\$ – scatter Jun 12 at 13:14
  • \$\begingroup\$ @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. \$\endgroup\$ – Nick Kennedy Jun 12 at 13:36
7
\$\begingroup\$

JavaScript (ES6), 219 bytes

A slower but significantly shorter version using bitmasks instead of strings.

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.

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

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.