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
    [padded_board.join("")].pack("B64").unpack("Q").first
  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