# Connect4 winner

Problem statement: given a string representing a Connect4 board, with Y meaning a yellow checker, and R meaning a red checker, determine which player, if any, has won the game.

My solution in Ruby generates all possible win position patterns, then compares each player’s positions against the win patterns to see if there are any matches. There are 42 spaces on a Connect4 board, so player boards and win position patterns are represented as a 64-bit integer, and comparisons are made using bitwise and.

I use some Ruby Array#pack/String#unpack hackery to convert an array of 1s and 0s into a 64-bit integer.

As for complexity analysis, once the win patterns have been generated (once, at compile time), and the board has been converted to two 64-bit integers, we have to do 138 comparisons to see which win positions match, and each comparison is just one bitwise and and one integer equality test, so if I add sorting the win patterns by likelihood and short-circuiting logic, this probably approaches the optimal solution.

``````class Connect4Board
def initialize(board_string)
@red    = board_to_int(board_string.chars.map { |char| char == 'R' ? 1 : 0 })
@yellow = board_to_int(board_string.chars.map { |char| char == 'Y' ? 1 : 0 })
end

def winner
if is_winner?(@red)
return "red"
elsif is_winner?(@yellow)
return "yellow"
else
return "none"
end
end

def is_winner?(board)
matching_patterns(board).any?
end

def matching_patterns(board)
PATTERNS.select { |pattern| pattern & board == pattern }
end

def board_to_int(board)
self.class.board_to_int(board)
end

# Pack a 42-element array of 1s and 0s into a 64-bit integer
def self.board_to_int(board)
padded_board = Array.new(64-board.length, 0) + board
end

class Patterns
class << self
BOARD_HEIGHT = 6 # A Connect 4 board is 6 spaces high
BOARD_WIDTH  = 7 # by 7 spaces across
PATTERN_SIZE = 4 # where a win consists of 4 in a row

# ****  Patterns 4 across: height 1, width 4.
#       24 total patterns.
def horiz_patterns
gen_patterns(1, PATTERN_SIZE)
end

# *     Patterns 4 down: height 4, width 1.
# *     21 total patterns.
# *
# *
def vert_patterns
gen_patterns(PATTERN_SIZE, 1)
end

# *     Diagonal patterns from upper left to lower right
#  *    making an obtuse angle with the X-axis.
#   *   Column index _increases_ with row index.
#    *  This is a :forward pattern.
#       12 total patterns.
def obtuse_patterns
gen_patterns(PATTERN_SIZE, PATTERN_SIZE, :forward)
end

#    *  Diagonal patterns from upper right to lower left
#   *   make an acute angle with the X-axis.
#  *    Column index _decreases_ with row index
# *     This is a :reverse pattern.
#       12 total patterns
def acute_patterns
gen_patterns(PATTERN_SIZE, PATTERN_SIZE, :reverse)
end

# 24 + 21 + 12 + 12 = 69 total patterns
def all_patterns
horiz_patterns + vert_patterns + obtuse_patterns + acute_patterns
end

def gen_patterns(pattern_height, pattern_width, direction = :forward)
patterns = []
0.upto(BOARD_HEIGHT - pattern_height) do |start_row|
0.upto(BOARD_WIDTH - pattern_width) do |start_col|
rows = indices(start_row, pattern_height, :forward)
cols = indices(start_col, pattern_width, direction)
board = blank_board
rows.zip(cols) { |row, col| board[row][col] = 1 }
patterns << Connect4Board.board_to_int(board.flatten)
end
end
patterns
end

# Generate row or column indices for a pattern, starting at basis.
# When amplitude is 1, generates 4 of the same: e.g. [0,0,0,0].
# When amplitude is 4, generates an increasing or decreasing
# pattern, depending on direction: e.g. [2,3,4,5] or [3,2,1,0]
def indices(basis, amplitude, direction)
indices = case amplitude
when 1
Array.new(PATTERN_SIZE, basis)
when PATTERN_SIZE
(basis...basis + PATTERN_SIZE).to_a
end
direction == :reverse ? indices.reverse : indices
end

def blank_board
Array.new(6) { Array.new(7,0) }
end
end
end
PATTERNS = Patterns.all_patterns
end

describe Connect4Board do
describe "#winner" do
it "works for horizontal wins" do
Connect4Board.new(
'_______'
'____R__'
'___RY__'
'__YYR__'
'_RYYYY_'
'_RRRYR_'
).winner.should == "yellow"
end

it "works for vertical wins" do
Connect4Board.new(
'_______'
'____R__'
'___RR__'
'__YYR__'
'_RYYRY_'
'_YYRYR_'
).winner.should == "red"
end

it "works for acute diagonal wins" do
Connect4Board.new(
'_______'
'____R__'
'___RR__'
'__RYY__'
'_RYYRY_'
'_YYRYR_'
).winner.should == "red"
end

it "works for obtuse diagonal wins" do
Connect4Board.new(
'_______'
'__Y_R__'
'__RYR__'
'__RYY__'
'_RYYRY_'
'_YYRYR_'
).winner.should == "yellow"
end
end
end

``````