13
\$\begingroup\$

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.

Adjacent:

  • 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
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Comintern Feb 26 '14 at 4:29
  • 1
    \$\begingroup\$ @Comintern How's that (I probably butchered the explanation. Could definitely be simpler). \$\endgroup\$ – Justin Feb 26 '14 at 5:43
  • \$\begingroup\$ Note: the definitions you gave for adjacent tiles are not equivalent (i.e. it is not manhattan distance equals one). \$\endgroup\$ – Howard Feb 26 '14 at 6:26
  • \$\begingroup\$ 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.) \$\endgroup\$ – Howard Feb 26 '14 at 6:30
  • 1
    \$\begingroup\$ I feel like there should be a very short solution in Prolog... \$\endgroup\$ – Nate Eldredge Mar 5 '14 at 4:31
3
+100
\$\begingroup\$

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

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Justin Mar 5 '14 at 4:32
  • \$\begingroup\$ Oh, thanks, I didn't know you could do some of those things (namely, remove the space between return and -1) \$\endgroup\$ – foota Mar 5 '14 at 6:48
  • \$\begingroup\$ 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 \$\endgroup\$ – Justin Mar 9 '14 at 7:12
  • \$\begingroup\$ @foota You can do if l<>q: instead of if not l==q:. \$\endgroup\$ – mbomb007 Apr 13 '15 at 16:41
3
\$\begingroup\$

Not an answer - Java

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

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

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Howard Feb 26 '14 at 10:15
  • \$\begingroup\$ @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). \$\endgroup\$ – Eric Tressler Feb 26 '14 at 12:28
  • \$\begingroup\$ 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". \$\endgroup\$ – Justin Feb 26 '14 at 16:47
  • \$\begingroup\$ Done. And if I can learn how the ternary operator works, I can save a few characters. \$\endgroup\$ – Eric Tressler Mar 3 '14 at 8:59
  • \$\begingroup\$ What about ties? \$\endgroup\$ – Justin Mar 4 '14 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.