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
It's possible to submit an incomplete solution so you can see how others have completed the exercise.
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
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.
Level up your programming skills with 3,449 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors. Exercism is 100% free forever.
Sign up Learn More
Community comments