17
\$\begingroup\$

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 if there's no room left
  # for the ship.
  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 << span.slice(offset, size)
    @ship_squares.last.each { |cell| cell.ship = size }
  end

  # Get an array of ship-coordinate-sets; useful for creating easily-parsable
  # output
  def ship_coordinates
    @ship_squares.map do |squares|
      squares.map { |square| [square.x, square.y] }
    end
  end

  # For pretty-printing the grid
  def to_s
    @squares.map do |row|
      row.map(&:to_s).join(" ")
    end.join("\n")
  end

  private

  # Helper method for #free_squares
  def free_chunks(grid)
    grid.flat_map do |row|
      row.chunk(&:free?).select(&:first).map(&:last)
    end
  end
end

# A grid square
class Square
  attr_reader :x, :y
  attr_accessor :ship

  # Init a square with the grid object it belongs to, and its x, y coordinates
  def initialize(grid, x, y)
    @grid = grid
    @x = x
    @y = y
    @ship = nil
  end

  # Is there a ship on this square?
  def blank?
    ship.nil?
  end

  # Is this square and its neighbors unoccupied?
  def free?
    blank? && neighbors.all?(&:blank?)
  end

  # This square's horizontal, vertical, and diagnoal neighbors
  def neighbors
    @neighbors ||= [-1, 0, 1].repeated_permutation(2).map do |dx, dy|
      @grid[x + dx, y + dy] unless dx.zero? && dy.zero?
    end.compact
  end

  def to_s
    blank? ? "·" : ship.to_s # note: using unicode character
  end
end

How it works: When placing a ship, the code first finds contiguous spans/runs of "free" squares using Array#chunk, i.e. arrays of squares that are unoccupied, and whose neighbors are also unoccupied. It does so for the regular grid (an array of rows), and the transposed grid (an array of columns) to get both horizontal and vertical spans. It then discards spans that are too short for the ship, and picks a random span from the remaining ones - or raises an exception if none remain. Lastly, it places the ship somewhere within the chosen span.

You can use it like so:

# create a standard 10x10 grid
grid = Grid.new

# place some ships of varying sizes (probably best to go from largest
# to smallest)
ships = [5, 4, 3, 2, 1]
ships.each { |size| grid.place_ship(size) }

# pretty-print the grid
puts grid

The above will output:

· · · · · · · · · ·
· 3 · · · · · · · ·
· 3 · · 4 4 4 4 · ·
· 3 · · · · · · · ·
· · · · · · · · 5 ·
· · · · · · · · 5 ·
· · · · 1 · · · 5 ·
· · · · · · · · 5 ·
· 2 · · · · · · 5 ·
· 2 · · · · · · · ·

Or you can get some more easily-parsable output like so:

grid.ship_coordinates.each do |squares|
  puts squares.map { |xy| xy.join(",") }.join(";")
end
8,4;8,5;8,6;8,7;8,8
4,2;5,2;6,2;7,2
1,1;1,2;1,3
1,8;1,9
4,6

I don't like the circular reference between Grid and Square. It's a (anti-)pattern I've come across when doing little programming challenges involving grids: I want a "grid" object that I can query, but I also want individual "cell"/"square" objects that know their context. I could have worked around it, but... shrug. As mentioned I wasn't too concerned, and this was a quick-and-dirty solution, but I'd love to see a neater solution.

Any input is welcome, though!

And again, if anyone wants to use this for anything, go right ahead!


Edit: Here's a web version. Same logic, just written in CoffeeScript. And I added options for how the ships should be spaced apart. It can output a few different formats, if anyone needs to feed their Battleship bot.

\$\endgroup\$
  • \$\begingroup\$ I have no idea how this Ruby magic works, but your random ship placement works beautifully. \$\endgroup\$ – Mast May 9 '15 at 18:42
  • 3
    \$\begingroup\$ If that's quick and dirty, I'd like to see what your clean code looks like. \$\endgroup\$ – Wayne Conrad May 10 '15 at 2:39
  • 1
    \$\begingroup\$ @WayneConrad Heh, thanks. When I said quick and dirty, it's mostly about the structure (that gross circular reference I mention), and overall efficiency. The code may look ok, but it's doing a lot of redundant work. Like checking a square's neighbors: Tons of overlap there, if you've just checked the square next to it. Five squares next to each other have 16 neighbors in total, but individually they each have 8 neighbors. So the code will perform 40 checks, even though 24 of them are totally redundant. That ain't too clever. \$\endgroup\$ – Flambino May 10 '15 at 11:26
  • \$\begingroup\$ @Flambino I would benchmark first and iff it is too slow, I would optimize, readability is preferable over a 0.01 seconds speedup. \$\endgroup\$ – Caridorc May 10 '15 at 18:50
  • 1
    \$\begingroup\$ @Caridorc Oh, I agree. Again, I'm not worried about speed, per se. Just that it's not particularly... elegant, for lack of a better word. It's just a pretty blunt approach. I'd still prefer readability over cleverness, but if there's a good compromise to be had, I'd be interested :) \$\endgroup\$ – Flambino May 10 '15 at 19:04
4
\$\begingroup\$

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".

\$\endgroup\$
  • 1
    \$\begingroup\$ True that it's inefficient; I'm well aware of that (but I let it be since speed wasn't an issue). Using a zero as "padding" is a neat solution, though. I started with ships being simple Struct-based objects, and squares holding either nil or a Ship. Didn't want to introduce a third "non-ship" type. But after I switched to squares just holding nil or an int, using a zero works well. Nice idea. \$\endgroup\$ – Flambino May 23 '15 at 9:25
  • 1
    \$\begingroup\$ As for #[]: The checks are there to guard against negative indices. I started with the same code as you suggest, but then calling grid[3, -1] would still return a square, just from the opposite side of the board. So the double check was to avoid Array#[]'s usual behavior. The unicode comment wasn't about the character itself, but just a note to say you might need the # encoding: UTF-8 comment if you want old Ruby versions to stop complaining about a multibyte character. Not really a concern, just an old habit. \$\endgroup\$ – Flambino May 23 '15 at 9:34
1
\$\begingroup\$

Your Ruby-Fu is well beyond mine, so I can't offer a "review" really. All I can do is point out a bug, that is really just a misunderstood requirement.

In your code, you don't allow ships to "touch", or be placed in adjacent squares. This isn't one of the rules. Ships are allowed in adjacent squares. They just can't (obviously) overlap and occupy the same square.

This opens up a strategy against your "AI"'s placement that wouldn't otherwise exist in the game. Let's say I know where the aircraft carrier is. Once I know that, I've eliminated an additional 16 squares from my choices, greatly increasing my chances of finding another one of the ships.

\$\endgroup\$
  • \$\begingroup\$ Oh, I know it's not a rule - it was a choice I made. As I write, it's "just to make the job harder for the opponent". But I do see how it might do the opposite as well. However, though it's not implemented in the review code and thus not really relevant, I've added a choice of different "spacing rules" on the web version. \$\endgroup\$ – Flambino May 11 '15 at 12:02
  • \$\begingroup\$ Oh. Okay. Sorry then, you called it out the behavior, but I wasn't sure you were aware of the rule. \$\endgroup\$ – RubberDuck May 11 '15 at 12:04
  • \$\begingroup\$ Oh. Okay. I just re-read your question. And given that I now understand what you were trying to do, I still think it's a bug. It actually makes it easier for an opponent that has figured out the placement behavior. \$\endgroup\$ – RubberDuck May 11 '15 at 12:06
  • \$\begingroup\$ True, that's a risk. Don't know how many hits it would take for a bot to reach that conclusion about placement, though. And it can't know for sure until it's actually sunk all the ships, can it? Anyway, the code can be tweaked though, as the web version is, to allow adjacent ships, but I'll leave it as-is in the question, of course. \$\endgroup\$ – Flambino May 11 '15 at 21:18
  • \$\begingroup\$ Yeah. You're right. I was thinking about a computer player using this to generate their grid in a 1 player game. A person would probably figure it out much faster than a bot. Anyway, it's all moot. \$\endgroup\$ – RubberDuck May 11 '15 at 22:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.