Erstellen Sie ein "n" für den Dictic Tac Toe Win-Checker

13

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 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
Justin
quelle
Wie definieren Sie die Topologie der Dimensionen n> 3, um zu bestimmen, was eine Gerade entlang einer Diagonale ist? Ist zum Beispiel eine Linie durch 3 benachbarte Eckpunkte ein Gewinn auf einem 3⁵-Brett? Sind die mittleren Quadrate jeder 3²-Ebene mit jedem Punkt einer anderen Ebene verbunden, die eine Kante mit dem n-Würfel teilt?
Comintern
1
@Comintern Wie ist das (ich habe wahrscheinlich die Erklärung abgeschlachtet. Könnte definitiv einfacher sein).
Justin
Hinweis: Die Definitionen, die Sie für benachbarte Kacheln angegeben haben, sind nicht äquivalent (dh die Entfernung in Manhattan ist nicht gleich eins).
Howard
Außerdem sollten Sie festlegen, dass nZüge auf einer Linie erforderlich sind, um ein Gewinner zu sein. (Es tut mir leid, dass ich diese Bemerkungen nicht in der Sandbox gepostet habe, aber ich hatte nicht einmal Zeit, sie dort zu sehen, weil sie so bald nach dem Sandboxen gepostet wurden.)
Howard,
1
Ich denke, es sollte eine sehr kurze Lösung in Prolog geben ...
Nate Eldredge

Antworten:

3

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.

foota
quelle
Einige Dinge: wechseln import *zu import*. Verwenden Sie 1für True und 0für False (Entfernen Tund F). return -1kann sein return-1(siehe Leerzeichen entfernen). Benennen Sie Ihre Methoden in einzelne Zeichenmethoden um. Lesen Sie die Tipps für weitere Optimierungen.
Justin
Oh, danke, ich wusste nicht, dass Sie einige dieser Dinge tun können (nämlich das Leerzeichen zwischen return und -1 entfernen)
foota
Ich habe ein bisschen an Ihrem Code Golf gespielt (das ist möglicherweise nicht alles gültig). Das Ergebnis ist hier: ideone.com/Ld2jAH . Bitte gehen Sie Ihre Antwort noch einmal durch und kürzen Sie den Code so weit wie möglich. Die Tipps Frage für Python ist sehr nützlich
Justin
@foota Du kannst if l<>q:statt if not l==q:.
mbomb007
3

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).

Wally
quelle
2

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

Eric Tressler
quelle
1
Ich denke, während man sagen kann, dass das In-Line-Verhalten eine arithmetische Progression impliziert, ist es nicht umgekehrt (z. B. 0,2,4 ist keine Lösung für das Standard-3,2-Tic-Tac-Toe-Verfahren).
Howard
@Howard, danke. Ich habe die Korrekturen vorgenommen. Es ist jetzt zu spät, um mit dem Golfen fertig zu werden, aber ich konnte es reparieren (glaube ich).
Eric Tressler
Sie können weiter Golf spielen, indem Sie verschiedene Ausgänge verwenden. Du musst nicht genau sagen X winsoder O wins. Die Ausgabe von 1oder 2(oder einer anderen Variation) ist vollkommen legitim, solange Sie in Ihrer Antwort erklären, wofür sie stehen. Wie gesagt (Hervorhebung hinzugefügt): " Geben Sie an, wer gewonnen hat".
Justin
Erledigt. Und wenn ich lernen kann, wie der ternäre Operator funktioniert, kann ich ein paar Zeichen speichern.
Eric Tressler
Was ist mit Krawatten?
Justin