19
\$\begingroup\$

Write a program to play the game of Connect 4. You are given the state of the board as input and you must decide which column to place your piece in to either get 4 in a row (horizontally, vertically, or diagonally) or block your opponent from doing the same.

The board is a 6x7 array, where each cell may be empty (' '), contain your piece ('X') or your opponent's piece ('O'). An example board:

O      
XX    X
XOX  OO
XOO OXO
OXXOXXO
XOXOXOX

You would want to play in column 3 (columns are 0-6, numbered from the left) for the diagonal win. So you output:

3

Your code must output a column number, and it must satisfy the following criteria:

  1. You cannot play in a column that already has 6 pieces in it.
  2. If there is at least one winning move, you must play one of them.
  3. If you can prevent your opponent from winning on his next move, you must do so.

Note that optimal play is not necessary, only that you take an immediate win or prevent your opponent's immediate win. If your opponent has more than one way to win, you need not block any of them.

You are given the board on standard input and must print a column number in which you want to play on standard output. The board is guaranteed to be well-formed (no holes, at least one possible move) and to not already have a win for either player.

Shortest code wins.

Example 1

      X
      O
      X
      O
 OOO  X
 XXX  O

You must play either column 0 or 4 for the win.

Example 2

      X
X     X
O     O
XOX  XO
XXO XOX
XXO XXO

You must play column 3 to block your opponent's immediate win.

Example 3

X      
XO     
OX    O
XO   XX
XXO OOO
OOO XXO

You cannot win or stop your opponent from winning, so you may play any column 1-6 (0 is full).

Example 4

X      
O      
X      
OOO    
XOX    
OXOX   

You cannot play in column 3, as it lets your opponent win immediately. You may play in columns 1-2 or 4-6.

\$\endgroup\$
9
\$\begingroup\$

C, 234 286 256 chars

Fixed to correctly solve the problem, by checking for opponent winning moves following every move attempted.

This code is very sensitive to the input file format - each line must conatain 7 chars + newline.
The board is treated as an 8x8 matrix, rather than 7x6. The 8th column contains the newlines, and the 2 extra rows contain zeros, so they don't interfere with the solution. They actually help - When moving right from the rightmost column, you hit to newline column, which serves as a boundary check.

w checks one position for an opportunity to win or block. q should be the cell to check around. It uses reursion to loop through 4 directions (starts with 9,8,7, then several times 1).
C checks for a sequence of identical characters starting at q in direction d, both back and forth. It returns the sum of both sequences (not counting the starting position), so if it returns 3, there's a row of 4.

char B[99],q;
C(i,d){
    return B[d*i+++q]-B[q]?d>0?C(1,-d):0:1+C(i,d);
}
w(x){
    return x&&C(1,x>6?x:1)>2|w(x-1);
}
t(l,c,r,v){
    for(;c--;)B[q=c]&32&B[c+8]-32?r=w(9,B[c]=l)?v=c:v||r*t(79,l,0,1)?r:c,B[c]=32:0;
    return r;
}
main(){
    putchar(48+t(88,16+read(0,B+16,48),0,0)%8);
}
\$\endgroup\$
5
\$\begingroup\$

Python 2.x - 594 591 576 557 523 459 458 433 bytes

This is the best I've achieved so far. I guess it's hard to beat C. Awesome challenge, I have to say.

r=range
f=[]
exec'f+=list(raw_input());'*6
def n(p):
 o,b,a,k=[],1,'O',lambda q:any([o[i:i+4]==list(q)*4for o in(f[x-x%7:],f[x%7::7])for i in r(3)]+[all(q==f[7*(y+u*i)+z+i]for i in r(4))for u,z,v,c in((1,0,3,4),(-1,3,6,3))for y in r(z,v)for z in r(c)])
 for x in r(42):
    if x>34<a>f[x]or x<35and f[x+7]>'0'>f[x]:f[x]=p;z=k(p)*b;o=z*[x]+o+[x]*(a==p or n(a)[1]);b-=z;f[x]=' '
 return o[0]%7,b
a,b,c,d=n('X')+n('O')
print(a,(c,a)[d])[b]

The if-line (line 7) has indentation of one tab. SE doesn't like tabs.

\$\endgroup\$
  • 2
    \$\begingroup\$ I spend way too much time refining these. Also, the 458 byte version didn't work correctly for example #4. Take 25 bytes away and it does. Magic. \$\endgroup\$ – seequ Jun 5 '14 at 6:26

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.