Avatar of paulfioravanti

paulfioravanti's solution

to Connect in the Ruby Track

Published at Jun 02 2019 · 0 comments
Instructions
Test suite
Solution

Compute the result for a game of Hex / Polygon.

The abstract boardgame known as Hex / Polygon / CON-TAC-TIX is quite simple in rules, though complex in practice. Two players place stones on a rhombus with hexagonal fields. The player to connect his/her stones to the opposite side first wins. The four sides of the rhombus are divided between the two players (i.e. one player gets assigned a side and the side directly opposite it and the other player gets assigned the two other sides).

Your goal is to build a program that given a simple representation of a board computes the winner (or lack thereof). Note that all games need not be "fair". (For example, players may have mismatched piece counts.)

The boards look like this (with spaces added for readability, which won't be in the representation passed to your code):

. O . X .
 . X X O .
  O O O X .
   . X O X O
    X O O O X

"Player O" plays from top to bottom, "Player X" plays from left to right. In the above example O has made a connection from left to right but nobody has won since O didn't connect top and bottom.


For installation and learning resources, refer to the Ruby resources page.

For running the tests provided, you will need the Minitest gem. Open a terminal window and run the following command to install minitest:

gem install minitest

If you would like color output, you can require 'minitest/pride' in the test file, or note the alternative instruction, below, for running the test file.

Run the tests from the exercise directory using the following command:

ruby connect_test.rb

To include color from the command line:

ruby -r minitest/pride connect_test.rb

Submitting Incomplete Solutions

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

connect_test.rb

require 'minitest/autorun'
require_relative 'connect'

# Common test data version: 1.1.0 a02d64d
class ConnectTest < Minitest::Test
  def test_an_empty_board_has_no_winner
    # skip
    board = [
      '. . . . .',
      ' . . . . .',
      '  . . . . .',
      '   . . . . .',
      '    . . . . .'
    ].map {|row| row.gsub(/^ */, '')}
    game = Board.new(board)
    assert_equal '', game.winner, 'an empty board has no winner'
  end

  def test_x_can_win_on_a_1x1_board
    skip
    board = [
      'X'
    ].map {|row| row.gsub(/^ */, '')}
    game = Board.new(board)
    assert_equal 'X', game.winner, 'X can win on a 1x1 board'
  end

  def test_o_can_win_on_a_1x1_board
    skip
    board = [
      'O'
    ].map {|row| row.gsub(/^ */, '')}
    game = Board.new(board)
    assert_equal 'O', game.winner, 'O can win on a 1x1 board'
  end

  def test_only_edges_does_not_make_a_winner
    skip
    board = [
      'O O O X',
      ' X . . X',
      '  X . . X',
      '   X O O O'
    ].map {|row| row.gsub(/^ */, '')}
    game = Board.new(board)
    assert_equal '', game.winner, 'only edges does not make a winner'
  end

  def test_illegal_diagonal_does_not_make_a_winner
    skip
    board = [
      'X O . .',
      ' O X X X',
      '  O X O .',
      '   . O X .',
      '    X X O O'
    ].map {|row| row.gsub(/^ */, '')}
    game = Board.new(board)
    assert_equal '', game.winner, 'illegal diagonal does not make a winner'
  end

  def test_nobody_wins_crossing_adjacent_angles
    skip
    board = [
      'X . . .',
      ' . X O .',
      '  O . X O',
      '   . O . X',
      '    . . O .'
    ].map {|row| row.gsub(/^ */, '')}
    game = Board.new(board)
    assert_equal '', game.winner, 'nobody wins crossing adjacent angles'
  end

  def test_x_wins_crossing_from_left_to_right
    skip
    board = [
      '. O . .',
      ' O X X X',
      '  O X O .',
      '   X X O X',
      '    . O X .'
    ].map {|row| row.gsub(/^ */, '')}
    game = Board.new(board)
    assert_equal 'X', game.winner, 'X wins crossing from left to right'
  end

  def test_o_wins_crossing_from_top_to_bottom
    skip
    board = [
      '. O . .',
      ' O X X X',
      '  O O O .',
      '   X X O X',
      '    . O X .'
    ].map {|row| row.gsub(/^ */, '')}
    game = Board.new(board)
    assert_equal 'O', game.winner, 'O wins crossing from top to bottom'
  end

  def test_x_wins_using_a_convoluted_path
    skip
    board = [
      '. X X . .',
      ' X . X . X',
      '  . X . X .',
      '   . X X . .',
      '    O O O O O'
    ].map {|row| row.gsub(/^ */, '')}
    game = Board.new(board)
    assert_equal 'X', game.winner, 'X wins using a convoluted path'
  end

  def test_x_wins_using_a_spiral_path
    skip
    board = [
      'O X X X X X X X X',
      ' O X O O O O O O O',
      '  O X O X X X X X O',
      '   O X O X O O O X O',
      '    O X O X X X O X O',
      '     O X O O O X O X O',
      '      O X X X X X O X O',
      '       O O O O O O O X O',
      '        X X X X X X X X O'
    ].map {|row| row.gsub(/^ */, '')}
    game = Board.new(board)
    assert_equal 'X', game.winner, 'X wins using a spiral path'
  end
end
# frozen_string_literal: true

class Board
  module ChildCoordinates
    ADJACENT_COORDINATES = lambda do |(y_index, x_index)|
      [x_index - 1, x_index + 1, y_index - 1, y_index + 1]
    end
    private_constant :ADJACENT_COORDINATES

    module_function

    def generate(board, piece, y_index, x_index)
      adjacent_coordinates(board, piece, y_index, x_index)
        .to_enum
        .with_object([board, piece])
        .each_with_object([], &method(:add_valid_child))
    end

    def adjacent_coordinates(board, piece, y_index, x_index)
      coordinates =
        [y_index, x_index]
        .then(&ADJACENT_COORDINATES)
        .freeze
      center_coordinates(y_index, coordinates).tap do |coord_list|
        add_above_coordinates(board, x_index, piece, coordinates, coord_list)
        add_below_coordinates(board, x_index, piece, coordinates, coord_list)
      end
    end
    private_class_method :adjacent_coordinates

    def add_valid_child((coordinate, (board, piece)), acc)
      if coordinate.all?(&method(:non_negative?)) &&
         expected_piece?(board, coordinate, piece)
        acc << coordinate
      end
    end
    private_class_method :add_valid_child

    def non_negative?(number)
      !number.negative?
    end
    private_class_method :non_negative?

    def expected_piece?(board, coordinate, piece)
      y, x = coordinate
      board[y][x] == piece
    end
    private_class_method :expected_piece?

    def center_coordinates(y_index, coordinates)
      left, right, _above, _below = coordinates
      [[y_index, left], [y_index, right]]
    end
    private_class_method :center_coordinates

    def add_above_coordinates(board, x_index, piece, coordinates, coord_list)
      left, right, above, _below = coordinates
      return unless board[above]

      coord_list.push(
        [above, x_index],
        piece == X ? [above, right] : [above, left]
      )
    end
    private_class_method :add_above_coordinates

    def add_below_coordinates(board, x_index, piece, coordinates, coord_list)
      left, right, _above, below = coordinates
      return unless board[below]

      coord_list.push(
        [below, x_index],
        piece == X ? [below, left] : [below, right]
      )
    end
    private_class_method :add_below_coordinates
  end
  private_constant :ChildCoordinates

  INITIAL_COLUMN_INDEX = 0
  private_constant :INITIAL_COLUMN_INDEX
  O = "O"
  private_constant :O
  X = "X"
  private_constant :X

  def initialize(board)
    @board = board.map(&:split)
  end

  def winner
    if win?(board, X)
      X
    elsif win?(rotated_board, O)
      O
    else
      ""
    end
  end

  private

  attr_reader :board

  def win?(board, piece)
    catch(:halt) do
      board
        .each
        .with_index
        .with_object([board, piece], &method(:check_row))
      false
    end
  end

  def check_row((row, y_index), (board, piece))
    return unless row.first == piece

    catch(:break) do
      [[y_index, INITIAL_COLUMN_INDEX]]
        .to_enum(:then)
        .with_object([board, row, piece], &method(:find_path))
    end
  end

  def find_path(stack, (board, row, piece))
    loop do
      y_index, x_index = coordinate = stack.pop
      throw(:halt, false) if y_index.nil?
      throw(:halt, true) if x_index == row.length - 1

      children = ChildCoordinates.generate(board, piece, y_index, x_index)
      add_search_path(stack, coordinate, children)
      throw(:break) if stack.last == coordinate
    end
  end

  def add_search_path(stack, coordinate, children)
    stack.push(coordinate)
    children.each do |child|
      stack.push(child) unless stack.include?(child)
    end
  end

  def rotated_board
    board.transpose.map(&:reverse)
  end
end

Community comments

Find this solution interesting? Ask the author a question to learn more.

What can you learn from this solution?

A huge amount can be learned from reading other people’s code. This is why we wanted to give exercism users the option of making their solutions public.

Here are some questions to help you reflect on this solution and learn the most from it.

  • What compromises have been made?
  • Are there new concepts here that you could read more about to improve your understanding?