Battleship Challenge: Naval Build-up

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

# 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_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.

• I have no idea how this Ruby magic works, but your random ship placement works beautifully.
– Mast
May 9, 2015 at 18:42
• If that's quick and dirty, I'd like to see what your clean code looks like. May 10, 2015 at 2:39
• @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. May 10, 2015 at 11:26
• @Flambino I would benchmark first and iff it is too slow, I would optimize, readability is preferable over a 0.01 seconds speedup. May 10, 2015 at 18:50
• @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 :) May 10, 2015 at 19:04

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

• 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. May 23, 2015 at 9:25
• 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. May 23, 2015 at 9:34

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.

• 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. May 11, 2015 at 12:02
• Oh. Okay. Sorry then, you called it out the behavior, but I wasn't sure you were aware of the rule. May 11, 2015 at 12:04
• 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. May 11, 2015 at 12:06
• 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. May 11, 2015 at 21:18
• 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. May 11, 2015 at 22:10