Проблема:

В шахматах есть довольно известное правило о ничьей повторением. Если одна и та же позиция повторяется 3 раза (или более), то игрок, намеревающийся сделать ход, который вызовет это повторение, может претендовать на ничью.

Иногда это легко определить для арбитра, если последние несколько ходов - это просто игроки, двигающиеся вперед и назад. Иногда это менее тривиально, когда фигуры значительно переместились между повторными позициями.

Проблема в этой задаче состоит в том, чтобы вывести истинное значение, если заявленная позиция нарисована повторением (было просмотрено 3 или более раз), и значение Falsey, если заявленная позиция не нарисована повторением, учитывая список ходов в координатной записи как описано ниже, или любое обозначение по вашему выбору (но вам придется преобразовать контрольные примеры).

Какая позиция?

В сценарии реального мира на положение будут влиять такие вещи, как то, может ли игрок сделать замок или возможен ли en-passant; Вы не должны учитывать это в своем решении проблемы. В этой задаче положение определяется просто конфигурацией фигур на доске. Таким образом, для целей этой проблемы две позиции считаются одинаковыми, если каждый квадрат на обеих досках занят одним и тем же типом фигуры одного цвета. Это не обязательно должна быть точная фигура, например, белые кони могут поменять квадраты, и если все остальные фигуры будут соответствовать критериям, это все равно будет та же самая позиция.

Как выглядит действительная запись?

Хотя я и продолжу объяснять обозначения координат, вы можете свободно принимать ввод с помощью выбранной вами системы обозначений. При условии, что:

• Каждый элемент в обозначениях описывает любую или все: часть / части, вовлеченные; поставлен ли чек, мат, двойная проверка, мат или пат; если произошел случайный захват; начальная позиция; окончательная позиция.
• Вы не можете иметь информацию о повторении в вашей записи.

Поэтому, пока эти критерии соблюдены, я с радостью приму, если вы укажете в своем ответе, свою систему обозначений. Это может быть, например, 0 проиндексированных строк, кортежей столбцов или что-либо еще, что имеет смысл для вашей программы.

Обозначение координат

Обозначение координат - это обозначение, которое описывает чисто движения как систему координат.

Перемещение описывается как сначала начальная координата из набора, {A1-H8}а затем снова координата назначения из того же набора. Таким образом , гамбит короля будет выглядеть (как набор строк)

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

Я считаю, что это лучшее обозначение для этой проблемы, потому что оно не усеяно посторонней информацией, такой как проверка или тип перемещения детали. Как упоминалось ранее, нотация может быть на ваш выбор, поэтому вы можете использовать другую нотацию, например, алгебраическую нотацию, или вы можете адаптировать эту нотацию (например, удалить тире или взять в качестве списка кортежей)

Правила:

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

Основные правила:

• Это код-гольф , поэтому выигрывает самый короткий ответ в байтах.
  Не позволяйте языкам кода-гольфа отговаривать вас от публикации ответов на языках, не относящихся к кодексу. Попробуйте найти как можно более короткий ответ для «любого» языка программирования.
• К вашему ответу применяются стандартные правила с правилами ввода / вывода по умолчанию , поэтому вам разрешено использовать STDIN / STDOUT, функции / метод с правильными параметрами и типом возврата, полные программы. Ваш звонок.
• По умолчанию лазейки запрещены.
• Если возможно, добавьте ссылку с тестом для вашего кода (например, TIO ).
• Кроме того, добавление объяснения для вашего ответа настоятельно рекомендуется.

Тестовые случаи

Вы должны вернуть правдивые значения для:

{"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"}

И фальси значения для:

{}
{"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"}

APL (Dyalog Extended) , 55 49 47 45 44 байта ^SBCS

-4 благодаря нгн.

Полная программа. Запрашивает обратный список пар обратных координат:
 например {"B1-C3","B8-C6"},[[[8,2],[6,3]],[[1,2],[3,3]]]

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

Попробуйте онлайн! (включает функцию полезности, Coordsкоторая переводит формат OP)

Настройте список состояний:

s←3 назначить трех до s(для з Tates)

Так как 3 не является допустимым состоянием доски, это не повлияет на наш счетчик повторений, и нам нужно сквозное значение назначения…

Построить представление шахматной доски:

5… Отбросить это для результата применения следующей производной функции между 5 и 3:
 ⍥⍳ расширить оба аргумента до их ɩ ndices;
  [1,2,3,4,5]… [1,2,3]
 ,∘⌽ Левая сторона соединена с обратной стороной правой стороны,
  [1,2,3,4,5,3,2,1]это представляет офицеров

⍪ сделать в стол;
 [[1],
  [2],
  [3],
  [4],
  [5],
  [3],
  [2],
  [1]]

6, добавьте (к каждому ряду) шестерку, представляющую пешки;
 [[6,1],
  [6,2],
  [6,3],
  [6,4],
  [6,5],
  [6,3],
  [6,2],
  [6,1]]

⍉ транспонировать;
 [[6,6,6,6,6,6,6,6],
  [1,2,3,4,5,3,2,1]]

¯4↑ взять отрицательные (т.е. последние) четыре (строки), заполненные нулями, представляющими пустые квадраты;
 [[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]]

(… ) Примените к этому следующую молчаливую функцию:

 - отрицать (это представляет противоположный цвет);
  [[ 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]]

  ⊖⍪ поместите перевернутый аргумент поверх этого, давая нам полный пансион;
  [[ 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]]

Составьте список ходов с последующим исходным состоянием:

⊂ приложить это (рассматривать это как единое целое)

⎕, запросить список ходов и добавить его в исходное состояние

Уменьшите * на функцию, которая добавляет текущее состояние в список и делает ход:

{… }/ Уменьшить на следующую анонимную лямбду:

 ⍵ правильный аргумент (текущее состояние)

 ⊂ приложите это, чтобы рассматривать это как единое целое

 s,← на месте добавить его в список штатов

 ⊃ раскрыть его, чтобы использовать это состояние

 … @⍺ В элементах с двумя координатами, которые представляет левый аргумент, поместите:
  0 ноль,
  , за
  ∘ которым следует
  ⊃ первое значение,
^{это эффективно «перемещает» значение в первой координате во вторую координату, оставляя после себя ноль}

Проверьте, есть ли у нас три или более конечных состояния:

s∩ пересечение всех состояний с этим последним; подмножество идентичных ему состояний

≢ подсчитать их

2≤ проверить, есть ли два или более (то есть три или более, включая конечное состояние)

* APL ассоциирован справа, поэтому сначала вызывается функция с начальным состоянием в качестве правого аргумента и начальным перемещением в качестве левого аргумента, а затем ее результат, новое состояние, становится новым правым аргументом со вторым ходом в качестве нового левого аргумента и т. д. Окончательный результат

R , 180 177 144 байт

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}

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

-3 байт благодаря Giuseppe
-29 байт благодаря использованию Ник Кеннеди Reduceи -rev(l)
-4 байтов в обратномz

В качестве входных данных принимает вектор целых чисел от 1 до 64, обозначающий квадраты. TIO включает в себя функцию для преобразования в этот формат. Различные части хранятся в виде целых чисел от 1 до 6 и от -1 до -6.

Объяснение:

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
}

Желе , 41 37 байт

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

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

Монадическая ссылка, которая принимает входные данные в виде списка пар 1-индексированных ходов основных строк [from, to]и возвращает 1 для ничьих и 0 для нет.

Обратите внимание, что код нижнего колонтитула в TIO переводит ходы, предоставленные OP, в числовой формат, но согласно обсуждению ниже вопроса числовой формат был бы допустимым вводом.

объяснение

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

Ожидает движение в [sq0, sq1]формате, где каждый квадрат находится в$[0..63]$ с $\text{a8}=0$, $\text{b8}=1$, ..., $\text{h1}=63$,

Возвращает логическое значение.

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

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

Как?

Частей

Значения, используемые для идентификации частей, на самом деле не имеют значения, если для каждого типа элементов существует одно уникальное значение.

Мы используем:

• 0 для пустых квадратов
• 1 / 8 / 9 / / B / C для ♟ / ♜ / ♞ / ♝ / ♛ / ♚
• 2 / 3 / 4 / 5 / 6 / 7 для ♙ / ♖ / ♘ / ♗ / ♕ / ♔

Доска и начальная позиция

Доска хранится в массиве $b$ который инициализируется путем разделения конкатенации следующих частей:

• '89ABCA981111111' → 8 черных основных фигур, за которыми следуют первые 7 черных пешек
• 10n**32n → последняя черная пешка на $\text{h7}$ ($1$), за которыми следуют 32 пустых квадрата ($0$)
• 0x7e5196ee74377 → все белые фигуры (расходуется на 2222222234567543 в десятичном виде)

что приводит к:

    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

Отслеживание позиций

Переменная $b$также используется в качестве объекта для отслеживания всех встреченных позиций. Ключ для каждой позиции$b$сам, но на этот раз как массив и неявно приведен к строке.

Вот почему мы делаем:

b[b] = -~b[b]

комментарии

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

Java 10, 336 330 287 285 282 276 байт

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 байт благодаря @Arnauld , изменив i%56<8?"ABCDECBA".charAt(i%56%7):i%48<16?1:0наi%56<8?i%8*35%41%10%8+2:9>>i/16&1 .

Ввод в виде двумерного массива целых чисел, где $a1=0, b1=1, ..., h8=63$(т.е. {"E2-E4",...есть [[12,28],...).

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

Объяснение:

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

Значения частей после их заполнения A[i]=(i%56<8?i%8*35%41%10%8+2:9>>i/16&1)*(i/32*2-1):

     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

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

Древесный уголь , 62 байта

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

Попробуйте онлайн! Ссылка на подробную версию кода. Принимает входной сигнал в виде массива пар чисел , где пронумерованы квадраты A1, B1, ... H8(0-индексированный) , так, например , первый тестовый случай будет представлен в виде [[[1, 18], [57, 42], [18, 1], [42, 57], [1, 18], [57, 42], [18, 1], [42, 57]]]и выводит , -если позиция ничья повторением. Программа конвертации. Все в одном. Объяснение:

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

Разделить число 23456432 на отдельные цифры. Они представляют собой белые фигуры.

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

Добавьте в пешки и пустые ряды. Белые пешки имеют ценность 1и черные пешки -1.

Ｆ…η⁸⊞η±ι

Добавьте отрицательную копию белых частей, которые представляют черные части.

Ｆθ«

Зацикливайтесь на движениях.

⊞υ⮌η

Сохраните копию доски. (Реверсирование - самый лучший способ скопировать доску.)

§≔η⊟ι§η§ι⁰

Обновите место назначения с помощью исходного фрагмента.

§≔η⊟ι⁰

Удалить исходную часть.

»›№υ⮌η¹

Определите, была ли текущая позиция видна более одного раза.

C # (интерактивный компилятор Visual C #) , 204 байта

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;}

Принимает входные данные как список кортежей целых чисел, где первое целое число - это место, откуда нужно двигаться, а второе - куда нужно двигаться. 0 представляет собой A1, 1 представляет собой A2, и 63 представляет собой H8.

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

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
    j.Add(d.ToArray());        //  Add the current board to the list
    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) , 246 245 244 байта

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;}

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

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
    j.add(d.clone());                 //  Add the current position to the list
    d[ k[1] ] = d[ k[0] ];            //  Set the destination square's value
                                      //  to the source squares
    d[ k[0] ] = 1;                    //  And clear the source square 
}                                     //End foreach
return j.stream()                     //Convert list of states to stream
  .filter(x ->                        //Filter each position by
    Arrays.equals(d,x)                //  if the position equals the final position 
  ).count() > 1;                      //And return if there are at least two
                                      //positions that are left
}