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.
