Эта доска Tic-Tac-Toe действительна?

48

Вызов

Если у вас есть крестики-нолики в любом формате, определите, действителен ли он или нет. Если доска может быть результатом игры в крестики-нолики, то она действительна. Например, эта доска действительна:

XOX
OXO
XOX
Наоборот, эта доска недействительна:

XXX
XXO
ООО

вход

  • Полный (9/9) крестики-нолики (результат, а не игра).

правила

  • Формат ввода должен быть способен отображать все 512 возможных плат ввода. Он должен быть указан вместе с инструкциями по его созданию, если он неясен / неясен. Вы должны указать маркировку доски в отдельности.
  • Должно быть два возможных выхода, один для достоверности и один для недействительности.
  • Можно предположить, что на доске нет пустых мест.

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

Действительно:

XOX
OXO
XOX

XOX
XOX
OXO

Xoo
OOX
OXX

OXO
XOX
OXO

Инвалид:

XXX
XXX
XXX

ООО
ООО
ООО

XXX
ООО
XXX

ООО
OOX
XXX

XXO
OXO
OOX

Небольшая помощь?

Доска считается действительной (для этой задачи) тогда и только тогда, когда выполняются следующие два условия:

  • Есть 5 X и 4 O, или 4 X и 5 O. Например,
    XXX
    OXO
    XXX
    считается недействительным, потому что есть 7 X и 2 Os.
  • Победил только игрок с 5-ю отметками, или ни одна из них не победила. Например,
    XXX
    ООО
    OOX
    считается недействительным, поскольку строка Os или строка Xs будут сформированы первыми. Два игрока не могут иметь свой ход одновременно.

Текущий победитель ...

... ответ Jelly ais523 , с поразительными 26 байтами!

Эрик Outgolfer
источник
2
Возможно также добавить тестовый пример, например O O O X O X X O X, чтобы показать, что у одного и того же игрока может быть как горизонтальный, так и вертикальный ряд.
Smls
2
Вы должны указать маркировку доски в отдельности. Я не уверен, что понимаю эту часть. Не могли бы вы предоставить контрпример?
Арно
3
@Tim X имеет 4 оценки.
Мартин Эндер
2
@Sparr "Только игрок с 5 оценками выиграл, или ни одна из них не выиграла."
Мартин Эндер
2
@Kevin (Ответ на 1-й комментарий) Потому что никакая доска 9/9 никогда не будет завершена, если победит второй игрок (игрок с 4 очками).
Эрик Outgolfer

Ответы:

11

Желе , 26 байт

ṢŒrṪ4=$$Ðfx3ðœ-µẆm€6R¤;/µL

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

Формат ввода немного необычный; это строка, представляющая доску, но с символами новой строки Windows (перевод каретки с последующим переводом строки). Например, XXO\r\nOXO\r\nOOX. (На самом деле, любая двухсимвольная строка заполнения между строками работает, но переводы строки Windows гораздо более оправданы, чем другие варианты.)

Основная идея заключается в том, что мы ищем символы, которые появляются 4 раза на входе, но не имеют трех равномерно распределенных вхождений в исходной строке. С двумя или более символами заполнения между линиями сетки 3 × 3 все горизонтальные, вертикальные и диагональные линии расположены равномерно, но никакая другая равномерно не может содержать три элемента.

Объяснение:

Символы ðи µявляются разделителями цепей , которые разбивают программу на несколько частей, каждая из которых независима. Я заменил их пробелами ниже, чтобы сделать вещи немного яснее.

ṢŒrṪ4=$$Ðfx3 œ- Ẇm€6R¤;/ L
Ṣ                           sorted version of the input
 Œr                         run-length-encode it
        Ðf                  keep only elements where
   Ṫ                        delete the last element, and it was
    4=                      equal to 4
      $$                    parse Ṫ4= as a group
          x3                repeat each element three times

                Ẇ           all sublists of the input
                 m€         take every nth element of each (€) sublist
                   6R       for each n in 1..6
                     ¤      parse 6R as a group
                      ;/    flatten one level (m€ creates a nested structure)

             œ-             multiset difference
                         L  length of that difference

Другими словами, мы находим список символов, которые появляются ровно четыре раза на входе, и составляем список, состоящий из трех копий каждого из них; мы находим список всех подпоследовательностей, которые равномерно распределены в исходной строке; и если мы вычтем второе из первого, мы хотим, чтобы результат имел длину 1 (то есть игрок сыграл четыре раза, но не выиграл). Обратите внимание, что, поскольку мы находимся в сетке 3 × 3 и каждый квадрат заполнен, оба игрока не могут играть четыре раза. В Jelly 1 - истина, 0 - ложь, поэтому нам не нужно делать ничего особенного, чтобы преобразовать полученный список в логическое значение. ( µLТребуется, однако, потому что в противном случае и то “XXX”и другое “OOO”были бы возможны истинные выходные значения, и вопрос требует, чтобы все действительные платы давали одинаковый вывод.)

Грег Мартин
источник
3
Это полностью читабельно.
Пабрамс
21

JavaScript (ES6), 88 87 байт

s=>(a=[...s]).sort()[5]-a[3]&[7,56,73,84,146,273,292,448].every(j=>j&i,i=`0b`+s^~-a[4])

Принимает входной сигнал в виде строки из 9 0и 1символов и возвращается 1за действительное, 0для инвалида. Мы сортируем персонажей по порядку. Если средние три символа теперь одинаковы, то доска является недействительной, так как слишком много одного куска. В противном случае мы конвертируем исходную плату в двоичную, переворачивая биты, если больше 0s, чем 1s. На этом этапе плата действительна, если 0не имеет строки из трех, поэтому мы просто тестируем все восемь строк с помощью массива битовых масок. Редактировать: 1 байт сохранен благодаря @ETHproductions.

Нил
источник
@ETHproductions А, конечно, результат будет 0 или 1 в любом случае.
Нил
14

Python 3, 131 127 125 100 96 байт

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

def z(b):return int('agqozfx67wwye6rxr508ch2i8qicekpreqkap0725pk',36)<<24&1<<b+(b>255)*(511-b-b)

Значение теста:

X X X
O X O
X X X

Представляется в виде двоичного значения 0b111010111, и функция возвращает ненулевое значение, если плата действительна.

Кен Я.Н.
источник
Удалена промежуточная переменная на 4 байта меньше
Кен YN
На два байта меньше, так как a&(1<<b)скобки не нужны.
Кен Ю.Н.
Сбил 25 байтов, используя симметрию, и еще один, сократив 24 младших бита - должен быть способ сделать это лучше if b>255:b=511-b!
Кен Ю.Н.
Нашел более подходящий способ сделать это if.
Кен YN
11

Пакет, 140 байт

@set/aXXX=OOO=O=0
@for %%l in (%* %1%2%3 %1%4%7 %1%5%9 %2%5%8 %3%5%7 %3%6%9 %4%5%6 %7%8%9)do @set/a%%l+=1
@cmd/cset/a!XXX*!(O-=5)+!OOO*!~O

Принимает input как девять отдельных аргументов командной строки и выводит их 1как действительные и 0недействительные. Работает, отслеживая количество раз, когда он видит Oи ортогональную линию OOOили XXX. Удобно, что Batch позволяет нам выполнять целочисленную арифметику косвенно, поэтому мы не увеличиваем, %%lа вместо этого используем некоторую переменную (хотя нас интересуют только три упомянутые переменные). Затем нам нужно проверить, что либо Xне выиграло, и есть пять Oс, либо Oне выиграло, и есть четыре Oс.

Нил
источник
10

Mathematica, 82 75 байт

Спасибо Мартину Эндеру за сохранение 7 байтов!

t=Total;3<(b=#~t~2)<6&&{t[c=If[b>4,1-#,#]],t/@c,Tr@c,Tr@Reverse@c}~FreeQ~3&

Безымянная функция, принимающая 3х3 вложенный список 1 и 0 в качестве входных и выходных данных Trueили False.

Использует некоторую удобную гибкость Totalфункции (здесь игра в гольф t): приведенный пример массива e = { {1,2,3} , {4,5,6} , {7,8,9} }, команда t[e]суммирует три вектора (здесь даются {12,15,18}); команда t/@eсуммирует каждый подсписок индивидуально (здесь приводим {6,15,24}); и команда e~t~2суммирует все девять элементов (здесь результат 45).

Итак, сначала мы проверяем, является 3<(b=#~t~2)<6ли общее число 1 с 4 или 5; если нет, мы выходим с False. Если это так, мы используем, c=If[b>4,1-#,#]чтобы заставить быть четыре 1, а не пять. Затем мы вычисляем суммы столбцов, суммы t[c]строк t/@c, сумму главной диагонали Tr@cи сумму противоположной диагонали Tr@Reverse~c, и используем ~FreeQ~3для проверки, что 3не может появиться на любом уровне в этих вычисленных суммах.

Забавное примечание: в отличие от большинства появлений на этом сайте, здесь Trне используется для суммирования одномерного списка, но на самом деле используется как задумано - для расчета следа двумерной матрицы!

Грег Мартин
источник
6

Pyth - 36 байт

Я включаю Diagas и использую две тройки вместо этого.

JsM+sCBQm@VdU3_BQ?q5KssQ*FJ?qK4!}3JZ

Тестирование

Maltysen
источник
5

JavaScript (ES6), 101 байт

Принимает входные данные в виде 9-битной двоичной маски, где X = 1и O = 0(MSB = верхняя левая ячейка, LSB = нижняя правая ячейка).

n=>[7,56,73,84,146,273,292,448,o=x=0].map((m,i)=>(c-=n>>i&1,m&n^m?m&n||o++:m&&x++),c=4)&&!(c|x&&~c|o)

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

Arnauld
источник
Я знал, что должно быть (несколько) простое побитовое решение. Хорошая работа
ETHproductions
5

Python 2, 158 132 109 92 91 123 байта

def v(b):f=sum(b,());w={x[0]for x in b+zip(*b)+[f[::4],f[-3:1:-2]]if len(set(x))==1};return sum(map(`b`.count,w))==len(w)*5

Входные данные представляют собой список / кортеж строк, каждая из которых состоит из трех кортежей, например:
[('X', 'O', 'X'), ('O', 'X', 'O'), ('X', 'O', 'X')]

Сохранял несколько байтов, игнорируя диагонали в ответе @ Maltysen, что также сокращало следующее выражение.

Спасибо @vaultah за сохранение 17 18 байт.

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

Попробуй это здесь.

объяснение

def v(b):
  f=sum(b,())
  w={x[0]for x in b+zip(*b)+[f[::4],f[-3:1:-2]]if len(set(x))==1}
  return sum(map(`b`.count,w))==len(w)*5

fявляется сплющенным входом для нарезки.
wсодержит символы с выигрышными последовательностями.
Подсчитайте вхождения каждого выигрышного персонажа, который будет равен 0, если wон пуст, или 5, если len(w)равен 1. Сумма 10, если у обоих есть последовательность выигрыша, невозможна. Победитель с 5 означает, что проигравший имеет 4. Вы не можете иметь> 5 без последовательности выигрыша.

Джейк Кобб
источник
lambda b:len({x[0]for x in b+zip(*b)if len(set(x))==1})<2and set(map(b .count,'XO'))=={4,5}сохраняет несколько байтов.
vaultah
и я только что заметил, что ...and{4,5}==set(map(b .count,'XO'))сохраняет еще один байт.
vaultah
Я думаю, что это неправильно считает последний «Неверный» пример из вопроса действительным, потому что это не гарантирует, что победителем станет игрок с 5 баллами.
Smls
@smls Ты прав. Проверка этого состояния стоит много байтов, может быть, это может быть в дальнейшем.
Джейк Кобб
5

R, 88 82 байта

x=scan();`if`(sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F)

Все комбинации трех целых чисел от 1 до 9, которые суммируют до 15, представляют собой строки / столбцы / диагонали квадрата, показанного ниже.

2 7 6
9 5 1
4 3 8

Функция принимает входные данные как вектор логических значений, T для «X», F для «O», который является плоским представлением платы. НО, они переупорядочены так, что их индекс совпадает с числом в квадрате в порядке (2,7,6,9,5,1,4,3,8). Этот порядок может быть достигнут путем выравнивания доски обычным способом, а затем нарезкой на c (6,1,8,7,5,3,2,9,4). Так это

X O X
O X O
X O X

представляется как:

c(T, F, T, F, T, F, T, F, T)[c(6,1,8,7,5,3,2,9,4)]

который:

c(F, T, F, T, T, T, F, T, F)

Функция сначала определяет, есть ли игрок с ровно четырьмя отметками. Если это так, функция использует «факт вещей, которые складываются до 15», чтобы определить, есть ли у этого игрока три в ряд (доска недействительна, если этот игрок делает).

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

f=function(x)ifelse(sum(x)%in%4:5,all(apply(combn(c(2,7,6,9,5,1,4,3,8)[which(x==(sum(x)<5))],3),2,sum)!=15),F)

Я новичок в этом, советы будут оценены.

ixodesbeta
источник
1
Сохранить 2 байта, если вы используете if()вместо: f=function(x)если (sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F). Не всесторонне протестировано. Обратные следы разрушают код, но это так backtick if backtick(.
Джонатан Кэрролл
1
Еще лучше; x=scan();если (sum(x)%in%4:5,all(apply(combn(which(x==(sum(x)<5)),3),2,sum)!=15),F)и ввод как 1и 0. 82 байта.
Джонатан Кэрролл
3

JavaScript (ES6), 145 139 131 127 байт

s=>!(q="XO"[s.split`O`.length-5])|![...s].some((c,i)=>c==q&!/(.)(\1|..(\1|.(\1|.\1.).)..)\1/.test(s.slice(0,i)+0+s.slice(i+1)))

Ввод в виде разделенной пробелами строки, такой как "XOX OXO XOX". Выходы 1для неверной платы, 0для действительной. Это, очевидно, не лучший метод, по крайней мере, не с JavaScript ...

Это в основном проверяет, выполняются ли оба следующих условия:

  • Есть ровно 4 или 5 Oс, И
  • есть по крайней мере один из 5 экземпляров, который создает неопределенную игру при удалении.

Регулярное выражение - проверить, была ли решена игра. Он соответствует доске, если есть какие-либо последовательности длины три из одного символа с 0 (строка), 2 (диагональ вниз-вправо), 3 (столбец) или 4 (диагональ вниз-влево), разделяющие каждую пару.

Тестовый фрагмент

ETHproductions
источник
2

Рубин, 104 99 91 байт

->x{[7,56,448,292,146,73,84,273].none?{|y|b=x.to_i 2;((a=x.count'1')==4?b:a==5?~b:7)&y==y}}

Формат ввода: двоичная строка из 9 символов (0 и 1), представляющая плату, например, первый тестовый пример 101010101. Сначала преобразуйте его в двоичное число, проверьте, равняется ли popcount 4 или 5, если это 5, инвертируйте число, чтобы у нас всегда было 4. Проверьте, совпадают ли три из них (маскируя по горизонтали, вертикали и диагонали).

TL; DR : вернуть false, если игрок с 4-мя выигранными выигрышами, в противном случае - true

Спасибо Джордан за комментарии,

Я не могу воспроизвести строку UTF-8, которая бы сохранила другой байт.

гигабайт
источник
Вы можете заменить .select{...}[0]на .find{...}.
Джордан
И вы можете сохранить еще один байт, заменив массив чисел на "8ǀĤITđ".unpack("U*")(в случае, если что-то теряется при переводе, строка является результатом вызова pack("U*")исходного массива; это 12 байтов).
Джордан
Вы могли бы использовать any?вместо none?, переворачивая вывод и сохраняя целый байт?
Алексис Андерсен
Я пробовал с одним? вместо ни одного? но тогда мне нужна! перевернуть вывод.
GB
1

Perl 6 , 103 99 байт

{my \c=%(.flat.Bag.invert)<5>;?all c,|(.[0]===c if [eq] $_ for |.flat[<0 4 8>,<2 4 6>],|$_,|.&zip)}

Лямбда, которая принимает список списков, как (('X','O','X'), ('O','X','O'), ('X','O','X')), и возвращает Bool.

Это работает так:

  1. Проверьте, какая отметка появляется ровно 5 раз, и сохраните ее в c. (Если метка не появится ровно 5 раз, это будет содержать ложное значение)
  2. Переберите все диагонали, строки и столбцы и отфильтруйте «выигрышные» (т. Е. Те, в которых все три буквы равны) .
  3. Проверьте, cверно ли, и каждая выигрышная линия имеет тип c.
SMLS
источник
1

PHP, 125 байт

for($p=$n=$argv[1];$p;$p/=2)$i+=$p&1;foreach([7,56,448,73,146,292,273,84]as$m)$n&$m^$m?$n&$m||$o++:$x++;echo!$x|!$o&&2>$i^=4;

У меня была та же идея, что и у Арнаулда : плата действительна, если установлено 4 или 5 битов, и либо, Xлибо Oни у кого нет полос (но не обоих).

Чтобы сгенерировать ввод из поля, заменить Xна 1и Oс 0, соединить строки и преобразовать двоичный код в десятичный, предоставив в качестве аргумента командной строки.

печатные издания 1для действительных; пустой вывод для недействительного. Беги с -r.

сломать

// count set bits
for($p=$n=$argv[1];$p;$p/=2)$i+=$p&1;
    /* ($p/=2 takes longer than $p>>=1, but eventually
       $p will come close enough to 0 for the loop to finish */
// count streaks for X and O
foreach([7,56,448,73,146,292,273,84]as$m)
    $n&$m^$m            // ($n masked with streak)!=streak <=> no streak for X
        ?$n&$m||$o++    // true: O has a streak if ($n masked with streak) is empty
        :$x++;          // false: X has a streak
echo!$x|!$o&&2>$i^=4;   // valid if not both have a streak
                        // AND $i is 4 or 5 (toggle 4 -> result 0 or 1)
Titus
источник
1

Swift, 178 байт

func t(i:String)->Bool{let r=i.characters.filter({$0=="X"}).count;let g=i.characters.split(separator:"\n").map(String.init).contains;return(r==5||r==4)&&(!g("XXX") && !g("OOO"))}
Калеб Клеветер
источник
0

ES6 (Javacript), 130, 138117 байт

правок:

  • 21 байт благодаря прекрасному совету @Neil!
  • Первоначальная версия была подвержена ошибке, которая теперь должна быть исправлена ​​по стоимости +8 байт. (Спасибо @ETHproductions за указание на это)

Чрезвычайно простой подход. Возможно, можно играть в гольф немного дальше.

Принимает ввод как 9 отдельных аргументов, 1 и 0

  • 1 для X
  • 0 для O

Аргументы: 1-3 - первый ряд, 4-6 - второй ряд, 7-9 - третий ряд.

Golfed

(a,b,c,d,e,f,g,h,j)=>![a+b+c,d+e+f,g+h+j,a+d+g,b+e+h,c+f+j,a+e+j,g+e+c,7].some(x=>x=="7777307777"[a+b+c+d+e+f+g+h+j])

Интерактивный «Испытательный стенд»

var a=b=c=d=e=f=g=h=j=0;

T=(a,b,c,d,e,f,g,h,j)=>![a+b+c,d+e+f,g+h+j,a+d+g,b+e+h,c+f+j,a+e+j,g+e+c,7].some(x=>x=="7777307777"[a+b+c+d+e+f+g+h+j]);

function test() {
  if(T(a,b,c,d,e,f,g,h,j)) {
     grid.style.backgroundColor='green';
     msg.innerHTML="GOOD"
  } else {
     grid.style.backgroundColor='red';
     msg.innerHTML="BAD"
  }
}
<table id=grid style="background: red">
<thead>
  <tr>
     <td id=msg align="center" colspan="3">BAD</td>
    </tr>
  </thead>
  <tr>
      <td><input type="checkbox" onchange="a=this.checked*1;test();" id="ca"/></td>
      <td><input type="checkbox" onchange="b=this.checked*1;test();" id="cb"/></td>
      <td><input type="checkbox" onchange="c=this.checked*1;test();" id="cc"/></td>
    </tr>
    <tr>
      <td><input type="checkbox" onchange="d=this.checked*1;test();" id="cd"/></td>
      <td><input type="checkbox" onchange="e=this.checked*1;test();" id="ce"/></td>
      <td><input type="checkbox" onchange="f=this.checked*1;test();" id="cf"/></td>
    </tr>
    <tr>
      <td><input type="checkbox" onchange="g=this.checked*1;test();" id="cg"/></td>
      <td><input type="checkbox" onchange="h=this.checked*1;test();" id="ch"/></td>
      <td><input type="checkbox" onchange="j=this.checked*1;test();" id="cj"/></td>
    </tr>
 </table>

дирижабль
источник
Я могу ошибаться, но похоже, что это только проверяет, есть ли победитель. Действительная доска не может иметь победителя; например, [1,0,1,1,0,1,0,1,0]( XOX XOX OXO).
ETHproductions
Да, я потерял отрицание, играя в гольф. Предполагается проверить, что противоположная сторона не является победителем. Должно быть исправлено сейчас. Спасибо !
Цеппелин
(Я начал комментировать перед последним редактированием) Можете ли вы а) писать a+b+c+d+e+f+g+H+iвместо F.reduce((r,c)=>r+=c*1)(в какой момент вам это не нужно F) б) писать .includes(C)(и переходить к Cзначению inline )?
Нил
@ Нил, это, вероятно, сработает, завтра попробую. Спасибо !
Цеппелин
Это OOO XXX OXOпровал?
Исмаэль Мигель