The Nonary Game - вымышленная игра, в которую играют в одноименную трилогию о видеоиграх. Ваша цель состоит в том, чтобы найти, сколько игроков (в лучшем случае) могут избежать данной игры, используя как можно меньше байт кода.

Правила игры

• Есть 9 игроков, пронумерованных от 1 до 9.
• Все игроки начинают в одной комнате.
• Есть любое количество дверей, каждая с номером от 1 до 9. Там могут быть повторяющиеся или отсутствующие номера дверей.
• Дверь - это односторонние связи между комнатами. Каждая дверь может быть использована только один раз .
• Только группы от 3 до 5 игроков могут пройти через дверь.
• Группа может пройти через дверь, только если сумма их чисел по модулю 9 совпадает с номером двери по модулю 9.
• Любой игрок, который проходит через 9 дверей, убегает (побеждает).

Примеры

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

<представляет собой отправную точку. Все игроки начинают там.

В этой обстановке каждый может убежать. Для этого есть различные способы, один из которых:

• [1, 2, 3, 4, 5] проходят через дверь 6 ((1 + 2 + 3 + 4 + 5)% 9 = 6), а [6, 7, 8, 9] проходят через дверь 3 ((6 + 7 + 8 + 9)% 9 = 3). Все встречаются во второй комнате.
• [1, 2, 3, 7] проходят через дверь 4, а [4, 5, 6, 8, 9] - через дверь 5.
• [1, 2, 3, 4, 8] пройти через одну из 9 дверей, [5, 6, 7, 9] пройти через другую.

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

На этот раз могут убежать максимум 4 человека:

• [1, 3, 5, 8, 9] пройти через дверь 8.
• [1, 3, 5, 9] пройти через дверь 9.

Возможны и другие списки выживших, такие как [2, 3, 4] или [1, 4, 6, 7], но более 4 человек не могут сбежать.

Соревнование

Учитывая карту, выведите максимальное количество игроков, которые могут сбежать.

• Не волнуйтесь, вам не нужно разбирать мои ужасные диаграммы! Ввод представляет собой помеченный ориентированный граф, который вы можете представить в любом удобном формате (набор ребер, матрица смежности ...).
• Если вашему представлению требуются метки для комнат, вы можете использовать любой непротиворечивый набор значений. Однако двери должны быть представлены целыми числами от 1 до 9.
• На входе всегда будет хотя бы одна дверь 9. Все 9 дверей всегда ведут к выходу, в то время как другие двери никогда не делают.
• Ваше представление может быть функцией или полной программой.
• Стандартные лазейки запрещены.

Контрольные примеры

Входы отображаются в виде списков триплетов [номер двери из комнаты в комнату], где 0 - начальная комната, а -1 - выход. Если вы решите использовать другой формат, вам придется конвертировать их соответствующим образом.

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 байт

Более медленная, но значительно более короткая версия, использующая битовые маски вместо строк.

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

Попробуйте онлайн!

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

JavaScript (ES7),  293 272  271 байт

Принимает участие в формате, описанном в задаче. Это поиск грубой силы.

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

Попробуйте онлайн! (первый тестовый случай истекает на TIO)

Как?

Массив P[]содержит список строк, описывающих игроков в каждой комнате.

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

Для каждой комнаты Xна месте rмы рассчитываем мощность X:

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

Для каждой группы игроков pи для каждой двери [d,s,t]в индексе jмы проверяем, не может ли группа пройти через дверь:

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

Если группа может пройти, мы делаем рекурсивный вызов:

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

Мы отслеживаем максимальное количество сбежавших игроков mи в итоге возвращаем его.

Желе , 76 байт

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

Попробуйте онлайн!

Полная программа, принимающая один аргумент, ориентированный граф, использующий комнаты 1, 2, ... и 0 в качестве выхода. Возвращает целое число, которое является максимальным числом, которое может выйти. Полное объяснение, чтобы следовать.

Должен работать без Ṣ€€Q4-х байтового сохранения, но медленно отдыхать.