Minesweeper: how many mines are near?

Write a program that adds the numbers to a minesweeper board.

Minesweeper is a popular game where the user has to find the mines using numeric hints that indicate how many mines are directly adjacent (horizontally, vertically, diagonally) to a square.

In this exercise you have to create some code that counts the number of mines adjacent to a square.

Transforms boards like this (where * indicates a mine):

+-----+
| * * |
|  *  |
|  *  |
|     |
+-----+


into this:

+-----+
|1*3*1|
|13*31|
| 2*2 |
| 111 |
+-----+


As can be seen in the provided test suite, a method Board.transform is required whose input and output are arrays of strings, representing the rows of the board. A ValueError must be raised in case of an invalid character or a non-border cell at the edge of the board.

My solution:

class ValueError < RuntimeError
end

class Position
attr_reader :y, :x

def initialize(y, x)
@y, @x = y, x
end

def neighbors
Position.each(y-1 .. y+1, x-1 .. x+1)
end

def self.each(ys, xs)
return enum_for(__method__, ys, xs) unless block_given?

ys.each do |y|
xs.each do |x|
yield Position.new(y, x)
end
end
end

def ==(other)
to_a == other.to_a
end

alias eql? ==

def hash
to_a.hash
end

def to_a
[y, x]
end
end

class Cell
BLANK_CELL_CHAR = ' '
MINE_CELL_CHAR = '*'
BORDER_CELL_REGEX = /\A[-+|]\z/

def self.from_char(char)
case char
when BLANK_CELL_CHAR
BlankCell.new
when MINE_CELL_CHAR
MineCell.new
when BORDER_CELL_REGEX
BorderCell.new(char)
else
raise ValueError, "Illegal character"
end
end

def blank?
false
end

def mine?
false
end

def border?
false
end
end

class BlankCell < Cell
attr_accessor :num_adjacent_mines

def initialize(num_adjacent_mines = nil) # nil means unknown
@num_adjacent_mines = num_adjacent_mines
end

def blank?
true
end

def to_s
if @num_adjacent_mines.nil? || @num_adjacent_mines == 0
BLANK_CELL_CHAR
else
@num_adjacent_mines.to_s
end
end
end

class BorderCell < Cell
def initialize(char)
@char = char
end

def border?
true
end

def to_s
@char
end
end

class MineCell < Cell
def mine?
true
end

def to_s
MINE_CELL_CHAR
end
end

class Board
def self.transform(input)
board = Board.new(input)
board.transform!
board.to_a
end

def initialize(input)
@height = input.length
@width = input.first.length

raise ValueError, "All lines must be of the same length" if input.any? { |line| line.length != @width }

@cells = Position.each(0...@height, 0...@width).map do |position|
char = input[position.y][position.x]
cell = Cell.from_char(char)
raise ValueError, "Expected a border cell" if should_be_border?(position) && !cell.border?
[position, cell]
end.to_h
end

def transform!
Position.each(0...@height, 0...@width).each do |position|
tranform_at!(position)
end
end

def to_a
(0...@height).map do |y|
(0...@width).map do |x|
at(Position.new(y, x)).to_s
end.join
end
end

private

def tranform_at!(position)
cell = at(position)
if cell.blank?
cell.num_adjacent_mines = position.neighbors.count do |position|
at(position).mine?
end
end
end

def at(position)
@cells.fetch(position)
end

def should_be_border?(position)
position.y == 0 || position.y == @height - 1 ||
position.x == 0 || position.x == @width - 1
end
end


What do you think?

• Why is position a class? – Nakilon Jan 8 '16 at 16:48
• @Nakilon Explain how I can solve this in a different way in your answer. – Spike Jan 11 '16 at 9:24
• OOP is misused here. As I see Position here is conceptually just an Array with its own and 9 more coordinates. – Nakilon Jan 11 '16 at 10:20

2 Answers

If you're using some kind of TDD all classes must be test-covered. Adding classes that are not mentioned in tests at least confusing, at most - leads to unnecessary complexity.

What is the difference between Cell, MineCell, Bordercell and BlankCell? They are storing input/output methods but must be responsible for business logic, I think. They are acting like higher level of Position abstraction. BTW, Position.each - good "trick".

Code is readable and easy to understand.

When I looked through once again, I noticed that this part can be improved:

def blank?
false
end
def mine?
false
end
def border?
false
end
######
def blank?
self.is_a?(BlankCell)
end
def mine?
self.is_a?(MineCell)
end
def border?
self.is_a?(BorderCell)
end


This methods definitions can be removed from Cell's subclasses.

My way (written in "least resistance way" with tests):

class ValueError < RuntimeError; end

class Board

def self.transform(input)
validate(input)
out = mark_field(substitute(input[1..-2]))
to_s(out, input)
end

private

class << self
def mark_field(field)
field.each.with_index.with_object(field) do |(row, r_indx), obj|
row.each.with_index do |cell, c_indx|
increment_cells(r_indx, c_indx, obj) unless cell
end
end
end

def substitute(input)
input.map do |line|
line.gsub(/[^*\s]/, '').chars.map{ |ch| ch == '*' ? nil : 0 }
end
end

def closest_cells(row, col, field)
arr = (row-1..row+1).flat_map{ |r| [r].product([*(col-1..col+1)])}
arr.reject{ |r, c| r < 0 || c < 0 || [r, c] == [row, col] || !(field[r] && field[r][c]) }
end

def increment_cells(row, col, arr)
closest_cells(row, col, arr).each { |r, c| arr[r][c] += 1 }
end

def to_s(out, input)
input[1..-2] = out.map do |line|
"|#{line.map{ |c| c == 0 ? ' ' : c ? c : '*' }.join}|"
end
input
end

def validate(input)
raise ValueError unless input.map(&:size).uniq.count == 1 &&
input.reject{ |line| line.count('|') == 2 }.size == 2 &&
!input.join.gsub!(/[^*\s\|\+\-]/, '')
end
end

end


I'd start by asking: What is the problem really asking for? As I see it, it's asking you to go through every cell on the grid and, if a cell is blank, fill it in with the number of surrounding bombs. When viewed from that persepctive, a minimal solution is just a map over the grid, and a helper function to count bomb neighbors at a given position.

While taking an object-oriented approach might be appropriate as requirements grow, I think it is likely to lead to over-engineering for the problem at hand, and to obscure, rather than elucidate, the essence of the algorithm. I can give advice on simplifying the OO solution if you like, but consider this alternative instead:

board = <<EOS
+-----+
| * * |
|  *  |
|  *  |
|     |
+-----+
EOS
.split("\n").map{|x| x.split('')}

def bomb_neighbors(i, j, arr)
[-1,0,1].product([-1,0,1]).count {|k,l| arr[i+k][j+l] == '*' }
end

labeled_board = board.map.with_index do |row, i|
row.map.with_index do |cell, j|
next cell unless cell == ' '
bombs = bomb_neighbors(i, j, board)
bombs == 0 ? ' ' : bombs
end
end

puts labeled_board.map{|x| x.join('')}.join("\n")


You can probably appreciate the advantages at a glance, but to name a few:

• Shorter and clearer, with very little incidental complexity
• No need to create separate classes for the different "types" of cell. For this problem, you care only if a cell is blank or non-blank. Everything else returns itself.
• No need for case statements or regexes
• No need to think about the "border" in your solution -- it's not fundamentally part of the problem, so shouldn't play a role in the solution.