Utwórz kontroler wygranych w kółko i krzyżyk

13

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

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

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

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

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

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

n = 6; d = 2(6 2 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
Justin
źródło
Jak definiujesz topologię wymiarów n> 3, aby określić, czym są linie proste wzdłuż przekątnej? Na przykład, czy jakakolwiek linia przechodząca przez 3 sąsiadujące wierzchołki stanowi wygraną na planszy 3⁵? Czy środkowe kwadraty każdej płaszczyzny 3² są połączone z każdym punktem innej płaszczyzny, która ma tę samą krawędź na n-sześcianie?
Komintern
1
@Comintern Jak to jest (prawdopodobnie wytłumaczyłem wyjaśnienie. Zdecydowanie może być prostsze).
Justin
Uwaga: podane przez ciebie definicje sąsiadujących kafelków nie są równoważne (tzn. Nie jest to odległość manhattan równa się jednemu).
Howard
Ponadto należy zdefiniować, że naby wygrać, trzeba wykonać ruchy na linii. (Przepraszam, że nie opublikowałem tych uwag w piaskownicy, ale nawet nie miałem czasu, aby je tam zobaczyć, ponieważ zostały opublikowane tak szybko po piaskownicy.)
Howard
1
Wydaje mi się, że w Prologu powinno być bardzo krótkie rozwiązanie ...
Nate Eldredge

Odpowiedzi:

3

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.

foota
źródło
Niektóre rzeczy: zmień import *na import*. Użyj 1dla Prawda i 0dla Fałsz (usuń Ti F). return -1może być return-1(sprawdź usuwanie spacji). Zmień nazwę swoich metod na metody jednoznakowe. Sprawdź wskazówki dotyczące dalszych optymalizacji.
Justin
Och, dzięki, nie wiedziałem, że możesz zrobić niektóre z tych rzeczy (mianowicie usunąć spację między zwrotem a -1)
foota
Zrobiłem trochę gry w golfa na twoim kodzie (może nie wszystkie są poprawne). Wynik jest tutaj: ideone.com/Ld2jAH . Przejrzyj ponownie swoją odpowiedź i maksymalnie skróć kod. Wskazówki pytanie o Python jest bardzo przydatna
Justin
@foota Możesz zrobić if l<>q:zamiast if not l==q:.
mbomb007
3

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

Wally
źródło
2

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 ++

Eric Tressler
źródło
1
Myślę, że chociaż można powiedzieć, że bycie w linii oznacza postęp arytmetyczny, nie ma odwrotnej strony (np. 0,2,4 nie będzie rozwiązaniem dla standardowego 3,2 tic tac toe).
Howard
@ Howard, dzięki. Wprowadziłem poprawki. Jest już za późno, abym skończył grać w golfa, ale udało mi się to naprawić (tak myślę).
Eric Tressler
Możesz dalej grać w golfa, używając różnych wyników. Nie musisz mówić dokładnie X winsani O wins. Jest całkowicie uzasadnione, aby generować 1lub 2(lub inną odmianę), o ile wyjaśnisz w odpowiedzi, co oznaczają. Jak powiedziałem (podkreślenie dodane): „ wskaż, kto wygrał”.
Justin
Gotowy. A jeśli nauczę się, jak działa operator trójskładnikowy, mogę zapisać kilka znaków.
Eric Tressler,
A co z krawatami?
Justin