Tworzenie najkrótszy program, aby sprawdzić, kto wygrał w n ^d Tic Tac Toe gry.

Twój program powinien działać, gdy n(szerokość) i d(numer wymiaru) znajdują się w następujących zakresach:

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 ² tj. 3 na 3):

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

n = 3; d = 3(3 ³ tj. 3 na 3 na 3):

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

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

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

n = 6; d = 2(6 ² tj. 6 na 6):

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

I tak dalej.

Zwycięstwo (jeśli grałeś wystarczająco dużo wielowymiarowych kółek i krzyżyk, to tak samo.)

Aby wygrać, jeden gracz musi mieć wszystkie sąsiadujące pola wzdłuż linii. Oznacza to, że gracz musi mieć nruchy na linii, aby zostać zwycięzcą.

Sąsiadujący:

• każda płytka jest punktem; na przykład (0,0,0,0,0) to punkt wd=5
• sąsiadujące płytki są płytkami, więc oba są punktami na tej samej jednostce d-cube. Innymi słowy, odległość Czebyszewa między płytkami wynosi 1.
• innymi słowy, jeśli punkt pprzylega do punktu q, wówczas każda współrzędna w podpowiedniej współrzędnej in qróżni się od niej nie więcej niż o jeden. Dodatkowo przynajmniej para współrzędnych różni się dokładnie o jeden.

Linie:

• Linie są definiowane przez wektory i kafelki. Linia to każda płytka dotknięta równaniem:p0 + t<some vector with the same number of coordinates as p0>

Wejście :

Dane wejściowe będą na STDIN. Pierwszy wiersz danych wejściowych będzie składał się z dwóch liczb noraz dw formie n,d.

Następnie pojawi się linia składająca się ze współrzędnych określających wykonane ruchy. Współrzędne są wymienione w następującej postaci: 1,1;2,2;3,3. Lewy górny róg jest punktem początkowym (0,0 dla 2D). W ogólnym przypadku ta lista będzie wyglądać tak, jakby 1,2,...,1,4;4,0,...,6,0;...pierwsza liczba reprezentowała lewą prawą stronę, drugą górę-dół-ność, trzecią do trzeciego wymiaru itp. Zauważ, że pierwsza współrzędna to Xpierwsza kolej, druga jest Opierwsza kolej, ....

Po wprowadzeniu pojawi się nowy wiersz.

Wyjście :

Wyjście będzie do STDOUT. Wystarczy wskazać, kto wygrał, jeśli ktoś wygrał, lub jeśli jest to remis. Jeśli nie jest to remis ani wygrana, nie wypisuj niczego.

Dodatkowo wskaż, czy doszło do zderzenia ruchu, to znaczy, czy w tym samym miejscu występują co najmniej dwa ruchy.

Jeśli przed zakończeniem wejścia było zwycięstwo / losowanie, Twój program może zrobić, co chce.

Przypadki testowe (ktoś chce coś jeszcze zasugerować?):

Wejście:

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

Przykładowe dane wyjściowe:

X wins

Kolejny możliwy wynik (wymaga wyjaśnienia):

1

Python, 745 578 znaków

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

Wprowadziłem kilka zmian i trochę się zmniejszyłem. Zauważ, że powrót True oznacza, że ​​x wygrał, False oznacza y wygrał, i oznacza, że ​​wykonano nieprawidłowy ruch.

Brak odpowiedzi - Java

Byłem ciekawy, jak wiele różnych sposobów można wygrać dla danego n, d, więc napisałem ten kod, aby wymienić je wszystkie.

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

Testowałem go ręcznie na n, d = 2..3,2..3 i wydaje się, że działa… po tym liczba możliwych sposobów na wygraną rośnie szybko, jak pokazano poniżej:

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

Po wygenerowaniu wszystkich zwycięskich zestawów, mogłem rozszerzyć program, aby sprawdzić dane wejściowe względem zwycięskich zestawów, ale oczywiście ta metoda nigdy nie wygrałaby golfa. Byłem zadowolony, mogąc się tutaj zatrzymać - tyle że wyglądało na to, że mogę znaleźć rozwiązanie w formie zamkniętej dla wielu sposobów na wygraną w funkcji ni d… Jest to liczba sposobów na wygraną = 0,5 ((n + 2) ^ d - n ^ d).

C ++ 794 849 znaków

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

Dane wyjściowe to: „X” (X wygrywa), „O” (O wygrywa) lub „!” (próba nielegalnego ruchu).

To po prostu mapuje punkty do tablicy liniowej i sprawdza wszystkie możliwe podzbiory wielkości n, najpierw pod kątem stałej wartości w X lub O, a następnie pod kątem bycia w linii. Aby sprawdzić, czy są w linii, współrzędne punktów w każdym podzbiorze są sprawdzane pojedynczo; każdy z nich musi albo wzrastać od 0 do n-1, zmniejszać się od n-1 do 0, lub być stały. Punkty są naturalnie uporządkowane w szyku liniowym, więc warto nazwać współrzędną rosnącą lub malejącą dla danego zestawu punktów.

Dziękujemy Howardowi za wskazanie poważnego błędu w pierwszej wersji.

W ramach solidarności z Quincunx muszę zaznaczyć, że byłoby parodią, gdyby wygrała odpowiedź w C ++