22
\$\begingroup\$

Introduction

Connect Four is a game where you attempt to get four in a row: horizontally, vertically, or diagonally. In this code golf, we will be trying to find who won, given a game board. There will always be one winner, and only one winner.


Task

Given a Connect Four board, figure out who the winner is: X or Y. There will always be one winner, and only one winner. The board size will always be 6 by 7 like how the game board is in the in picture.

Given a board the following board, in this instance, X is red and Y is blue:

enter image description here

Your input would be:

OOOOOOO
OOOOOOO
OOOOOOO
OOOOXOO
OOOXXOO
OOXYYYY

You can separate rows of the game by newline character (like above), no dividing character, divide the rows into an array or list, or you can input a matrix of characters.

Correct output for this example:

Y

Y has four in a row; so, Y is the winner. So, we output Y.


Test cases

Input:

OOOOOOO
OOOOOOO
OOOOOOO
OOOOOOO
OOYYOOO
OYXXXXO

Output:

X

Input:

OOOOOOO
OOOOOOO
OOOOOOO
XXXXOOO
YXYYOOO
YXYYXYX

Output:

X

Input:

YXYYXOO
XYXXYOO
XXXYYOO
YYYXXOO
XXYYYYO
XXYYXXO

Output:

Y

Input:

OOOOOOO
OOOOOOO
OYOOOOO
OOYOOOO
OOOYOOO
OOOOYOO

Output:

Y

Input:

OOOOOOO
OOOOOOO
OYOOOOX
OOYOOOX
OOOXOOX
OXOXYOX

Output:

X

Scoring

Least number of bytes wins!

\$\endgroup\$
9
  • \$\begingroup\$ This is the perfect challenge for PMA/Snails codegolf.stackexchange.com/questions/47311/… \$\endgroup\$ Apr 21, 2017 at 1:21
  • 3
    \$\begingroup\$ Can we assume that the winner will always have one more token than the loser? \$\endgroup\$ Apr 21, 2017 at 2:38
  • 1
    \$\begingroup\$ @mathjunkie I was wrong, you can't assume that. \$\endgroup\$
    – Neil
    Apr 21, 2017 at 2:44
  • 3
    \$\begingroup\$ @nfnneil does the output have to be X or Y or can we choose two other consistent outputs to indicate the winner? \$\endgroup\$ Apr 21, 2017 at 5:51
  • 2
    \$\begingroup\$ Can we choose to use other characters as input? Or to input a numeric matrix? \$\endgroup\$
    – Luis Mendo
    Apr 21, 2017 at 7:42

17 Answers 17

7
\$\begingroup\$

Retina, 51 48 bytes

Thanks to Martin Ender for saving 3 bytes

M`X((.{6}X){3}|(.{8}X){3}|(.{7}X){3}|XXX)
T`d`YX

Try it Online!

Takes input as a comma-separated list of rows

\$\endgroup\$
3
  • \$\begingroup\$ You can save a few bytes by using a match stage and shortening (.{7}X){3}|XXX to (.{7}X|X)\4\4: tio.run/nexus/retina#fc4xCsMwDAXQPfcI2GC6NDS5QaeipcP/… \$\endgroup\$ Apr 21, 2017 at 5:57
  • 1
    \$\begingroup\$ @MartinEnder I don't see how you can use \4 - you want to repeat the effect of the .{7}, not the matched string. (And balancing groups would probably be far too long.) \$\endgroup\$
    – Neil
    Apr 21, 2017 at 7:59
  • 1
    \$\begingroup\$ @Neil oh yeah, nevermind, somehow I didn't consider that there are other OXY cells than the match in the grid. using the match stage still saves 3 bytes then. \$\endgroup\$ Apr 21, 2017 at 8:00
6
\$\begingroup\$

Javascript (ES6), 54 55

Edit 1 byte saved thanks @Arnauld

I just check if X is the winner, as There will always be one winner, and only one winner

Input is a string with any separator, like in @Arnauld's answer

F=    
b=>'YX'[+[0,6,7,8].some(x=>b.match(`X(.{${x}}X){3}`))]

;['OOOOOOO OOOOOOO OOXOOOO OOXOOOO OOXOOOO OOXOYYY'
 ,'OOOOOOO OOOOOOO OOXOOOO OOYXOOO OOYOXOO OOYYOXY'
 ,'OOOOOOO,OOOOOOO,OOOOOOO,OOOOOOO,OOYYOOO,OYXXXXO'
 ,'OOOOOOO,OOOOOOO,OOOOOOO,XXXXOOO,YXYYOOO,YXYYXYX'
 ,'YXYYXOO,XYXXYOO,XXXYYOO,YYYXXOO,XXYYYYO,XXYYXXO']
.forEach(s => console.log(s,F(s)))

\$\endgroup\$
0
5
\$\begingroup\$

JavaScript (ES6), 77 76 69 bytes

Saved 7 bytes thanks to Neil

Takes input as a something-separated string, where something is basically any character.

b=>[...'XXXXYYYY'].find((c,i)=>b.match(`(${c}.{${(i%4+6)%9}}){3}`+c))

Test cases

let f =

b=>[...'XXXXYYYY'].find((c,i)=>b.match(`(${c}.{${(i%4+6)%9}}){3}`+c))

console.log(f("OOOOOOO,OOOOOOO,OOOOOOO,OOOOOOO,OOYYOOO,OYXXXXO"))
console.log(f("OOOOOOO,OOOOOOO,OOOOOOO,XXXXOOO,YXYYOOO,YXYYXYX"))
console.log(f("YXYYXOO,XYXXYOO,XXXYYOO,YYYXXOO,XXYYYYO,XXYYXXO"))

\$\endgroup\$
2
  • \$\begingroup\$ Why not use b.match()? Should save on the RegExp call. \$\endgroup\$
    – Neil
    Apr 21, 2017 at 8:04
  • \$\begingroup\$ @Neil I totally forgot that match() was doing an implicit conversion to RegExp. Thanks! \$\endgroup\$
    – Arnauld
    Apr 21, 2017 at 8:22
4
\$\begingroup\$

Jelly, 25 22 bytes

ŒgL⁼¥Ðf
;UŒD€;Z;$ç€4FṀ

Takes a list of strings (or list of list of characters) formed of X, Y, and O (would also work with replacements such that the space has a lower ordinal than both counters).

Try it online! or run an augmented version that takes a multiline string.

How?

ŒgL⁼¥Ðf - Link 1, runs of given length: list A, length B  e.g. "XYYYXXO", 4
Œg      - group runs of equal elements of A                     ["X","YYY","XX","O"]
     Ðf - filter keep:
    ¥   -     last two links as a dyad:
  L     -         length                                         1   3     2    1
   ⁼    -         equal to B?         (none kept in this case->) 0   0     0    0

;UŒD€;Z;$ç€4FṀ - Main link: list of list of chars (or list of stings) I
 U             - reverse each row of I
;              - I concatenated with that
  ŒD€          - positive diagonals of €ach (positive and negative diagonals)
        $      - last two links as a monad:
      Z        -     transpose of I (i.e. the columns)
       ;       -     concatenated with I (columns + rows)
     ;         - concatenate (all the required directional slices)
         ç€4   - call the last link (1) as a dyad for €ach with right argument = 4
            F  - flatten the result
             Ṁ - take the maximum ('Y'>'X'>'O') - this has the bonus effect of returning:
                               'Y' or 'X' for a winning board; and
                               'O' or '' for a (valid) game in progress.
\$\endgroup\$
3
\$\begingroup\$

Python 2, 143 bytes

m=input()
u=[r[::-1]for r in m]
print"YX"[any(any('X'*4in''.join(t[i][j-i]for i in range(j+1))for j in range(6))for t in(m[::-1],m,u,u[::-1]))]

Takes a list of strings or a list of list of chars. Hard-coded for 6 rows by 7 columns, as the specification guarantees.

Try it online!

\$\endgroup\$
3
\$\begingroup\$

K (ngn/k), 45 bytes

{"YX"@|//{&/'(x;+x),x@'/:|:\!4}''+'4'4''~2!x}

Try it online!

Takes a matrix of characters and returns one of X or Y. If simplified I/O is allowed (0, 1, 2 for X, O, Y for input and boolean for output), I can remove 2! from preprocessing and "YX"@ from postprocessing, giving 38 bytes.

How it works

{"YX"@|//{&/'(x;+x),x@'/:|:\!4}''+'4'4''~2!x}   x: matrix of chars
~2!x       for each char, convert X to 1 and O/Y to 0
+'4'4''    extract all 4x4 sub-matrices using size-4 windows
{...}''    for each submatrix...
|:\!4        (0 1 2 3;3 2 1 0)
x@'/:        for each row of above, extract one element from each row of x
             which gives the diagonal and the antidiagonal of x
(x;+x),      prepend x and transpose of x
&/'          reduce each by boolean AND
             x -> vertical test, +x -> horizontal test
|//        repeat reducing by boolean OR until only one value remains
"YX"@      convert 1 to X and 0 to Y
\$\endgroup\$
1
  • \$\begingroup\$ -3: trainify by removing { x} \$\endgroup\$
    – ngn
    Aug 3, 2021 at 16:51
2
\$\begingroup\$

Jelly, 19 bytes

UŒD;ŒD;Z;ṡ€4;/ṢEÞṪṪ

Try it online!

The core of this answer is copied from my answer to this very similar question.

Explanation

UŒD;ŒD;Z;ṡ€4;/ṢEÞṪṪ
   ;  ; ;             Append {the input} and the following three values:
UŒD                     the antidiagonals of {the input};
    ŒD                  the diagonals of {the input};
       Z                the transposed {input}.
         ṡ 4          Find all length-4 substrings
          €             of each subarray within that.
            ;/        Flatten one level.
                Þ     Sort, with the following sort order:
               E        If all elements are the same, sort later.
              Ṣ         Tiebreak via lexicographical order.
                 ṪṪ   Take the last element of the last element.

Fairly simple: we take all rows, columns, diagonals, and antidiagonals (just as in the n-queens validator), then take all length-4 substrings of those, then sort them in such a way that the winning line of 4 sorts to the end. (We need the tiebreak in case there's an OOOO in addition to the XXXX or YYYY.) Take the last element of the last element, and that'll be X or Y as required.

\$\endgroup\$
2
\$\begingroup\$

PHP, 71 Bytes

echo preg_match('#X(XXX|(.{8}X){3}|(.{7}X){3}|(.{9}X){3})#',$argn)?X:Y;

Online Version

\$\endgroup\$
2
\$\begingroup\$

Python 2, 201 143 129 128 107 Bytes

I decided to add horizontal, vertical, and diagonal together into one list and then add increment then look for X for times in it. And since there will always be a winner, I can assume Y won if X doesn't. This codes takes a matrix of all the different pieces and empty places.

lambda m:"YX"[any("X"*4in"".join(a)for a in zip(*m)+m+zip(*["0"*(7-i)+m[i]+"00"*i+m[i]for i in range(6)]))]

Try it online!

Credits

\$\endgroup\$
13
  • \$\begingroup\$ It's perfectly acceptable to self-answer. \$\endgroup\$ Apr 21, 2017 at 2:56
  • \$\begingroup\$ Without looking too much at it, there seems to be useless whitespaces at: i:] for, i, r, r] for and 1 for. \$\endgroup\$
    – Yytsi
    Apr 21, 2017 at 4:48
  • \$\begingroup\$ @TuukkaX Thanks for the input, updated. \$\endgroup\$
    – Neil
    Apr 21, 2017 at 4:50
  • \$\begingroup\$ Also, *(len(m)-1) could be *~-len(m). How it works. \$\endgroup\$
    – Yytsi
    Apr 21, 2017 at 4:54
  • \$\begingroup\$ The ] for and 1 for are still there. \$\endgroup\$
    – Yytsi
    Apr 21, 2017 at 5:02
2
\$\begingroup\$

PowerShell, 66 65 58 54 bytes

I just check if X is the winner, as There will always be one winner, and only one winner. Thanks to edc65.

Input is a string with no dividing character. Thanks to Arnauld.

param($b)'YX'[1-in(0,5,6,7|%{$b-match"X(.{$_}X){3}"})]

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 3, 105 90 81 80 bytes

Regex based. Lines are space separated. Saved 9 bytes thanks to @Lynn.

Saved 1 byte by utilizing the fact that there is a guaranteed match. So if there's no win for X then there must be a win for Y.

lambda x:re.findall('X(XXX'+'|(.{%d}X){3}'*3%(6,7,8)+')',x)and'X'or'Y'
import re

Try it online!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I think you can do something like: lambda x:re.findall('(X|Y)(z'+'|(.{%d}\\1){3}'*4%(0,6,7,8)+')',x)[0][0] \$\endgroup\$
    – Lynn
    Mar 3, 2020 at 1:31
  • \$\begingroup\$ @Lynn Good catch! Thanks. Saved 9 bytes. \$\endgroup\$
    – mypetlion
    Mar 3, 2020 at 17:54
1
\$\begingroup\$

Zsh, 207 ... 158 bytes

Version history: 4 iterations for ~25 bytes first week; then 3 more iterations for ~25 bytes 6 months later, 1 more for 1 byte 11 months later.

t(){a=($^a-$^@_);for s l (${w:^^argv}){s+=$l;i=;repeat $#s a[++i]+=$s[i+1];}}
w=(+)
t $@
for s;w[++j]=${(l:j:)}_
t $@
t ${(Oa)@}
[[ $a = *XXXX* ]]&&<<<X||<<<Y

(first) (second) (third) (fourth) (fifth) (sixth) (seventh) (eigth)

In the footer, I print both the input board and the array we build from it to stderr. Scroll down to debug to see them. The array we build is a lot longer now, since t does a cartesian product with input board on every call. (Hey, it shortened the code by a few bytes.)

There's a lot to cover here, so I moved the (sixth edition) comments to an annotated gist.

(tl;dr: concatenate transpositions of the original array, but make sure to keep them separated)

\$\endgroup\$
1
\$\begingroup\$

Ruby, 84 bytes

Takes the board as a single continuous string with no separators. Finds a non-O character that's in a connect-4 and returns it.

->b{b[(0..41).find{|i|b[i]!=?O&&[1,6,7,8].any?{|j|(1..3).all?{|n|b[i+j*n]==b[i]}}}]}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 58 55 56 bytes

{"XY"@|/&/'88<x ./:/:,/{x+/:/:+3+[4#1-+!3 3;]\&4}'+!6 7}

Try it online!

{ } function with argument x

+!6 7 all possible pairs of 0..5 and 0..6

{ }' for each of them do

4#1-+!3 3 are 4 of the 8 ortho-diagonal directions: (1 1;1 0;1 -1;0 1)

3+[ ]\&4 start with a list of four zeroes (&4) and make 3 steps in each of the directions

x+/:/: start from each possible position and take the steps in each possible direction

,/ concatenate. at this point we have a matrix of 4-lists of coordinate pairs, some of them extending beyond the board

x ./:/: look up the corresponding cells from x

88< which of them are "Y"-s? (88 is the ascii code of "X")

&/' which 4-lists consist only of "Y"-s? (and-reduce-each)

|/ is there at least one such? (or-reduce)

"XY"@ if false return "X", if true return "Y"

\$\endgroup\$
1
\$\begingroup\$

J, 42 bytes

1 e.[:,4 4(*/"1@,|:,,{~3 0+3 5*/i.@4);._3]

Try it online!

Takes input as a matrix of integers where 0 is blank, 1 is X, and 2 is Y. Returns 1 if X wins, 0 if Y wins.

\$\endgroup\$
1
\$\begingroup\$

05AB1E (legacy), 29 26 25 bytes

í‚εεÐм«NFÁ]€ø`IIø)J»γ4ùSà

Input as a character-matrix.

Uses the legacy version for -1 byte, since min/max also works on characters. In the new version of 05AB1E, the trailing à (maximum) should have been instead (sort, keep last item).

Try it online or verify all test cases.

Explanation:

í                 # Reverse each row of the (implicit) input-list
 ‚                # Pair it with the (implicit) input-list
  ε               # Map over both matrices:
   ε              #  Map over each row:
    Ð             #   Triplicate the current row
     м            #   Remove all these characters, leaving a list of empty strings of the
                  #   same size as the row
      «           #   Merge this list of empty strings to the row
       NF         #   Loop the (0-based) row-index amount of times:
         Á        #    And rotate the row with appended empty strings towards the right
  ]               # Close the nested maps and inner loop
   €              # For both mapped matrices:
    ø             #  Zip/transpose; swapping rows/columns
                  # (we now have a list of all diagonals and anti-diagonals)
     `            # Push both lists of lists separated to the stack
      I           # Push the input again
       Iø         # And push the input, zipped/transposed
         )        # Wrap everyone on the stack into a list
                  # (we now have a list of all diagonals, anti-diagonals, rows, and columns)
          J       # Join each inner-most list of characters together to a string
           »      # Join each inner list together to a string; and then join these strings
                  # with newline delimiter
            γ     # Split everything into parts with equal adjacent characters
             4ù   # Only keep the parts of length 4
               S  # Flatten it to a list of characters
                à # And get the maximum character of this list
                  # (after which it is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

Python 3.8 (pre-release), 114 112 bytes

Using a bitboard approach to check for 4 in a row.
Input: a 2D list of integers, where 0 represents empty cell, 1 is X, and 2 is Y.
Output: a positive integer if X wins, or 0 if Y wins.

lambda L:(b:=sum(sum(zip(*(L+[[0]*7])),())[i]%2<<i for i in range(49)))*any((r:=b&b<<i)&r<<i*2for i in(1,6,7,8))

Try it online!

Explanation

The bitboard's layout is as follow (the missing positions in the last row is padded with 0):

0  8 16 24 32 40 48
1  9 17 25 33 41 49
2 10 18 26 34 42 50
3 11 19 27 35 43 51
4 12 20 28 36 44 52
5 13 21 29 37 45 53
6 14 22 30 38 46 54

This is the core of the function: given the bitboard b representing X's occupancies, check if X is winning:

any(
    # shift the board by i, 2i, 3i, 4i and and all of them together
    # if there's a set bit in the result (aka result != 0), then there is a 4-in-a-row
    (r:=b&b<<i)&r<<i*2 
    # do this for all 4 directions
    # 1: vertical, 7: horizontal, 6 and 8: diagonal
    for i in(1,6,7,8)
)

This part contructs the bitboard b for X:

b:=sum(
    sum(zip(*
        (L+[[0]*7]) # append a row of 0 at the bottom of L
    ),())           # flatten L into a list, with the index correspond
                    #   to the correct position in the bitboard layout
    [i]%2<<i        # set the ith bit to 1 if the new list has X (=1) at that index      
    for i in range(49)
) # sum all the set bits together to create the bitboard
\$\endgroup\$

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.