Possible moves in Othello/Reversi

Question

Othello/Reversi is a board game in which players take turn placing pieces of a color (dark or light) on the 8x8 board. The possible moves are positions where there are one or more pieces of the opponent's color in a straight (horizontal, vertical, or diagonal) line between that position and a piece of the player's color.

For example, on this board, the numbers on the left mark the row, the letters on the bottom mark the column, the empty spaces are marked ., the dark pieces are marked D, the light pieces are marked L, and the possible moves for dark are marked *:

1........
2........
3...D....
4...DD...
5.*LLLD..
6.****L..
7.....**.
8........
 abcdefgh

Your task is to take a board as input and output the positions of the possible moves dark can make.

Rules

• Input and output can be in any convenient format. Possible input formats include as a string separated by newlines, as a matrix, and as a flattened list of numbers. Output positions can be in a format like b5, a list of two numbers, or a complex number. You may also choose to modify the input.
• The output may be in any order but cannot contain duplicates.
• You may use different values to represent D, L, and ., as long as they are distinct.
• You may assume that at least one move exists.
• Standard loopholes apply.
• This is code-golf, so the shortest code in bytes in each language wins.

Test cases

........
........
...D....
...DD...
..LLLD..
.....L..
........
........

b5 b6 c6 d6 e6 f7 g7

[[1, 4], [1, 5], [2, 5], [3, 5], [4, 5], [5, 6], [6, 6]]

---

........
........
........
...LD...
...DL...
........
........
........

c4 d3 e6 f5

[[2, 3], [3, 2], [4, 5], [5, 4]]

---

.....L..
...LL...
.DDDD.L.
.LDDDLL.
.LLDLLL.
.L.LD...
..LLL...
.L...L..

a4 a5 a6 a7 b7 c1 c6 c8 d1 d8 e1 e8 f6 g6 h3 h4 h5 h6

[[0, 3], [0, 4], [0, 5], [0, 6], [1, 6], [2, 0], [2, 5], [2, 7], [3, 0], [3, 7], [4, 0], [4, 7], [5, 5], [6, 5], [7, 2], [7, 3], [7, 4], [7, 5]]

• Arnauld: Can we output by adding the positions to the input?
• Yousername: @Arnauld Yes, as long as the values are distinct from the input values.

Answer 1

Python 3, (削除) 245 (削除ここまで) (削除) 238 (削除ここまで) (削除) 212 (削除ここまで) (削除) 197 (削除ここまで) (削除) 191 (削除ここまで) 184 bytes

def f(T,*R):
 for m in range(576):
 for q in range(1,8*T[m//72][m%8]):
 w,z=m//72+m%9//3*q-q,m%8+m%9%3*q-q;d=T[w][z];b=(w>=0<=z)*(q>1<2-d)
 if-~d+b:R+=((z,w),)*b;break
 return{*R}

Try it online!

A function that receives a list of strings and outputs a set containing sized-2 tuples.

• -21 bytes by removing i, j, a and b, and replacing the if T[i][j]=='D': with a multiplication inside the range

• -7 bytes thank to @Dingus by using two if-s instead of if-elif-else

• -26 bytes by removing the flag variable and compacting loops m and n into one

• -15 bytes thank to @Yousername (OP) by accepting a matrix of integers instead of a matrix of strings, where the empty slot is \0ドル\$, a dark piece is \1ドル\$, and a light piece is \$-1\$

• -6 bytes by inlining i and j and simplifying b

• -5 bytes thank to @Dingus by inlining n!

• -2 bytes by replacing a default argument list with an *args tuple

Python 3, (削除) 270 (削除ここまで) 266 bytes

Original version.

def f(T):
 R=[]
 for m in range(64):
 i=m//8;j=m%8
 if T[i][j]=='D':
 for n in range(9):
 a=n//3;b=n%3;f=0
 for q in range(1,8):
 w,z=i+q*a-q,j+q*b-q;d=T[w][z]
 if'L'==d:f=1
 elif(d=='.')*f*(w>=0<=z):R+=[(z,w)];break
 else:break
 return{*R}

Try it online!

• -4 bytes by using a set-literal instead of a set-function

---

How does it work?

The output variable here is R. Since the board is 8x8, we can iterate over it as a continuous range (for m in range(64):), storing the current row and column on i and j, respectively.

Every "D" piece has 8 possible directions to be validated: north, south, east, west, northwest, northeast, southwest and southeast. We also assume a "D" piece will be validated against itself: this case will be basically a no-op, and it's only considered here so that we can directly do for n in range(9): instead of iterating over a range(8) and making additional checks.

We then split n into two variables a and b, each containing values from 0 to 2. Basically, the following transformation is applied:

n = 0 --> a = 0; b = 0 --(-1)-> a = -1; b = -1 (southwest)
n = 1 --> a = 0; b = 1 --(-1)-> a = -1; b = 0 (south)
n = 2 --> a = 0; b = 2 --(-1)-> a = -1; b = +1 (southeast)
n = 3 --> a = 1; b = 0 --(-1)-> a = 0; b = -1 (west)
n = 4 --> a = 1; b = 1 --(-1)-> a = 0; b = 0 (no-op)
n = 5 --> a = 1; b = 2 --(-1)-> a = 0; b = +1 (east)
n = 6 --> a = 2; b = 0 --(-1)-> a = +1; b = -1 (northwest)
n = 7 --> a = 2; b = 1 --(-1)-> a = +1; b = 0 (north)
n = 8 --> a = 2; b = 2 --(-1)-> a = +1; b = +1 (northeast)

Since a board has a limit of 8 pieces in each direction (8x8), we iterate over range(1, 8). The variable q here describes how far we are going into the direction described by n: if n is north and q is 1, we are looking at the first slot on the top of (i, j); if n is east and q is 2, we are looking at the second slot on the right of (i, j). That slot has coordinates (w, z), with value d.

If that slot contains a "L" piece, we can proceed with the validation; set flag to true. That flag implements the requirement

The possible moves are positions where there are one or more pieces of the opponent's color in a straight (horizontal, vertical, or diagonal) line between that position and a piece of the player's color.

We can only add a possible move to R if the flag has been set; that is, if there is an "L" piece between a "D" piece and an empty slot.

If the next slot on that direction is an empty spot, a "L" piece has already been visited (i.e. if f is true) and if (w, z) is a valid spot on the board, then add it to R and stop validating.

Continue for all "D" pieces, for all possible directions, for all possible offsets.

• Yousername: You are allowed to take the input as a list of lists of integers instead, with D, L, and . mapping to distinct integers, which could make this a little shorter.
• enzo: @Dingus thanks, so much better!
• enzo: @Dingus Nice improvement! About the argument, you're definitely correct. However, I was able to reduce more two bytes by using an *args tuple, so it can be called consecutive times without a dummy list.
• Dingus: Ah, nicely done with the *args. I tried to do the same thing but my output always contained an empty tuple at the start that I couldn't work out how to avoid (I'm not a Pythonista).

Answer 2

Charcoal, 40 bytes

E8SF8F8«Jικ¿⊙E8+⪫KD8✳λω.D=×ばつ6L...λ⌕λD1*

Attempt This Online! (Only using ATO here because the version of Charcoal on TIO erroneously extends the canvas when you use PeekDirection.) Link is to verbose version of code. Outputs by drawing *s where the possible moves are. Explanation:

E8S

Copy the input to the canvas.

F8F8«Jικ

Jump to each square in turn.

¿⊙E8+⪫KD8✳λω.D

For every direction, peek in that direction, appending .D to the peeked string...

=×ばつ6L...λ⌕λD1

... if after truncating the string at the position of the first D, the result is not . but is a prefix of .LLLLLL...

*

... overwrite the . with a *.

• Nahuel Fouilleul: I'm sorry but the link provided shows L replaced by *
• Neil: @NahuelFouilleul Sorry about that, I had the wrong comparison all along and never noticed (earlier versions had extra checks in which obscured the difference).

Answer 3

Perl (-p), 60 bytes

for$i(0,7..9){s/D(.{$i}(L.{$i})+)\K\.|\.(?=(?1)D)/*/s&&redo}

Attempt This Online!

Answer 4

JavaScript (ES11), 115 bytes

Expects a matrix with \0ドル\$ for empty, \1ドル\$ for light, \2ドル\$ for dark. Returns another matrix in the same format, using \3ドル\$ for the possible moves for dark.

m=>m.map((r,y)=>r.map((n,x)=>[...35678+m].some(d=>(g=X=>(q=m[Y+=~-(d/3)]?.[X+=d%3-1])&1&&g(X)|!n)(x,Y=y)*q&2)?3:n))

Attempt This Online!

Commented

m => // m[] = input matrix
m.map((r, y) => // for each row r[] at index y in m[]:
 r.map((n, x) => // for each value n at index x in r[]:
 [...35678 + m] // we coerce 35678 to a string and get the values
 // 0, 1 and 2 from m[] (if the board does not
 // contain at least one empty, one light and one
 // dark square, then there's no possible move and
 // some() would fail anyway)
 .some(d => // for each direction d:
 (g = X => // g is a recursive function taking X
 ( q = // q is the value of the square on
 m[Y += ~-(d / 3)] // the updated row Y
 ?.[X += d % 3 - 1] // and the updated column X
 ) & 1 && // if it's a light one:
 g(X) // do a recursive call
 | !n // and set the final result if n != 0
 )(x, Y = y) // initial call to g with the current position
 * q & 2 // test whether the last square is dark
 ) ? // end of some(); if truthy:
 3 // set this square as a possible move
 : // else:
 n // leave it unchanged
 ) // end of inner map()
) // end of outer map()

• l4m2: Why d/3%3 if d<9?
• Arnauld: @l4m2 Thanks. What I initially had in mind was to use 2**29, which requires the %3. Then I reverted to "01235678" and forgot to remove the %3.

Answer 5

Google Sheets, 253 bytes

=let(_,lambda(a,r,regexmatch(join(,a),r)),f,"^L+D",b,"DL+$",if((H8=".")*or(_(A8:G8,b),_(I8:O8,f),_(H1:H7,b),_(H9:H15,f),_({A1,B2,C3,D4,E5,F6,G7},b),_({A15,B14,C13,D12,E11,F10,G9},b),_({I7,J6,K5,L4,M3,N2,O1},f),_({I9,J10,K11,L12,M13,N14,O15},f)),"*",H8))

Put the input in cells H8:O15 and the formula in cell X8, and copy the formula cell to the range X8:AE15. The output is returned as a matrix in the latter cells, mimicking the format shown in the example in the question.

Try it.

Generates strings by joining seven values to the left, right, up and down, and diagonally from a cell. Matches each string against a regex that looks at the start or at the end, depending on the string's direction from the origin.

othello.png

Ungolfed:

=let( 
 isMatch_, lambda(a, x, 
 regexmatch(join("", a), x) 
 ), 
 left, A8:G8, 
 right, I8:O8, 
 up, H1:H7, 
 down, H9:H15, 
 leftup, { A1, B2, C3, D4, E5, F6, G7 }, 
 leftdown, { A15, B14, C13, D12, E11, F10, G9 }, 
 rightup, { I7, J6, K5, L4, M3, N2, O1 }, 
 rightdown, { I9, J10, K11, L12, M13, N14, O15 }, 
 forward, "^L+D", 
 backward, "DL+$", 
 if( 
 and( 
 (H8 = "."),
 or( 
 isMatch_(left, backward), 
 isMatch_(right, forward), 
 isMatch_(up, backward), 
 isMatch_(down, forward), 
 isMatch_(leftup, backward), 
 isMatch_(leftdown, backward), 
 isMatch_(rightup, forward), 
 isMatch_(rightdown, forward) 
 ) 
 ), 
 "*", 
 H8 
 ) 
)

Answer 6

Jelly, 30 bytes

ŒJðŒṬ9_ZṚ,ƊŒD;$€ẎẆ€ẎẠƇQ€ḂḄ5eðƇ

A monadic Link that accepts a list of lists of 0s (spaces), 1s (dark pieces), and 2s (light pieces) and yields a list of valid spaces at which dark may play - each as 1-indexed [row, column].

Try it online! (The footer translates to the input above, calls the Link, and transforms the output to the sorted, 0-indexed [column, row] format used in the question's examples.)

pretty-print version.

How?

ŒJðŒṬ9_ZṚ,ƊŒD;$€ẎẆ€ẎẠƇQ€ḂḄ5eðƇ - Link: Board (.:0 D:1 L:2)
ŒJ - multidimensional indices -> all coords
 ð ðƇ - keep those for which - f(coord, Board):
 ŒṬ - array with a 1 at {coord} and 0s elsewhere
 9_ - Board subtract that (i.e. Board -1 @ coord)
 ZṚ,Ɗ - rotate {that} a quarter and pair with {that}
 ŒD;$€ - concatenate each to its forward diagonals
 Ẏ - tighten
 Ẇ€ - sublists of each
 Ẏ - tighten
 ẠƇ - keep if: all? (those with no 0s (spaces))
 Q€ - deduplicate each
 Ḃ - mod two
 Ḅ - convert from binary
 5e - five exists?

Answer 7

Retina 0.8.2, 105 bytes

s`\.(?=(L+|(.{7}L)+.{7}|(.{8}L)+.{8}|(.{9}L)+.{9})D|(?<=D(L+|(.{7}L)+.{7}|(.{8}L)+.{8}|(.{9}L)+.{9}).))
*

Try it online! Link is to test suite that accepts multiple double-spaced boards. Outputs by drawing *s where the possible moves are. Explanation: From each . the regular expression tries to look both ahead or behind in each possible direction for at least one L followed by a D.

Retina 1, 70 bytes

+s,T,,`.`*`([.D])(L+|(.{7}L)+.{7}|(.{8}L)+.{8}|(.{9}L)+.{9})(?!1円)[.D]

Try it online! Link is to test suite that accepts multiple double-spaced boards. Outputs by drawing *s where the possible moves are. Explanation: The regular expression matches every pair of . and D (in either order) that are separated by a run of Ls in any of the forward directions. The ,T,, command then transliterates the first and last character (,, is a step range using defaults of all three values) of each match (, is a regular range using defaults and is only needed so that the second range can be specified) from . to * (the D is therefore unaffected). The + then repeats until there are no more matches.