Erstellen Sie das kürzeste Programm, um zu überprüfen, wer in einem n ^d tic tac toe-Spiel gewonnen hat.

Ihr Programm sollte funktionieren, wenn n(width) und d(dimension number) in diesen Bereichen liegen:

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, dh 3 mal 3):

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

n = 3; d = 3(3 ³ dh 3 mal 3 mal 3):

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

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

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

n = 6; d = 2(6 ^2, dh 6 mal 6):

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

Und so weiter.

Gewinnen (Wenn Sie genug mehrdimensionales Tic Tac Toe gespielt haben, ist dies dasselbe.)

Um zu gewinnen, muss ein Spieler alle angrenzenden Felder entlang einer Linie haben. Das heißt, dieser Spieler muss nZüge auf einer Linie haben, um ein Gewinner zu sein.

Benachbart:

• jedes Plättchen ist ein Punkt; Zum Beispiel (0,0,0,0,0) ist ein Punkt ind=5
• Benachbarte Kacheln sind solche Kacheln, die beide Punkte auf derselben Einheit d-Würfel sind. Mit anderen Worten beträgt der Chebyshev-Abstand zwischen den Kacheln 1.
• Mit anderen Worten, wenn ein Punkt pan einen Punkt angrenzt q, unterscheidet sich jede Koordinate in der pentsprechenden Koordinate qdarin nicht mehr als um eins. Außerdem unterscheidet sich mindestens ein Koordinatenpaar um genau eins.

Linien:

• Linien werden durch Vektoren und eine Kachel definiert. Eine Linie ist jedes Plättchen, das von der folgenden Gleichung getroffen wird:p0 + t<some vector with the same number of coordinates as p0>

Eingabe :

Die Eingabe erfolgt in STDIN. Die erste Zeile der Eingabe wird zwei Zahlen, sein nund din der Form n,d.

Danach wird eine Linie aus Koordinaten erstellt, die die durchgeführten Bewegungen angeben. Die Koordinaten werden in Form aufgeführt werden: 1,1;2,2;3,3. Die obere linke Ecke ist der Ursprung (0,0 für 2D). Im allgemeinen Fall entspricht diese Liste der Stelle, 1,2,...,1,4;4,0,...,6,0;...an der die erste Zahl die Links-Rechts-Position, die zweite Auf-Ab-Position, die dritte bis dritte Dimension usw. darstellt. Beachten Sie, dass die erste Koordinate die Xerste und die zweite Kurve ist ist Os erste Runde, ....

Der Eingabe folgt eine neue Zeile.

Ausgabe :

Die Ausgabe erfolgt nach STDOUT. Geben Sie einfach an, wer gewonnen hat, wenn jemand gewonnen hat oder ob es ein Unentschieden ist. Wenn es weder ein Unentschieden noch ein Sieg ist, gib nichts aus.

Geben Sie außerdem an, ob es einen Zugkonflikt gibt, dh, ob sich mindestens zwei Züge an derselben Position befinden.

Wenn vor dem Ende der Eingabe ein Gewinn / Unentschieden stattgefunden hat, kann Ihr Programm tun, was es will.

Testfälle (will jemand noch mehr vorschlagen?):

Eingang:

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

Beispielausgabe:

X wins

Eine andere mögliche Ausgabe (Erklärung erforderlich):

1

Python, 745 578 Zeichen

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

Ich habe ein paar Änderungen vorgenommen und es ziemlich verkleinert. Beachten Sie, dass eine Rückgabe von True bedeutet, dass x gewonnen hat, False bedeutet, dass y gewonnen hat, und bedeutet, dass ein ungültiger Zug ausgeführt wurde.

Keine Antwort - Java

Ich war neugierig, wie viele verschiedene Möglichkeiten es gibt, um für ein bestimmtes n zu gewinnen, und schrieb diesen Code, um sie alle aufzulisten.

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

Ich habe es von Hand auf n getestet, d = 2..3.2..3 und es scheint zu funktionieren ... danach wächst die Anzahl der möglichen Gewinnmöglichkeiten schnell, wie unten gezeigt:

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

Nachdem ich alle Gewinnsätze generiert hatte, konnte ich das Programm erweitern, um die angegebenen Eingaben mit Gewinnsätzen zu vergleichen, aber natürlich würde diese Methode niemals den Golf gewinnen. Also war ich damit zufrieden, hier anzuhalten - außer es sah so aus, als ob ich eine geschlossene Lösung für die Anzahl der Gewinnmöglichkeiten in Abhängigkeit von n und d finden könnte… Es ist Anzahl der Gewinnmöglichkeiten = 0,5 ((n + 2) ^ d - n ^ d).

C ++ 794 849 Zeichen

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

Ausgabe ist: "X" (X gewinnt), "O" (O gewinnt) oder "!" (illegaler Zugversuch).

Dies ordnet nur die Punkte in einem linearen Array zu und überprüft alle möglichen Teilmengen der Größe n, um zuerst bei X oder O konstant zu sein und dann um in einer Linie zu sein. Um zu überprüfen, ob eine Linie vorliegt, werden die Koordinaten der Punkte in jeder Teilmenge einzeln überprüft. Sie müssen entweder von 0 auf n-1 ansteigen, von n-1 auf 0 abfallen oder konstant sein. Die Punkte sind natürlich in der linearen Anordnung angeordnet, daher ist es sinnvoll, eine Koordinate für eine gegebene Menge von Punkten zu erhöhen oder zu verringern.

Vielen Dank an Howard für den Hinweis auf einen schwerwiegenden Fehler in der ersten Version.

Aus Solidarität mit Quincunx muss ich darauf hinweisen, dass es eine Farce wäre, wenn eine C ++ - Antwort gewinnt