Battleship Challenge: Naval Build-up

The community challenge for this month says:


Everyone has played Battleship. Let's implement the logic that sinks one.

But that presumes that there's something to sink. We can't have the armada turn its guns on itself out of boredom.

So I figured I'd write something that could randomly place ships on a Battleship grid. Don't know if I'll have the time/inclination to write a Battleship-bot as the challenge suggests, but if I do, a grid generator will be useful. Might be useful to someone else as well - if it's worth a damn.

So I wrote something quick and dirty. It's very rough code, but it does the job.

The specs/assumptions I went with were:

• The grid is square

• No two ships can be adjacent to each other (i.e. touching)

The latter point is just to make the job harder for the opponent; no risk of two ships being hit by the opponent targeting the neighbors of a square that's known to be harboring (pun!) a ship.

I haven't implemented anything to make this playable - it just builds the grid and that's that. It's not exactly efficient, but I'm not concerned about performance, to be honest; it's just a means to an end (the bot), not an end in itself.

That's enough ado, so here's the code:

```
class Grid
attr_reader :size

# Init a grid by its size (the number of squares/cells on a side)
def initialize(size = 10)
@size = size
@ship_squares = []
@squares = Array.new(size) do |y|
Array.new(size) { |x| Square.new(self, x, y) }
end
end

# Get a grid square by is x, y coordinates. Returns nil if the
# coordinates are out-of-bounds
def [](x, y)
return nil unless (0...size).cover?(x)
return nil unless (0...size).cover?(y)
@squares[y][x]
end

# Get (horizontally or vertically) contiguous spans of free squares,
# i.e. squares that are unoccupied and whose neighbors are unoccupied
def free_squares
free_chunks(@squares) + free_chunks(@squares.transpose)
end

# Randomly place a ship. This'll raise an error

Square#free? is rather inefficient — if the square itself is not occupied, it needs to check up to 8 neighboring squares. To compute Grid#free_squares, then, you need to inspect nearly 2 orientations × 10 rows × 10 columns × 8 neighbors ≈ 1600 squares (actually a bit fewer, due to edges and existing ships).

In contrast, Grid#place_ship is a rare operation. Therefore, a simple optimization is that when you place a ship, you also mark a one-unit buffer zone around the ship as reserved. One way to do that is to say that the buffer squares are occupied by "ship 0".

class Grid
  def place_ship(size)
    span = free_squares.select { |span| span.count >= size }.sample
    raise "Ocean's gettin' crowded" unless span
    offset = rand(0..span.count - size)
    @ship_squares << (ship = span.slice(offset, size))
    ship.each do |cell|
      cell.ship = size
      # Reserve a buffer zone around the ship
      cell.neighbors.each { |neighbor| neighbor.ship ||= 0 }
    end
  end
end

class Square
  # Is there no ship on this square?
  def blank?
    ship.nil? || ship == 0
  end

  # Is this square and its neighbors unoccupied?
  def free?
    ship.nil?
  end
end

Nitpicks

In Square#initialize, it is unnecessary to write @ship = nil.

In Square#to_s, a more informative comment would be # '·' == "\u00b7".

StackExchange Code Review Q#90267, answer score: 4