Crear el programa más corto para comprobar que ha ganado en un n ^d juego de tic tac toe.

Su programa debería funcionar cuando n(ancho) y d(número de dimensión) están en estos rangos:

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 ² es decir, 3 por 3):

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

n = 3; d = 3(3 ³ es decir, 3 por 3 por 3):

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

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

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

n = 6; d = 2(6 ² es decir, 6 por 6):

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

Y así.

Ganar (si has jugado suficientes tic tac toe multidimensionales, esto es lo mismo).

Para que haya una victoria, un jugador debe tener todos los cuadrados adyacentes a lo largo de una línea. Es decir, ese jugador debe tener nmovimientos en una línea para ser un ganador.

Adyacente:

• cada azulejo es un punto; por ejemplo (0,0,0,0,0) es un punto end=5
• las fichas adyacentes son fichas, de modo que ambos son puntos en la misma unidad d-cubo. En otras palabras, la distancia de Chebyshev entre las fichas es 1.
• en otras palabras, si un punto pes adyacente a un punto q, entonces cada coordenada en pla coordenada correspondiente no qdifiere de ella en más de uno. Además, al menos en el par de coordenadas difiere exactamente en uno.

Líneas:

• Las líneas están definidas por vectores y un mosaico. Una línea es cada mosaico golpeado por la ecuación:p0 + t<some vector with the same number of coordinates as p0>

Entrada :

La entrada será a STDIN. La primera línea de entrada será dos números, ny den la forma n,d.

Después de esto, habrá una línea que consiste en coordenadas que especifican los movimientos que se han realizado. Coordenadas se mostrarán en el formulario: 1,1;2,2;3,3. La esquina superior izquierda es el origen (0,0 para 2D). En el caso general, esta lista será como 1,2,...,1,4;4,0,...,6,0;...donde el primer número representa izquierda-derecha-ness, el segundo arriba-abajo-ness, el tercero a la 3ra dimensión, etc. Tenga en cuenta que la primera coordenada es Xel primer giro, el segundo es Oel primer turno ...

La entrada será seguida por una nueva línea.

Salida :

La salida será a STDOUT. Simplemente indique quién ganó si alguien ganó, o si es un empate. Si no es un empate ni una victoria, no generes nada.

Además, indique si hay un choque de movimientos, es decir, si hay al menos dos movimientos en la misma ubicación.

Si hubo una victoria / empate antes de que finalizara la entrada, su programa puede hacer lo que quiera.

Casos de prueba (¿alguien quiere sugerir algo más?):

Entrada:

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

Salida de ejemplo:

X wins

Otra salida posible (requiere explicación):

1

Python, 745 578 caracteres

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

Hice algunos cambios y lo reduje bastante. Tenga en cuenta que un retorno de Verdadero significa que x ha ganado, Falso significa que ganó, y significa que se realizó un movimiento no válido.

No es una respuesta - Java

Tenía curiosidad por ver cuántas maneras diferentes había de ganar para un determinado n, d, así que escribí este código para enumerarlos a todos.

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

Lo probé a mano en n, d = 2..3,2..3 y parece funcionar ... después de eso, la cantidad de formas posibles de ganar crece rápidamente como se muestra a continuación:

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

Después de haber generado todos los conjuntos ganadores, podría extender el programa para verificar la entrada dada contra los conjuntos ganadores, pero, por supuesto, ese método nunca ganaría el golf. Así que me contenté con detenerme aquí, excepto que parecía que podría encontrar una solución de forma cerrada para la cantidad de formas de ganar en función de n y d ... Es la cantidad de formas de ganar = 0.5 ((n + 2) ^ d - n ^ d).

C ++ 794849 caracteres

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

La salida es: "X" (X gana), "O" (O gana) o "!" (intento de movimiento ilegal).

Esto simplemente asigna los puntos en una matriz lineal y verifica todos los subconjuntos posibles de tamaño n, primero por ser constantes en X u O, y luego por estar en una línea. Para verificar que esté en una línea, las coordenadas de los puntos en cada subconjunto se examinan de una en una; cada uno debe estar aumentando de 0 a n-1, disminuyendo de n-1 a 0, o constante. Los puntos se ordenan naturalmente en la matriz lineal, por lo que tiene sentido llamar a una coordenada aumentando o disminuyendo para un conjunto dado de puntos.

Gracias a Howard por señalar un grave error en la primera versión.

En solidaridad con Quincunx, debo señalar que sería una parodia si gana una respuesta de C ++