Create an n to the d tic tac toe win-checker

Create the shortest program to check who has won in an nd tic tac toe game.

Your program should work when n (width) and d (dimension number) are in these ranges:

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 (32 ie 3 by 3):

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

n = 3; d = 3 (33 ie 3 by 3 by 3):

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

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

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

n = 6; d = 2 (62 ie 6 by 6):

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

And so on.

Winning (If you've played enough multi-dimensional tic tac toe, this is the same.)

In order for there to be a win, one player must have all the adjacent squares along a line. That is, that player must have n moves on a line to be a winner.

• each tile is a point; for example (0,0,0,0,0) is a point in d=5
• adjacent tiles are tiles such they are both points on the same unit d-cube. In other words, the Chebyshev distance between the tiles is 1.
• in other words, if a point p is adjacent to a point q, then every coordinate in ps corresponding coordinate in q differs from it by no more than one. Additionally, at least on coordinate pair differs by exactly one.

Lines:

• Lines are defined by vectors and a tile. A line is each tile hit by the equation: p0 + t<some vector with the same number of coordinates as p0>

Input:

Input will be to STDIN. The first line of input will be two numbers, n and d in the form n,d.

After this will be a line consisting of coordinates specifying the moves that have been done. Coordinates will be listed in the form: 1,1;2,2;3,3. The upper left corner is the origin ( 0,0 for 2D). In the general case, this list will be like 1,2,...,1,4;4,0,...,6,0;... where the first number represents left-right-ness, the second up-down-ness, the third through the 3rd dimension, etc. Note that the first coordinate is Xs first turn, the second is Os first turn, ....

The input will be followed by a newline.

Output:

Output will be to STDOUT. Simply indicate who won if someone won, or if it is a tie. If it is neither a tie nor a win, don't output anything.

Additionally, indicate if there is a move clash, that is, if there are at least two moves in the same location.

If there was a win/draw before the input ended, your program can do whatever it wants.

Test cases (anyone want to suggest any more?):

Input:

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

Example Output:

X wins

Another possible output (requires explanation):

1
• How are you defining the topology of dimensions n>3 for determining what a straight lines along a diagonal is? For example, does any line through any 3 adjacent vertices constitute a win on a 3⁵ board? Are the middle squares of each 3² plane connected to every point of another plane that shares an edge with it on the n-cube? Feb 26 '14 at 4:29
• @Comintern How's that (I probably butchered the explanation. Could definitely be simpler). Feb 26 '14 at 5:43
• Note: the definitions you gave for adjacent tiles are not equivalent (i.e. it is not manhattan distance equals one). Feb 26 '14 at 6:26
• Moreover you should define that it takes n moves on a line to be a winner. (Sorry for not posting these remarks in the sandbox but I didn't even have time to even see it there because it was posted so soon after sandboxing.) Feb 26 '14 at 6:30
• I feel like there should be a very short solution in Prolog... Mar 5 '14 at 4:31

Python, 745 578 Characters

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

I made some changes and shrank it down quite a bit. Note that a return of True means that x has won, False means y won, and , means that an invalid move was made.

• Some things: change import * to import*. Use 1 for True, and 0 for False (remove T and F). return -1 can be return-1 (check out removing spaces). Rename your methods into single char methods. Check out tips for more optimizations. Mar 5 '14 at 4:32
• Oh, thanks, I didn't know you could do some of those things (namely, remove the space between return and -1) Mar 5 '14 at 6:48
• I did a little bit of golfing on your code (that may not all be valid). The result is here: ideone.com/Ld2jAH . Please go through your answer again and shorten the code as much as you can. The tips question for python is very useful Mar 9 '14 at 7:12
• @foota You can do if l<>q: instead of if not l==q:. Apr 13 '15 at 16:41

I was curious to see how many different ways there were to win for a given n,d so I wrote this code to list them all.

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 {
for(int i=0; i<Math.pow(n,d); i++) {
String s = Integer.toString(i,n);
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 {
}
}

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

I hand-tested it on n,d = 2..3,2..3 and it appears to work… after that the number of possible ways to win grows quickly as shown below:

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

Having generated all wining sets, I could extend the program to check the given input against winning sets but, of course, that method would never win the golf. So I was content to stop here - except it looked like I could find a closed-form solution for the number of ways to win as a function of n and d… It is Number of ways to win = 0.5( (n+2)^d - n^d).

C++ 794 849 chars

#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,P,T=1,x={},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;}

Output is: "X" (X wins), "O" (O wins), or "!" (illegal move attempt).

This just maps the points into a linear array and checks all possible subsets of size n, first for being constant at X or O, and then for being in a line. To check for being in a line, the coordinates of the points in each subset are examined one at a time; they must each be either increasing from 0 to n-1, decreasing from n-1 to 0, or constant. The points are naturally ordered in the linear array, so it makes sense to call a coordinate increasing or decreasing for a given set of points.

Thanks to Howard for pointing out a serious mistake in the first version.

In solidarity with Quincunx, I have to point out that it would be a travesty if a C++ answer wins

• I think that while you can say that being in line implies arithmetic progression, it does not hold the other way round (e.g. 0,2,4 won't be a solution for the standard 3,2 tic tac toe). Feb 26 '14 at 10:15
• @Howard, thanks. I've made the corrections. It's too late now for me to finish golfing it, but I was able to fix it (I think). Feb 26 '14 at 12:28
• You can golf it further by using different outputs. You don't have to say exactly X wins or O wins. It is perfectly legitimate to output 1 or 2 (or some other variation) as long as you explain in your answer what they stand for. As I said (emphasis added): "indicate who won". Feb 26 '14 at 16:47
• Done. And if I can learn how the ternary operator works, I can save a few characters. Mar 3 '14 at 8:59
• What about ties? Mar 4 '14 at 13:56