Создайте n-d-tic tac toe win-checker

13

Создать самую короткую программу , чтобы проверить , кто выиграл в п й Tic Tac Toe игры.

Ваша программа должна работать, когда n(ширина) иd (номер измерения) находятся в следующих диапазонах:

n∈[3,6]∩ℕ  ie a number from this list: 3,4,5,6
d∈[2,5]∩ℕ  ie a number from this list: 2,3,4,5

n = 3; d = 2(3 2 т.е. 3 на 3):

[][][]
[][][]
[][][]

n = 3; d = 3(3 3 т.е. 3 на 3 на 3):

[][][]
[][][]
[][][]

[][][]
[][][]
[][][]

[][][]
[][][]
[][][]

n = 6; d = 2(6 2 т.е. 6 на 6):

[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]

И так далее.

выигрыш (если вы играли достаточно многомерных крестики-нолики, это то же самое.)

Чтобы победа была, у одного игрока должны быть все смежные квадраты вдоль линии. То есть этот игрок должен иметьn ходы на линии, чтобы быть победителем.

Рядом:

  • каждая плитка - это точка; например (0,0,0,0,0) является точкой вd=5
  • соседние плитки - это плитки, так что они обе являются точками на одном и том же d-кубе. Другими словами, расстояние Чебышева между плитками равно 1.
  • другими словами, если точка pсмежна с точкой q, то каждая координата в ps соответствующей координате qотличается от нее не более чем на единицу. Кроме того, хотя бы пара координат отличается ровно на одну.

линии:

  • Линии определяются векторами и плиткой. Линия - это каждая ячейка, пораженная уравнением:p0 + t<some vector with the same number of coordinates as p0>

вход :

Вход будет в STDIN. Первая строка ввода будет двумя числами, nи dв видеn,d .

После этого будет строка, состоящая из координат, определяющих ходы, которые были сделаны. Координаты будут перечислены в следующем виде: 1,1;2,2;3,3. Верхний левый угол - это начало координат (0,0 для 2D). В общем случае этот список будет аналогичен тому, 1,2,...,1,4;4,0,...,6,0;...где первое число представляет левый-правый, второй-вверх-вниз, с третьего по третье измерение и т. Д. Обратите внимание, что первая координата - это Xпервый поворот, второй Это Oпервый поворот, ....

За вводом последует новая строка.

Выход :

Выход будет на STDOUT. Просто укажите, кто выиграл, если кто-то выиграл или это ничья. Если это не ничья и не победа, ничего не выводите.

Кроме того, укажите, есть ли столкновение ходов, то есть если в одном и том же месте есть как минимум два хода.

Если до завершения ввода была победа / ничья, ваша программа может делать все, что захочет.

Тестовые случаи (кто-нибудь хочет предложить больше?):

Входные данные:

4,3
0,0,0;1,1,1;1,0,1;2,0,2;0,0,1;2,0,0;2,0,1;3,0,2;3,0,1

Пример вывода:

X wins

Другой возможный вывод (требует объяснения):

1
Джастин
источник
Как вы определяете топологию измерений n> 3 для определения, что такое прямые вдоль диагонали? Например, является ли какая-либо линия через любые 3 смежные вершины победой на доске 3 on? Связаны ли средние квадраты каждой плоскости 3² с каждой точкой другой плоскости, имеющей с ней ребро на n-кубе?
Коминтерн
1
@Comintern Как это (я, вероятно, вырезал объяснение. Определенно может быть проще).
Джастин
Примечание: определения, которые вы дали для соседних плиток, не эквивалентны (то есть, это не манхэттенское расстояние равно единице).
Говард
Более того, вы должны определить, что для того, nчтобы стать победителем, нужны ходы на линии. (Извините, что не разместил эти замечания в песочнице, но у меня даже не было времени даже увидеть их там, потому что они были опубликованы так скоро после песочницы.)
Говард
1
Я чувствую, что должно быть очень короткое решение в Прологе ...
Нейт Элдредж

Ответы:

3

Python, 745 578 символов

import sys
x=[]
o=[]
t=1
b=","
k=map
def m(c):
 m=x if t else o
 c=k(int,c.split(b))
 if c in o+x:
  print b
  sys.exit()
 m.append(c)
 r=0
 for p in m:
  r=w(p,m)
 return r
def w(p,m):
 for q in m:
  d=max(k(lambda x,y:abs(x-y),p,q))
  if d==u:
   if e(p,q,m):
    return 1
 return 0
def e(p,q,m):
 v=k(lambda p,q:(p-q)/u,q,p)
 l=p
 for i in range(1,n):
  y=k(lambda j,h:j+h,l,v)
  if y not in m:
   return 0
  l=y
 if not l==q:
  return 0
 return 1
q=sys.stdin.readline
d=q()
v=q()
z=d.split(b)
(n,d)=k(int,z)
a=v.split(";")
u=n-1
for c in a:
 r=m(c)
 if r:
  print t
 t=not t

Я сделал некоторые изменения и сократил их немного. Обратите внимание, что возврат True означает, что x выиграл, False означает, что y выиграл, и означает, что был сделан неверный ход.

foota
источник
Некоторые вещи: изменить import *на import*. Используйте 1для True и 0для False (удалить Tи F). return -1может быть return-1(проверить удаление пробелов). Переименуйте ваши методы в одиночные методы char. Ознакомьтесь с советами по оптимизации.
Джастин
О, спасибо, я не знал, что вы могли бы сделать некоторые из этих вещей (а именно, убрать пробел между return и -1)
foota
Я немного поиграл в ваш код (это может быть не все правильно). Результат здесь: ideone.com/Ld2jAH . Пожалуйста, повторите ваш ответ еще раз и сократите код, насколько это возможно. Советы вопрос питона очень полезно
Джастин
@foota Вы можете сделать if l<>q:вместо if not l==q:.
mbomb007
3

Не ответ - Java

Мне было любопытно посмотреть, сколько было способов выиграть для данного n, d, поэтому я написал этот код, чтобы перечислить их все.

import java.util.*;

public class MultiDTTT {
    static Set<Win> wins = new HashSet<Win>();
    static final int d = 3;
    static final int n = 3;
    static final char maxChar = (char)(n-1) + '0'; 

    public static void main(String[] args) throws Exception {
        String pad = "";
        for(int i=0; i<d; i++) pad = pad + "0";
        for(int i=0; i<Math.pow(n,d); i++) {
            String s = Integer.toString(i,n);
            s = pad.substring(s.length()) + s;
            buildWin(s,"",0);
        } 
        System.out.println(wins.size());
        for(Win w : wins) System.out.println(w.toString());
    }

    static void buildWin(String s, String p,int i) {
        if(i<d) {
            if(s.charAt(i) == '0') {
                buildWin(s,p+"u",i+1);
                buildWin(s,p+"s",i+1);
            }
            else if(s.charAt(i) == maxChar) {
                buildWin(s,p+"d",i+1);
                buildWin(s,p+"s",i+1);
            }
            else {
                buildWin(s,p+"s",i+1);
            }
        }
        else {
            if(p.contains("u") || p.contains("d")) wins.add(new Win(s,p));
        }
    }

    static class Win {
        String start;
        String pattern;
        Set<String> list = new HashSet<String>();

        Win(String s, String p) {
            start = s;
            pattern = p;
            char[] sc = s.toCharArray();
            for(int i=0; i<n; i++) {
                list.add(new String(sc));
                for(int j=0; j<d; j++) {
                    switch (p.charAt(j)) {
                        case 'u':
                            sc[j]++;
                            break;
                        case 'd':
                            sc[j]--;
                            break;
                        case 's':
                            break;
                    }
                }
            }
        }

        public String toString() {
            String s = ""; //start + ", " + pattern + "\n    ";
            for(String ss : list) s = s + ss + " ";
            return s;
        }

        public boolean equals(Object x) {
            return (x instanceof Win) && this.list.equals(((Win)x).list);
        }
        public int hashCode(){
            return list.hashCode();
        }
    }
}

Я проверил это вручную на n, d = 2..3,2..3, и он, кажется, работает… после этого число возможных способов выиграть быстро растет, как показано ниже:

n       1       2       3       4       5       6
d                           
1       1       1       1       1       1       1
2       1       6       8       10      12      14
3       1       28      49      76      109     148
4       1       120     272     520     888     1400
5       1       496     1441    3376    6841    12496
6       1       2016    7448    21280   51012   107744

Сгенерировав все выигрышные наборы, я мог бы расширить программу, чтобы сравнить данные с выигрышными сетами, но, конечно, этот метод никогда не выиграл бы в гольфе. Так что я был рад остановиться здесь - за исключением того, что выглядело так, как будто я мог найти решение в закрытой форме для количества способов выиграть в зависимости от n и d… Это Количество способов выиграть = 0,5 ((n + 2) ^ d - n ^ d).

бестолочь
источник
2

C ++ 794 849 символов

#include <algorithm>
#include <iostream>
#include <cmath>
#include <string>
#define _ return
#define Y int
#define Z(a) cout<<#a
#define W(a,b,c) for(a=c;a++<b;)
using namespace std;Y n,d,A[5],P[6],T=1,x[7776]={},i,j,k,a,z,p=pow(n,d);char c;bool B;string s;Y K(){a=P[j];W(k,i,0)a/=n;_ a%n;}Y M(){j=0;z=K();W(j,n,1){if(K()!=z){_ 1;}}_ 0;}Y N(){W(j,n,0)if(K()!=n-1-j)_ 1;_ 0;}Y O(){W(j,n,0)if(K()!=j)_ 1;_ 0;}Y S(){z=0;W(i,d,0){z*=n;z+=A[i];}_ z;}Y C(){a=z=0;W(i,p,0){if(s[i]-'0'){P[z]=i;++z;if(a){if(x[i]!=a)_ 0;}else a=x[i];}}_ a;}Y L(){W(i,d,0)if(M()*N()*O())_ 0;_ 1;}Y main(){cin>>n>>c>>d;while(1){W(i,d,0)B=cin>>A[i]>>c;if(x[S()]){Z(!);_ 0;}x[S()]=T;T*=-1;if(!B)break;}W(i,p,0)i<n?s+="1":s+="0";do if(C()&&L()){C()==1?Z(X):Z(O);_ 0;}while(prev_permutation(s.begin(),s.end()));_ 0;}

Вывод: «X» (X побед), «O» (O побед) или «!» (незаконная попытка переезда).

Это просто отображает точки в линейный массив и проверяет все возможные подмножества размера n, сначала на постоянство в X или O, а затем на наличие в линии. Чтобы проверить нахождение в линии, координаты точек в каждом подмножестве проверяются по одному; каждый из них должен либо увеличиваться от 0 до n-1, уменьшаться от n-1 до 0, либо быть постоянным. Точки естественным образом упорядочены в линейном массиве, поэтому имеет смысл называть координаты, увеличивающиеся или уменьшающиеся для данного набора точек.

Спасибо Говарду за указание на серьезную ошибку в первой версии.

В знак солидарности с Quincunx я должен отметить, что в случае победы C ++ победа будет пародией

Эрик Тресслер
источник
1
Я думаю, что хотя вы можете сказать, что нахождение в очереди подразумевает арифметическую прогрессию, оно не удерживает обратное (например, 0,2,4 не будет решением для стандартного 3,2 крестика).
Говард
@ Говард, спасибо. Я внес исправления. Сейчас уже слишком поздно, чтобы закончить игру в гольф, но я смог это исправить (я думаю).
Эрик Тресслер
Вы можете играть в гольф дальше, используя различные выходы. Вы не должны сказать точноX wins или O wins. Вполне законно выводить 1или 2(или некоторые другие варианты), если вы объясните в своем ответе, что они обозначают. Как я уже сказал (выделение добавлено): « укажите, кто победил».
Джастин
Выполнено. И если я смогу узнать, как работает троичный оператор, я могу сохранить несколько символов.
Эрик Тресслер
Как насчет связей?
Джастин