The Problem: Minesweeper

This exercise, one of the ones designated “Medium”, is called “Minesweeper”. It’s an exercise to populate a minesweeper grid with the number values for the eponymous computer game.

Your task is to add the mine counts to empty squares in a completed Minesweeper board. The board itself is a rectangle composed of squares that are either empty (‘ ‘) or a mine (‘*’). For each empty square, count the number of mines adjacent to it (horizontally, vertically, diagonally). If the empty square has no adjacent mines, leave it empty. Otherwise replace it with the adjacent mines count.

https://exercism.org/tracks/ruby/exercises/minesweeper/solutions/armahillo

Pass 1: Scaffolding

I usually like to start with creating a separate class, to keep the “execution flow” separate from the data modeling. From some preliminary test runs, I knew that the inputs would get passed in as a string and get passed out as a string. But I also knew that in order to leverage a lot of the Ruby enumerable methods, I would need to convert to Arrays. Since we care about setting a number, we’re going to initialize any blank space to a 0, and then reverse that if it’s still 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Minefield
  attr_accessor :grid

  def initialize(input)
    @grid = input.map! { |i| i.chars.map! { |c| c == ' ' ? 0 : c  } }
  end

  def to_s
    @grid.map { |i| i.map(&:to_s).join.gsub('0', ' ') }
  end
end

class Minesweeper # this is the default class the tests expect
  def self.annotate(input)
    field = Minefield.new(input)


    field.to_s
  end
end

Due to some junk inputs, there was a little bit of robustness that had to be added to the initialize and to_s methods:

# In
@grid = input.map! { |i| i == '' ? '' : i.chars.map! { |c| c == ' ' ? 0 : c  } }

# Out
@grid.map { |i| i.is_a?(Array) ? i.map(&:to_s).join.gsub('0', ' ') : i || '' }

Once I had this, it gave me an abstraction I could work with, and also get back out of.

Pass 2: Finding neighbors

One of the early starts I had involved trying to find each empty square and then calculating how many mines were around it, but for most boards that would be more iterations since there are generally more empty spaces than mines.

Instead, what I decided to do was find each mine and then consider all of its neighbors. A “neighbor” is any adjacent square (orthogonal, diagonal), like this (the 💣 is the mine):

🔘🔘🔘
🔘💣🔘
🔘🔘🔘

The cool thing here is that any neighbor is adjacent, meaning it’s only 1 unit away on either row or column, so we can define any given neighbor set as:

[row-1, col-1], [row-1, col], [row-1, col+1]
[row,   col-1],      💣       [row,   col+1]
[row+1, col-1], [row+1, col], [row+1, col+1]

If we iterate through the field as a 2D array (rows, columns), we then can consider each individual cell (a ‘*’ is a mine, here):

1
2
3
4
5
6
7
8
9
10
11
12
13
class Minesweeper # this is the default class the tests expect
  def self.annotate(input)
    field = Minefield.new(input)

    field.grid.each.with_index do |row, row_index|
      row.each.with_index do |col, col_index|
        field.update_neighbors(row_index, col_index) if col == '*'
      end
    end

    field.to_s
  end
end

But what about when we’re looking at cells on the edge? Well, we know that we don’t want any negative values for either. We can also ensure that we’re not using values that are equal or greater than the number of rows / cols. I called the method that determines this “viable_neighbors”.

1
2
3
4
5
6
7
8
9
10
11
def viable_neighbors(row, col)
  [
    [row-1, col-1], [row-1, col], [row-1, col+1],
    [row,   col-1],               [row,   col+1],
    [row+1, col-1], [row+1, col], [row+1, col+1]
  ].reject { |neighbor|
    neighbor.any?(&:negative?) ||
    neighbor[0] >= @grid.size ||      # @grid.size is the number of rows
    neighbor[1] >= @grid.first.size   # @grid.first.size is the number of columns
  }
end

This then returns an array of tuples that we can increment:

1
2
3
4
5
def update_neighbors(row = 0, col = 0)
  viable_neighbors(row, col).each do |neighbor|
    @grid[neighbor[0]][neighbor[1]] += 1
  end
end

Pass 3: Implementing Enumerable

This is perhaps some syntactic sugar, but I really wanted to have a simpler API where I can just use :each instead of a nested loop. So I included Enumerable, and then added this method to Minefield:

1
2
3
4
5
6
7
def each
  @grid.each.with_index do |cells, row|
    cells.each.with_index do |cell, col|
      yield(cell, row, col)
    end
  end
end

This then let me change the .annotate method to:

1
2
3
4
5
6
7
8
9
def self.annotate(input)
  @field = Minefield.new(input)

  @field.each do |cell, row, col|
    @field.update_neighbors(row, col) if cell == '*'
  end

  @field.to_s
end

Because of a bad-input gotcha, had to add this inside the outer loop of :each:

@grid.each.with_index do |cells, row|
  next unless cells.is_a?(Array)

At this point, the tests passed.

Pass 4: Polish

At this point I made two final changes:

class Minefield
  MINE_CHAR = '*'

The “mine” character is defined as a constant. Also:

neighbor.any?(&:negative?) || !@grid.dig(*neighbor).is_a?(Integer)

Array gives the :dig method, which lets you specify a series of args and it will attempt to safely find its way into that element. All we care about is whether or not the field is an integer already. If the attempted cell is out of bounds, we just ignore it.

A gotcha here is that we have to keep the “negative” check because technically you can access negative indices in an array, it just wraps around in reverse; but not in the other direction.

irb(main):001> array = [1,2,3]
=> [1, 2, 3]
irb(main):002> array[2]
=> 3
irb(main):003> array[-1]
=> 3

Tests all passed. I added a couple comments to clarify, and submitted!