# Determine winner of Connect 4

You are given a partially filled Connect 4 grid (7x6).

O X
O X
X O X O     O
X O X O   X X
O X X X O O X
O O O X X O X

(Input can be given as a 1D or 2D array and as letters or numbers, etc.)

Assume that

• X started the game.
• Nobody has won yet.
• Players may not have played well until now, but now onwards they will both employ optimal strategies.
• Input grid is not faulty.

You must output a single value that indicates which player wins (or a draw)

Code golf challenge; so shortest code wins. Your program does not have to actual compute the output in reasonable amount of time, but you should be able to prove that the output will be obtained correctly in a finite amount of time.

• Related. Nov 11, 2015 at 14:13
• @MartinBüttner Does that mean I will get downvoted, or is it okay to leave my question here? Nov 11, 2015 at 14:25
• It just means the questions are related, nothing more, nothing less. The purpose of posting the link is for the challenges to appear in each other's "Linked" sidebar, so people can find related challenges more easily. If I considered your question a duplicate, I would have said so (or just closed it), so don't worry. :) Nov 11, 2015 at 14:27
• Is "optimal play" well defined? If so, can you provide a link describing the algorithm for optimal play? Nov 11, 2015 at 14:28
• @Rainbolt It has been solved and there exist perfect algorithms also. Read Wikipedia for more. Nov 11, 2015 at 14:34

# Perl, 119118 117 bytes

Includes +4 for -0p

Give rotated board padded with spaces on STDIN (gravity pulls stones to the right)

connect4.pl
OXXX
XOO
OX
OOXX
XXXO
XXOOXO
OOXXOO
^D

connect4.pl:

#!/usr/bin/perl -p0
y/XO/OX/if$^S|y/X//>y/O//;$_=$$_||=/Z@{[map"|O".".{_}O"x3,0,5..7]}/sx||s% (?! )%_="`X'";do0%eg?/1/?3:1+/2/:2 Prints 3 if player to move wins, 1 if player to move loses and 2 for a draw. On older perls you can use a literal ^S to gain one byte. If you don't mind extreme inefficiency you can leave out the$$_||= (transposition table) and gain 6 more bytes. If you leave out the \$_= it will show you where to play instead of the result (play on 1 and win if there is one, play on 2 and draw if there is one or play on any 3 and lose)

Builds and evaluates a complete minimax tree. You will run out of memory and time unless the board is already reasonably well filled.

• Why on earth did someone downvote? The golfing is truly amazing (I golf with perl and obtaining such a solution is extremly hard - I'm not sure any other perl golfer I know could have come up with that code). And the code has the required behavior.