Criar o programa mais curto para verificar quem ganhou em uma n ^d tic tac toe game.

Seu programa deve funcionar quando n(largura) e d(número da dimensão) estiverem nestes intervalos:

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 ² ou seja, 3 por 3):

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

n = 3; d = 3(3 ³ ou seja, 3 por 3 por 3):

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

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

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

n = 6; d = 2(6 ² ou seja, 6 por 6):

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

E assim por diante.

Vencendo (Se você já jogou o suficiente jogo da velha multidimensional, é o mesmo.)

Para que haja uma vitória, um jogador deve ter todos os quadrados adjacentes ao longo de uma linha. Ou seja, esse jogador deve ter nmovimentos em uma linha para ser um vencedor.

Adjacente:

• cada peça é um ponto; por exemplo (0,0,0,0,0) é um ponto emd=5
• peças adjacentes são peças tais que são os dois pontos na mesma unidade d-cubo. Em outras palavras, a distância Chebyshev entre os blocos é 1.
• em outras palavras, se um ponto pé adjacente a um ponto q, então todas as coordenadas em ps coordenadas correspondentes qdiferem dele em não mais que um. Além disso, pelo menos no par de coordenadas difere em exatamente um.

Linhas:

• As linhas são definidas por vetores e um bloco. Uma linha é cada bloco atingido pela equação:p0 + t<some vector with the same number of coordinates as p0>

Entrada :

A entrada será para STDIN. A primeira linha de entrada será dois números ne dno formato n,d.

Depois disso, haverá uma linha composta por coordenadas, especificando os movimentos que foram feitos. Coordenadas serão listados no formulário: 1,1;2,2;3,3. O canto superior esquerdo é a origem (0,0 para 2D). No caso geral, essa lista será como 1,2,...,1,4;4,0,...,6,0;...onde o primeiro número representa esquerda-direita, a segunda cima-baixo, a terceira até a terceira dimensão, etc. Observe que a primeira coordenada é Xa primeira volta, a segunda é Oa primeira vez, ....

A entrada será seguida por uma nova linha.

Saída :

A saída será para STDOUT. Basta indicar quem ganhou se alguém ganhou ou se é um empate. Se não houver empate nem vitória, não produza nada.

Além disso, indique se há um conflito de movimentação, ou seja, se houver pelo menos duas jogadas no mesmo local.

Se houve uma vitória / empate antes do término da entrada, seu programa pode fazer o que quiser.

Casos de teste (alguém quer sugerir mais?):

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

Saída de exemplo:

X wins

Outra saída possível (requer explicação):

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

Fiz algumas alterações e reduzi-o bastante. Observe que um retorno de True significa que x ganhou, Falso significa y ganhou e significa que uma jogada inválida foi feita.

Não é uma resposta - Java

Eu estava curioso para ver quantas maneiras diferentes de ganhar para um determinado n, d, então escrevi esse código para listar todas elas.

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

Eu testei manualmente em n, d = 2..3,2..3 e parece funcionar ... depois disso, o número de maneiras possíveis de ganhar cresce rapidamente, como mostrado abaixo:

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

Tendo gerado todos os conjuntos de vitórias, eu poderia estender o programa para verificar a entrada fornecida contra os conjuntos vencedores, mas, é claro, esse método nunca venceria o golfe. Então, eu estava contente em parar por aqui - exceto que parecia que eu poderia encontrar uma solução de forma fechada para o número de maneiras de ganhar em função de n e d… É o número de maneiras de ganhar = 0,5 ((n + 2) ^ d - n ^ d).

C ++ 794 849 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;}

A saída é: "X" (X vence), "O" (O vence) ou "!" (tentativa de movimento ilegal).

Isso apenas mapeia os pontos em uma matriz linear e verifica todos os subconjuntos possíveis de tamanho n, primeiro por serem constantes em X ou O e depois por estarem em uma linha. Para verificar se há uma linha, as coordenadas dos pontos em cada subconjunto são examinadas uma de cada vez; cada um deve aumentar de 0 a n-1, diminuir de n-1 a 0 ou ser constante. Os pontos são ordenados naturalmente na matriz linear; portanto, faz sentido chamar uma coordenada aumentando ou diminuindo para um determinado conjunto de pontos.

Agradecemos a Howard por apontar um erro grave na primeira versão.

Em solidariedade ao Quincunx, devo salientar que seria uma farsa se uma resposta em C ++ vencesse