# Problem:

In chess, there is a somewhat well known rule about draw by repetition. If the same position is repeated 3 times (or more) then the player intending to make the move which will cause the this repetition can claim a draw.

Sometimes this is an easy task for an arbiter to spot, if the last few moves are just the players moving backwards and forwards. Sometimes it is less trivial, when pieces have moved significantly between repeated positions.

The problem in this challenge is to output a truthy value if the claimed position is draw by repetition (has been seen 3 times or more) and a falsey value if the claimed position is not draw by repetition, given a list of moves in coordinate notation as described below, or any notation of your choosing (but you'll have to convert the test cases).

### What is a position?

In a real world scenario, the position would be affected by things such as whether a player can castle or whether en-passant is possible; you should not consider these in your solution to the problem. In this problem a position is defined simply by the configuration of the pieces on the board. So, for the purposes of this problem, two positions are seen to be the same if each square on both boards is occupied by the same type of piece of the same colour. This does not have to be the exact piece for example white's knights could swap squares and if all other pieces fulfill the criteria this would still be the same position.

### What does a valid notation look like?

Although I will go on to explain coordinate notation, you are free to take input by a notation system you choose. Provided that:

• Each item in the notation describes any or all of: the piece/pieces involved; whether check, checkmate, double check, checkmate or stalemate have been delivered; if en-passant capture has occurred; the initial position; the final position.

So as long as these criteria are met I am happy to accept, as long as you specify in your answer, your notation system. This could be e.g. 0 indexed row,column tuples or whatever makes sense for your program.

### Coordinate Notation

Coordinate notation is a notation which describes purely the moves as a system of coordinates.

A move is described as first the initial coordinate from the set {A1-H8} and then the destination coordinate again from the same set. So the King's Gambit would look like (as a collection of strings)

{"E2-E4","E7-E5","F2-F4"}


I believe it's the best notation to use for this problem because it is not littered with extraneous information like whether check has occurred or what the type of piece moving is. As mentioned before the notation can be of your choice, so you could use another notation e.g. algebraic notation or you could adapt this notation (e.g. remove the dashes, or take as a list of tuples)

## Rules:

• You should not consider whether a position or move is valid, only whether it causes repetition
• You can assume that castling and pawn promotion will not occur.
• You should take a list of strings as input and output a truthy or falsey value corresponding to whether the third (or more) repetition has occurred on the final move
• The game always starts at the standard starting position for chess. The initial position can count towards repetition.
• Draw by repetition has not occurred if the position is not repeated by the final move

## General rules:

• This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.

### Test Cases

You should return truthy values for:

{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8"}
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8"}
{"B1-C3","B8-C6","D2-D4","D7-D5","D1-D3","D8-D6","C3-B1","C6-B8","B1-C3","B8-C6","D3-D1","D6-D8","D1-D3","D8-D6"}
{"D2-D4","B8-C6","E2-E4","C6-D4","D1-E2","D4-E6","E2-F3","E6-D4","F3-D1","D4-C6","D1-E2","C6-D4","E1-D1","D4-C6","D1-E1","C6-D4"}
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","B1-C3"}


And falsey values for:

{}
{"E2-E4","E7-E5","F2-F4"}
{"B1-C3","B8-C6","C3-B1","C6-B8","B1-C3","B8-C6","C3-B1","C6-B8","F2-F4","F7-F5"}
{"E2-E4","E7-E5","G1-F3","B8-C6","F1-C4","G8-F6","F3-G5","D7-D5","E4-D5","F6-D5","G5-F7"}
{"D2-D4","B8-C6","E2-E4","C6-D4","D1-E2","D4-C6","E2-D1","C6-D4","D1-E2","D4-C6","E2-D1"}
{"B1-C3","B8-C6","C3-B5","C6-B4","B5-D4","B4-D5","D4-C6","D5-C3","C6-B8","C3-B1","B8-C6","B1-C3","C6-B8","C3-B1"}
{"E2-E4","E7-E5","D1-E2","E8-E7","E1-D1","D8-E8","E2-E1","E7-D8","E1-E2","E8-E7","E2-E1","E7-E8"}

• Can we take input as, say, a list of pairs of squares numbered in a row-major order, getting rid of chess entirely? How about a list of pairs of pairs of coordinates? Apr 2 '19 at 12:57
• You won't be able to get rid of chess entirely, since the pieces themselves and capturing pieces are both still important. You can define your coordinate system however you like though. I'll clarify in the question what properties a valid set of inputs will have. Apr 2 '19 at 13:00
• @KevinCruijssen I'll explicitly add that the initial state DOES count. I think you spotted that the pieces matter, so do the colour of the piece. The second last test case is where black and white's knights swap over. In the last one the queen and king swap around for both players Apr 2 '19 at 13:31
• @ExpiredData Can you explain why the 3rd falsey case is falsey? After the last C6-B8 the initial position has occurred thrice.
Apr 2 '19 at 13:35
• Ah, it has to be the final position that appeared at least twice before.
Apr 2 '19 at 13:37

# APL (Dyalog Extended), 55494745 44 bytesSBCS

-4 thanks to ngn.

Full program. Prompts for reversed list of reversed coordinate pairs:
e.g. {"B1-C3","B8-C6"} is [[[8,2],[6,3]],[[1,2],[3,3]]]

2≤≢s∩{0,∘⊃@⍺⊃s,←⊂⍵}/⎕,⊂(⊖⍪-)¯4↑⍉6,⍪5,∘⌽⍥⍳s←3


Try it online! (includes the utility function Coords which translates OP's format)

Set up a list of states:

s←3 assign three to s (for states)

Since 3 is not a valid board state, it will not affect our repetition count, and we need the pass-through value of the assignment…

Build a chess board representation:

5… discard that for the result of applying the following derived function between 5 and 3:
⍥⍳ extend both arguments to their ɩndices;
[1,2,3,4,5][1,2,3]
,∘⌽ the left side concatenated with the reverse of the right side
[1,2,3,4,5,3,2,1] this represent the officers

⍪ make into table;
[[1],
 [2],
 [3],
 [4],
 [5],
 [3],
 [2],
 [1]]

6, prepend (to each row) a six, representing pawns;
[[6,1],
 [6,2],
 [6,3],
 [6,4],
 [6,5],
 [6,3],
 [6,2],
 [6,1]]

⍉ transpose;
[[6,6,6,6,6,6,6,6],
 [1,2,3,4,5,3,2,1]]

¯4↑ take negative (i.e. the last) four (rows), padding with zeros, representing empty squares;
[[0,0,0,0,0,0,0,0],
 [0,0,0,0,0,0,0,0],
 [6,6,6,6,6,6,6,6],
 [1,2,3,4,5,3,2,1]]

() apply the following tacit function to that:

- negate (this represents the opposite colour);
[[ 0, 0, 0, 0, 0, 0, 0, 0],
 [ 0, 0, 0, 0, 0, 0, 0, 0],
 [-6,-6,-6,-6,-6,-6,-6,-6],
 [-1,-2,-3,-4,-5,-3,-2,-1]]

⊖⍪ stack the flipped argument on top of that, giving us the full board;
[[ 1, 2, 3, 4, 5, 3, 2, 1],
 [ 6, 6, 6, 6, 6, 6, 6, 6],
 [ 0, 0, 0, 0, 0, 0, 0, 0],
 [ 0, 0, 0, 0, 0, 0, 0, 0],
 [ 0, 0, 0, 0, 0, 0, 0, 0],
 [ 0, 0, 0, 0, 0, 0, 0, 0],
 [-6,-6,-6,-6,-6,-6,-6,-6],
 [-1,-2,-3,-4,-5,-3,-2,-1]]

Construct a list of moves followed by the initial state:

⊂ enclose that (to treat it as a single unit)

⎕, prompt for the list of moves, and prepend that to the initial state

Reduce* by a function which appends the current state to the list and makes a move:

{}/ reduce by the following anonymous lambda:

⍵ the right argument (the current state)

⊂ enclose it to treat it as a unit

s,← in-place append it to the list of states

⊃ disclose it to use that state

…@⍺ at the elements with the two coordinates that the left argument represents, put:
0 a zero
, followed
∘ by
⊃ the first value
this effectively "moves" the value at the first coordinate to the second coordinate, leaving behind a zero

Check if we have three or more of the final state:

s∩ the intersection of all states with that final one; the subset of states identical to it

≢ tally them up

2≤ check if there are two or more (i.e. three or more including the final state)

* APL is right-associative, so first the function is called with the initial state as right argument and the initial move as left argument, and then its result, the new state, becomes the new right argument with the second move as new left argument, etc. The final result is the

• I'm pretty sure this can be shortened significantly by using scan \ instead of reduce /
Apr 2 '19 at 15:38
• save 2 bytes with this ugly hack: ⍳3⊣s←⍬ -> ⍳s←3. it works because 3 is not a valid board so it won't affect repetition detection
– ngn
Apr 2 '19 at 19:12
• @ngn Ugh. Thanks. We're approaching Jelly.
Apr 2 '19 at 20:00
• (0,⊃)@ -> 0,∘⊃@
– ngn
Apr 3 '19 at 10:23
• @ngn Done. Thanks.
Apr 3 '19 at 14:57

# R, 180177 144 bytes

function(M,+=rep,l=c(1:5,3:1,6+8,0+16)){z=rev(Reduce(function(x,y){x[y[2:1]]=x[y]*1:0;x},M,c(l,-rev(l)),,T));sum(sapply(z,identical,el(z)))>2}


Try it online!

-3 bytes thanks to Giuseppe
-29 bytes thanks to Nick Kennedy's use of Reduce and -rev(l)
-4 bytes by reversing z

Takes as input a vector of integers between 1 and 64 denoting the squares. The TIO includes a function to transform into that format. The different pieces are stored as integers between 1 and 6 and between -1 and -6.

Explanation:

function(M,                                # M is the vector of moves
+ = rep,
l = c(1:5, 3:1, 6 + 8, 0 + 16)) { # initial position of white pieces
z = rev(Reduce(function(x, y) {
x[y[2:1]] = x[y] * 1:0                 # a piece moves from y[1] to y[2]; y[1] becomes 0
x
}, M, c(l, -rev(l)), , T))
sum(sapply(z, identical, el(z))) > 2    # find number of past positions identical to the last position
}

• I’ve put a revised version of yours at [bit.ly/2OHPexp]. It’s ok TIO but the link is too long for a comment. The code is inspired by yours, but uses a cumulative Reduce at its core. It’s 148 bytes. Apr 2 '19 at 21:53
• @NickKennedy Thanks! I was actually about to look into using negative integers for the black pieces; I'm glad you did it first. I like what you did with Reduce: I clearly need to learn more about this. Apr 2 '19 at 22:15
• @NickKennedy I got a further 4 bytes off your version by reversing z. Apr 2 '19 at 22:24

# Jelly, 41 37 bytes

Ø0;6x8;“Ġ²F’D¤UN;ƊW;µị@⁹Ṫ¤¦0⁹¦$\ċṪ$>1


Try it online!

A monadic link that takes the input as a list of pairs of 1-indexed row-major moves [from, to] and returns a 1 for draws and 0 for not.

Note the footer code on TIO translates the moves as supplied by the OP to the numeric format, but per the discussion below the question, the numeric format would have been a valid input.

### Explanation

Ø0                                    | 0,0
;6                                  | concatenate to 6 (pawn)
x8                                | repeat each 8 times (two blank rows and 1 row of pawns)
;“Ġ²F’D¤                        | concatenate to 1,2,3,4,5,3,2,1
UN;Ɗ                    | concatenate a negated flipped version to this one
W;                  | wrap as a list and concatenate the input list to the board
µ                 | start a new monadic chain
$\ | reduce using the two links below ị@⁹Ṫ¤¦ | replace the item pointed to by the second coordinate by the value of the one at the first 0⁹¦ | replace the item at first coordinate with zero ċṪ$   | finally count the items equal to the final one (not including it)
>1 | and check of >1


# JavaScript (Node.js),  121  111 bytes

Expects the moves in [sq0, sq1] format, where each square is in $$\[0..63]\$$ with $$\\text{a8}=0\$$, $$\\text{b8}=1\$$, ..., $$\\text{h1}=63\$$.

Returns a Boolean value.

a=>[a,...a].map(([x,y])=>r=b[b[b[y]=b[x],x]=0,b]=-~b[b],b=[...'89ABCA981111111'+10n**32n+0x7e5196ee74377])&&r>2


Try it online!

## How?

### Pieces

The values used to identify the pieces do not really matter as long as there's one unique value per piece type.

We use:

• 0 for empty squares
• 1 / 8 / 9 / A / B / C for ♟ / ♜ / ♞ / ♝ / ♛ / ♚
• 2 / 3 / 4 / 5 / 6 / 7 for ♙ / ♖ / ♘ / ♗ / ♕ / ♔

### Board and initial position

The board is stored in the array $$\b\$$ which is initialized by splitting the concatenation of the following parts:

• '89ABCA981111111' → the 8 black major pieces, followed by the first 7 black pawns
• 10n**32n → the last black pawn on $$\\text{h7}\$$ ($$\1\$$) followed by 32 empty squares ($$\0\$$)
• 0x7e5196ee74377 → all white pieces (expends to 2222222234567543 in decimal)

which results in:

    a b c d e f g h
+----------------
8 | 8 9 A B C A 9 8
7 | 1 1 1 1 1 1 1 1
6 | 0 0 0 0 0 0 0 0
5 | 0 0 0 0 0 0 0 0
4 | 0 0 0 0 0 0 0 0
3 | 0 0 0 0 0 0 0 0
2 | 2 2 2 2 2 2 2 2
1 | 3 4 5 6 7 5 4 3


### Keeping track of the positions

The variable $$\b\$$ is also used as an object to keep track of all encountered positions. The key for each position is $$\b\$$ itself, but this time as an array and implicitly coerced to a string.

This is why we do:

b[b] = -~b[b]


## Commented

a =>                    // a[] = input
[ a,                  // dummy entry to mark the initial position as encountered once
...a                // append the actual data
].map(([x, y]) =>     // for each pair of squares [x, y] in this array:
r =                 //   store the last result in r
b[                  //   update b[b]:
b[                //     update b[x]:
b[y] = b[x],    //       set b[y] to b[x]
x               //       set b[x] ...
] = 0,            //     ... to 0
b                 //     set b[b] ...
] = -~b[b],         //   ... to b[b] + 1 (or 1 if b[b] is undefined)
b = [...(…)]        //   initialize b[] (see above)
)                     // end of map()
&& r > 2              // return true if the last result is greater than 2

• I didn't write a test case for it yet, but does this work if the 2 pieces of the same colour swap over (e.g. repetition where two white knights are swapped)? I'll write a test case when I get a chance. Apr 2 '19 at 16:37
• Yes I mean that, I'll update when I can Apr 2 '19 at 17:18
• @ExpiredData This should now work as expected. Apr 2 '19 at 18:00

# Java 10, 336330287285282 276 bytes

m->{var V=new java.util.HashMap();int i=64,A[]=new int[i];var t="";for(;i-->0;)t+=A[i]=(i%56<8?i%8*35%41%10%8+2:9>>i/16&1)*(i/32*2-1);V.put(t,1);for(var a:m){for(t="",A[a[1]]=A[a[0]],A[a[0]]=0,i=64;i-->0;)t+=A[i];V.compute(t,(k,v)->v!=null?(int)v+1:1);}return(int)V.get(t)>2;}


-11 bytes thanks to @Arnauld by changing i%56<8?"ABCDECBA".charAt(i%56%7):i%48<16?1:0 to i%56<8?i%8*35%41%10%8+2:9>>i/16&1.

Input as a 2D array of integers where $$\a1=0, b1=1, ..., h8=63\$$ (i.e. {"E2-E4",... is [[12,28],...).

Try it online.

Explanation:

m->{                   // Method with 3D character array parameter and boolean return-type
var V=new java.util.HashMap();
//  Create a Map to store the occurrences of the board-states
int i=64,            //  Index integer, starting at 64
A[]=new int[i];  //  Create the 8 by 8 board
var t="";            //  Temp-String, starting empty
for(;i-->0;)         //  Loop i in the range (64,0]:
t+=                //    Append the string t with:
A[i]=            //     Fill the i'th cell with:
i%56<8?        //      If it's either the first or eighth row:
i%8*35%41%10%8+2
//       Fill it with 2,7,3,5,9,3,7,2 based on index i
:9>>i/16&1)    //      Else if it's either the second or seventh row:
//       Fill it with 1
//      Else (the third, fourth, fifth, or sixth rows):
//       Fill it with 0
*(i/32*2-1);   //      Then multiply it by -1 or 1 depending on whether i
//      is below 32 or not
V.put(t,1);          //  Then set string t in the map to 1 for the initial state
for(var a:m){        //  Loop over each of the input's integer-pairs:
for(t="",          //   Make the String empty again
A[a[1]]=       //   Set the to-cell of the current integer-pair of the input to:
A[a[0]],     //    The value in the from-cell of the same integer-pair
A[a[0]]=0,     //   And then empty this from-cell
i=65;i-->0;)   //   Inner loop i in the range (64,0]:
t+=A[i];     //    Append the i'th value to the String t
V.compute(t,(k,v)->v!=null?(int)v+1:1);}
//   Increase the value in the map for String t as key by 1
return(int)V.get(t)  //  Return whether the value in the map for the last String t
>2;}         //  is at least 3


The values of the pieces after filling them with A[i]=(i%56<8?i%8*35%41%10%8+2:9>>i/16&1)*(i/32*2-1) are:

     a  b  c  d  e  f  g  h
+------------------------
1 | -2 -7 -3 -5 -9 -3 -7 -2
2 | -1 -1 -1 -1 -1 -1 -1 -1
3 |  0  0  0  0  0  0  0  0
4 |  0  0  0  0  0  0  0  0
5 |  0  0  0  0  0  0  0  0
6 |  0  0  0  0  0  0  0  0
7 |  1  1  1  1  1  1  1  1
8 |  2  7  3  5  9  3  7  2


Try it online.

• Wrestled for a while with a way to avoid using t, is there no structure you can use to store state which will do something like java.util.Arrays.deepHashCode? If so there's loads of bytes to spare Apr 2 '19 at 16:29
• Also, I wonder if this is technically correct based on the implementation of hashmap, there's probably going to be hash collisions for chess boards given that the possible configurations is huge? I'm not going to give you a counterexample for that though! Apr 2 '19 at 16:41
• @ExpiredData There indeed is a java.util.Arrays.deepHashCode(A), but apparently some of the hashes are still the same somehow (i.e. last test case has -447346111=3 in the map..) if I compare the resulting map of my current answer and the resulting map using deepHashCode(A). Also, it would be 3 bytes longer instead of shorter, since I have to use deepHashCode(A) twice (for the initial state as well). Apr 2 '19 at 19:26
• But the first black rook is different from the second black rook. two positions are seen to be the same if each square on both boards is occupied by the same type of piece of the same colour Apr 2 '19 at 21:30
• Not fully tested in Java, but the expression i%8*35%41%10%8+2 should be a possible replacement for "ABCDECBA".charAt(i%8), saving 6 bytes. It generates the pattern [ 2, 7, 3, 5, 9, 3, 7, 2 ]. Apr 3 '19 at 10:11

# Charcoal, 62 bytes

≔↨²³⁴⁵⁶⁴³²χηＦ⁴⁸⊞η÷⁻⁴⁰ι³²Ｆ…η⁸⊞η±ιＦθ«⊞υ⮌η§≔η⊟ι§η§ι⁰§≔η⊟ι⁰»›№υ⮌η¹


Try it online! Link is to verbose version of code. Takes input as an array of pairs of numbers where the squares are numbered A1, B1, ... H8 (0-indexed) so for instance the first test case would be represented as [[[1, 18], [57, 42], [18, 1], [42, 57], [1, 18], [57, 42], [18, 1], [42, 57]]] and outputs a - if the position is a draw by repetition. Conversion program. All in one. Explanation:

≔↨²³⁴⁵⁶⁴³²χη


Split the number 23456432 into individual digits. These represent the white pieces.

Ｆ⁴⁸⊞η÷⁻⁴⁰ι³²


Add in the pawns and the empty rows. The white pawns have value 1 and the black pawns -1.

Ｆ…η⁸⊞η±ι


Append a negated copy of the white pieces, which represent the black pieces.

Ｆθ«


Loop over the moves.

⊞υ⮌η


Save a copy of the board. (Reversing is the golfiest way to copy the board.)

§≔η⊟ι§η§ι⁰


Update the destination with the source piece.

§≔η⊟ι⁰


Remove the source piece.

»›№υ⮌η¹


Determine whether the current position was seen more than once before.

# C# (Visual C# Interactive Compiler), 204 bytes

n=>{var j=new List<char[]>();var d=("ABCDECBATTTTTTTT"+new string('Z',32)+7777777712345321).ToArray();foreach(var(a,b)in n){j.Add(d.ToArray());d[b]=d[a];d[a]='Z';}return j.Count(r=>r.SequenceEqual(d))>1;}


Takes input as a list of tuples of integers, where the first integer is where to move from, and the second is where to move to. 0 represents A1, 1 is A2, and 63 is H8.

Try it online!

n=>{
var j=new List<char[]>();    //Initialize a list to save states of a board
var d=("ABCDECBATTTTTTTT" +  //White pieces
new string('Z',32) +         //Empty spaces
7777777712345321)            //Black pieces
.ToArray(); //Initialize the chessboard
foreach(var(a,b)in n){       //Foreach (source square, destination square) in the input
d[b]=d[a];                 //  Set the destination square to the source square's value
d[a]='Z';                  //  And set the souce square to empty
}
return j.Count(         //Return that the amount...
r=>r.SequenceEqual(d) //  of past positions that are equal to the current position...
)>1;                    //is at least two
}


# Java (JDK), 246245 244 bytes

import java.util.*;n->{var j=new ArrayList<char[]>();var d=("ABCDECBATTTTTTTT"+"".repeat(32)+7777777712345321l).toCharArray();for(var k:n){j.add(d.clone());d[k[1]]=d[k[0]];d[k[0]]=1;}return j.stream().filter(x->Arrays.equals(d,x)).count()>1;}


Try it online!

import java.util.*;                   //Import the java.util package

n->{                                  //Function taking in int[][],
//where each int[] is a a pair of numbers
var j = new ArrayList<char[]>();    //List to save each position of the chessboard
var d =                             //The chessboard's starting position
("ABCDECBATTTTTTTT" +             //  All the white pieces
"&#1".repeat(32) +                //  Plus the empty squares
7777777712345321l)                //  And the black pieces
.toCharArray();                     //Split to array of chars
for(var k:n){                       //Foreach [sourceSquare, destinationSquare] in input