# 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. – Martin Ender Nov 11 '15 at 14:13
• @MartinBüttner Does that mean I will get downvoted, or is it okay to leave my question here? – ghosts_in_the_code Nov 11 '15 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. :) – Martin Ender Nov 11 '15 at 14:27
• Is "optimal play" well defined? If so, can you provide a link describing the algorithm for optimal play? – Rainbolt Nov 11 '15 at 14:28
• @Rainbolt It has been solved and there exist perfect algorithms also. Read Wikipedia for more. – ghosts_in_the_code Nov 11 '15 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. – Dada Oct 19 '16 at 19:56
• This makes my brain hurt. +1! – levelonehuman Oct 19 '16 at 20:01
• @Dada how do you know this answer is down voted? I see 3 as vote... – RosLuP Oct 19 '16 at 21:37
• @RosLuP when I first saw this post, it had 1 downvote. Also, when you have enough rep, you can see how many up and down votes a post has : in that case, now it has 4 up and 1 down. – Dada Oct 20 '16 at 5:07