title: Who can escape the Nonary Game?

text:
# Question
Title: 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

```

# Answer
> 7 votes
# 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.

# Answer
> 2 votes
# 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.

# Answer
> 0 votes
# Python3, 402 bytes

Little long, but very fast:

```
from itertools import*
R=range
O=sorted
def f(r):
 q=[({0:{*R(1,10)}},r,0)]
 l,S=[],[]
 for D,r,C in q:
  l+=[len(D.get(-1,[]))]
  for i in D:
   for t in R(3,6):
    for j in combinations(D[i],t):
     for a,b in enumerate(r):
      if b[0]%9==sum(j)%9 and b[1]==i:
       if(str(U:={**D,i:O({*D[i]}-{*j}),b[2]:O({*D.get(b[2],[]),*j})}))not in S:q+=[(U,r[:a]+r[a+1:],C)];S+=[str(U)]
 return max(l+[0])

```

Try it online!

---
Tags: code-golf, game
---


title: Follow the border

text:
# Question
Title: Follow the border
*Inspired by Is this Flow Free puzzle trivial? by @Bubbler. Lengthy chunks of this challenge are borrowed from there. This may be one step of a solution for the linked challenge, depending on chosen strategy.*

## Challenge

Given an array of digits `1-9` and a padding character of your choice, output the border of the shape made by the digits (in any direction, with any starting point).

### Example

Here, the padding character is `0`.

```
Input   Border  Output (one of possible)
00111   00###   111334442222211133
13333   ###3#
13243   #32##
13240   #32#0
23240   #3##0
22200   ###00

```

## Rules

The input can be taken as a single string/array or a list of lines. You may also take the dimensions of the array as input.

The input shape will be guaranteed to be at least 2 cells thick (so no overlapping borders) and will be interconnected (so one continuous border).

You may assume only the digits 1-9 are used and choose the padding character to be either `0` or any consistent non-digit one. You may omit the trailing padding in the input and assume the array will have minimal dimensions to fit the shape (so no column or row full of `0` will be provided).

Output the string/list in any convenient manner.

This is , the shortest code per language wins!

## Test cases

Here, the padding character is `0`. Outputs here start at the leftmost cell of first row, but rotations and reflections of that vector are fine.

```
00111
13333
13243
13240
23240
22200
Output: 111334442222211133

11111
13331
12221
Output: 111111122211

00110
33333
32222
Output: 113322223333

00330
03240
13243
23243
22043
Output: 334433344232221332

0000777
0006666
0025550
0555300
8888000
9990000
Output: 7776655358899988552566

123456
789876
540032
120000
345678
987654
Output: 123456623789842456784567893157

```

# Answer
# JavaScript (ES6),  ~~116~~  101 bytes

Expects a list of strings, using any non-digit character for padding. Returns a string.

```
a=>(g=X=>+(d&=3,v=(a[y=Y+--d%2]||0)[x=X+~-d%2])?x-q|y?v+g(x,Y=y):v:g(X,d+=2))(q=a[d=Y=0].search`\\d`)

```

Try it online!

### How?

This algorithm starts at the leftmost non-empty cell on the first row of the grid and goes counterclockwise from there, leading to the outputs provided in the test cases in reverse order.

The recursive function \\$g\\$ takes a position \\$(X,Y)\\$ and a direction \\$d\\$. (NB: \\$Y\\$ and \\$d\\$ are global variables. Only \\$X\\$ is passed explicitly.)

We first look for the smallest \\$q\ge0\\$ such that the cell at \\$(q,0)\\$ is not empty and do an initial call to \\$g\\$ with \\$(X,Y)=(q,0)\\$ and \\$d=0\\$.

Within the function \\$g\\$:

1. We force \\$d\\$ into \\$\[0,1,2,3\]\\$ by isolating the two least significant bits, and we decrement it afterwards.
2. We advance by one square to a new position \\$(x,y)\\$, according to the updated value of \\$d\\$:
    * \\$-1\\$ = north
    * \\$0\\$ = west
    * \\$1\\$ = south
    * \\$2\\$ = east
3. If we've just reached \\$(q,0)\\$, the border is complete. We append the last value and stop.
4. Otherwise, we do a recursive call:
    * If the cell at our new position is non-empty, we append the value of the cell to the final result and process the recursive call `g(x,Y=y)`. Because \\$d\\$ was decremented at step 1, it means that we do a 90° turn to the right.
    * Otherwise, we process the recursive call `g(X,d+=2)`, which means that we rollback to the previous position and do a 90° turn to the left.
> 5 votes

# Answer
# Charcoal, ~~82~~ ~~53~~ 51 bytes

```
ＷＳ⟦ι⟧Ｊ⌕⭆θ¬Σι0⁰≔⁰θＷ¬⁼0ＫＫ«⊞υＫＫ≦⊕θＷ›0§ＫＶ⁻¹θ≦⊖θ✳⊗θ0»⎚↑υ

```

Try it online! Link is to verbose version of code. Uses space as the padding character. Edit: Saved ~~29~~ 31 bytes by realising that the border end could be detected without deleting the interior. Explanation:

```
ＷＳ⟦ι⟧

```

Print the input to the canvas.

```
Ｊ⌕⭆θ¬Σι0⁰

```

Find the first digit in the first row.

```
≔⁰θ

```

Start moving horizontally.

```
Ｗ¬⁼0ＫＫ«

```

Repeat until the border has been traversed.

```
⊞υＫＫ

```

Append the next border cell to the result.

```
≦⊕θ

```

Try rotating left.

```
Ｗ›0§ＫＶ⁻¹θ≦⊖θ

```

Rotate right if necessary until a digit is found.

```
✳⊗θ0

```

Move in that direction, erasing the current border.

```
»⎚↑υ

```

Output the final result.
> 4 votes

# Answer
# Python3, 307 bytes

```
E=enumerate
M=[(0,1),(0,-1),(1,0),(-1,0)]
def f(b):
 d={(x,y):v for x,r in E(b)for y,v in E(r)}
 T=[]
 for x,y in d:
  if d[(x,y)]and any((x+X,y+Y)not in d or not d[(x+X,y+Y)]for X,Y in M):T+=[d[(x,y)]]
  if 0==d[(x,y)]:T+=[d[J]for X,Y in[(1,1),(-1,-1),(1,-1),(-1,1)]if(J:=(x+X,y+Y))in d and d[J]]
 return T

```

Try it online!
> 1 votes

---
Tags: code-golf, array, path-finding
---


title: Line up the Diagonals of a Grid of Text

text:
# Question
Title: Line up the Diagonals of a Grid of Text
Given a rectangular grid of text, line up the diagonals that go from the upper-left to the bottom-right into columns such that the lowest-rightmost characters of all diagonals are on a level. Use spaces for indentation.

For example, if the input grid of text is

```
abcd
1234
WXYZ

```

then you'd line up the diagonals `W`, `1X`, `a2Y`, `b3z`, `c4`, and `d` in columns giving this output:

```
  ab
 123c
WXYZ4d

```

Note that the lowest-rightmost characters of all diagonals, `WXYZ4d`, are at the same level.

# Details

* The input grid of text will be at minimum 1×1 in size and all lines will be the same length.
* You may take the input grid as a multiline string or as a list of single line strings.
* The input grid will only contains printable ASCII characters (includes space).
* The output may optionally have one trailing newline but there should be no other empty lines.
* The lines of the output may optionally have trailing spaces but should not have unnecessary leading spaces.

# Other Examples

Empty lines separate examples. Each input is directly followed by its output.

```
123
456
789

  1
 452
78963

123.?!
456??!
789!!!

  123.
 456???
789!!!!!

**@
@

 **
@  @

/\/\
\/ /
/ /\
\/\/

   /
  \/\
 / / /
\/\/\/\

12
34
56
78
90

 7531
908642

Code

Code

G
O
L
F

FLOG

~

~

```

# Scoring

The shortest code in bytes wins.

# Answer
> 5 votes
## , 12 bytes

```
|./.&.|:&.|.

```

Defines an anonymous verb. Try it online!

## Explanation

```
|./.&.|:&.|.
|.            Reversed
  /.          anti-diagonals
    &.        under
      |:      transpose
        &.    under
          |.  reversal

```

In J, `u &. v` (read: `u` under `v`) means "v, then u, then inverse of v". Reversal and transpose are self-inverses, so the program really means "reverse, transpose, extract reversed anti-diagonals, transpose, reverse".

With example input:

```
abcd
1234
WXYZ

```

Reverse:

```
WXYZ
1234
abcd

```

Transpose:

```
W1a
X2b
Y3c
Z4d

```

Extract reversed anti-diagonals (and pad with spaces):

```
W
X1
Y2a
Z3b
4c
d

```

Transpose:

```
WXYZ4d
 123c
  ab

```

Reverse:

```
  ab
 123c
WXYZ4d

```

# Answer
> 2 votes
## CJam, 29 bytes

```
qN/{)\z}h]2/{~W%+}%eeSf.*W%N*

```

Try it online!

### Explanation

Instead of extracting the diagonals, we peel off layers from the end, alternating left and right. Consider the following input:

```
GFDB
EEDB
CCCB
AAAA

```

If we write out the diagonals as required by the challenge, we get:

```
   G
  EEF
 CCCDD
AAAABBB

```

Note that this is simply (from bottom to top), the bottom-most row, concatenated with the right-most column. This definition also works if the input is rectangular.

```
{      e# Run this loop while there are still lines left in the input.
  )    e#   Pull off the bottom-most row.
  \    e#   Swap with the remaining rows.
  z    e#   Transpose the grid so that the next iteration pulls off the last
       e#   column instead. However, it should be noted that transposing
       e#   effectively reverses the column, so the second half of each output
       e#   line will be the wrong way around. We'll fix that later.
}h     e# When the loop is done, we'll have all the individual layers on the
       e# stack from bottom to top, alternating between horizontal and vertical
       e# layers. There will be an empty string on top.
]      e# Wrap all those strings in a list.
2/     e# Split into pairs. There may or may not be a trailing single-element
       e# list with the empty string.
{      e# Map this block over each pair...
  ~    e#   Dump the pair on the stack.
  W%   e#   Reverse the second element.
  +    e#   Append to first element.
       e#   If there was a trailing single-element list, this will simply
       e#   add the empty string to the previous pair, which just removes
       e#   the empty string.
}%
ee     e# Enumerate the list, which pairs each string (now containing both halves)
       e# of an output line from bottom to top) with its index.
Sf.*   e# Turn those indices X into strings of X spaces, to get the correct
       e# indentation.
W%     e# Reverse the list of strings so the longest line ends up on the bottom.

```

# Answer
> 2 votes
# JavaScript, ~~116~~ 101 bytes

```
f=(s,r='$&',l='',z=s.replace(/.$|\n?(?!.*\n)..+/gm,x=>(l=x+l,'')))=>l?f(z,r+' ')+l.replace(/\n?/,r):l

G.onclick=()=>O.textContent=f(I.value);
```

```
<textarea id=I style=height:100px>/\/\
\/ /
/ /\
\/\/</textarea><button id=G>Go</button><pre id=O></pre>
```

I just wanted to use this regex pattern `/.$|\n?(?!.*\n)..+/gm` idea. <sup>(https://regex101.com/r/mjMz9i/2)</sup>

JavaScript regex flavour is disappointing, I had to use `(?!.*\n)` because it doesn't have `\Z` implemented, and somehow I didn't get to use `\0`.

* 15 bytes off thanks @Neil.

# Answer
> 2 votes
# Jelly, 11 or 10 bytes

```
ZŒDṙLUz⁶ṚUY

```

Try it online!

A fairly different algorithm from my other solution; this one uses a builtin to get at the diagonals, rather than doing things manually.

Explanation:

```
ZŒDṙLUz⁶ṚUY
Z           transpose
 ŒD         diagonals, main diagonal first
    L       number of lines in the original array
   ṙ        rotate list (i.e. placing the short diagonal first)
     U      reverse inside lines
      z⁶    transpose, padding with spaces
        ṚU  rotate matrix 180 degrees
          Y (possibly unnecessary) join on newlines

```

The diagonals come out in possibly the worst possible orientation (requiring repeated transpositions, reversals, and rotations), and in the wrong order (Jelly outputs the main diagonal first, so we have to move some diagonals from the end to the start to get them in order). However, this still comes out shorter than my other Jelly solution.

# Answer
> 1 votes
# Jelly, 15 or 14 bytes

```
L’⁶x;\Ṛ;"µZUZṚY

```

Try it online!

This is an algorithm that doesn't use Jelly's built-in for diagonals. Doing that might make it shorter; I might well try that next.

Here's how the algorithm works. Let's start with this input:

```
["abc",
 "def",
 "ghi"]

```

We start off with `L’⁶x;\`. `L’` gives us the length of the input minus 1 (in this case, 2). Then `⁶x` gives us a string of spaces of that length (`" "` in this case); and `;\` gives us the cumulative results when concatenating it (a triangle of spaces). We then reverse the triangle and concatenate it to the left side of the original (`;"` concatenates corresponding elements of lists, `µ` forcibly causes a break in the parsing and thus uses the original input as the second list by default), giving us this:

```
["  abc",
 " def",
 "ghi"]

```

This is almost the solution we want, but we need to move the elements downwards to be flush with the last string. That's a matter of transposing (`Z`), reversing inside each line (`U`), transposing again (`Z`), and reversing the lines ():

```
["  abc",
 " def",
 "ghi"]

```

transpose

```
["  g",
 " dh",
 "aei",
 "bf",
 "c"]

```

reverse within rows

```
["g  ",
 "hd ",
 "iea",
 "fb",
 "c"]

```

transpose

```
["ghifc",
 " deb",
 "  a"]

```

reverse the rows

```
["  a",
 " deb",
 "ghifc"]

```

Finally, `Y` joins on newlines. It's unclear to me whether or not this is required to comply with the specification (which allows input as a list of strings, but doesn't say the same about output), so the exact byte count depends on whether it's included or omitted.

# Answer
> 1 votes
# Pyth, 16 bytes

```
j_.t_M.Tm+*;l=tQ

```

### Big Pyth:

```
join-on-newline
reverse transpose-and-fill-with-spaces reverse func-map transpose-justified
map
  plus
    times innermost-var
      length assign tail input
    implicit-innermost-var
  implicit-input

```

Since people say golfing languages are hard to read, I've designed Big Pyth, which is both easily readable and easily translatable to Pyth. The linked file translates an input stream of Big Pyth to Pyth. Each whitespace-separated Big Pyth token corresponds to a Pyth token, either a character or a `.` followed by a character. The exceptions are the `implicit` tokens, which are implicit in the Pyth code.

I want to see how good an explanatory format Big Pyth is, so I'm not going to give any other explanation. Ask me if you want something explained, however.

# Answer
> 1 votes
# Vyxal, 5 bytes

```
Þ√Ṙṅ§

```

Try it Online!

Header converts it into a single character matrix which is a valid input form.

# Answer
> 0 votes
## JavaScript (ES6), 140 bytes

```
a=>[...Array(m=(h=a.length)<(w=a[0].length)?h:w)].map((_,i)=>[...Array(h+w-1)].map((_,j)=>(a[x=i+h-m-(++j>w&&j-w)]||``)[x+j-h]||` `).join``)

```

Takes input and output as arrays of strings. Also accepts a two-dimensional character array input, and save 7 bytes if a two-dimensional character array output is acceptable. Explanation: The height of the result `m` is the minimum of the height `h` and width `w` of the original array, while the width is simply one less than the sum of the height and width of the original array. The source row for the characters on the main portion of the result come directly from the appropriate row of the original array, counting up from the bottom, while on the extra portion of the result the source row moves up one row for each additional column. The source column for both halves of the result turns out to be equal to the destination column moved one column left for each source row above the bottom.

# Answer
> 0 votes
# Octave, 57 bytes

```
@(A){B=spdiags(A),C=B>0,D='  '(C+1),D(sort(C))=B(C),D}{5}

```

# Answer
> 0 votes
# Python 3, 247 bytes

```
def a(s):
 s=s.split('\n')
 for i,l in enumerate(s):r=len(s)-i-1;s[i]=' '*r+l+' '*(len(s)-r-1)
 print(*[''.join(i) for i in list(zip(*[''.join(a).rstrip([::-1].ljust(min(len(s),len(s[0])))for a in zip(*[list(i)for i in s])]))[::-1]],sep='\n')`

```

# Answer
> 0 votes
# Python 2, 150 bytes

```
def f(l):w=len(l[0]);h=len(l);J=''.join;R=range;print'\n'.join(map(J,zip(*['%%-%ds'%h%J(l[h+~i][j-i]for i in R(h)if-w<i-j<1)for j in R(h-~w)]))[::-1])

```

Takes input as list of strings.

# Answer
> 0 votes
## Clojure, 194 bytes

Implemented the hard way by grouping characters to `G` and then generating lines.

```
#(let[n(count %)m(count(% 0))G(group-by first(for[i(range n)j(range m)][(min(- n i)(- m j))((% i)j)]))](apply str(flatten(for[k(reverse(sort(keys G)))][(repeat(dec k)" ")(map last(G k))"\n"]))))

```

Takes input as a `vec` of `vec`s like `[[\a \b \c \d] [\1 \2 \3 \4] [\W \X \Y \Z]]`. Example:

```
(def f #( ... ))
(print (str "\n" (f (mapv vec(re-seq #".+" "abcd\n1234\nWXYZ")))))

  ab
 c123
d4WXYZ

```

---
Tags: code-golf, string, grid
---