Talk to me about Battleship… your job could depend on it!

The classic game “Battleship” has captivated military sailors and civilians alike for at least 100 years as players attempt to hone in on a strategy to destroy their opponent’s ships placed on a game board while avoiding detection and certain destruction of their own ships.  The game became one of the earliest home computer programs when it was released on the Z80 Compucolor back in 1979, according to Wikipedia’s sources.  And for more than 35 years since, it has been a concept one could use to test someone’s knowledge of programming a system in an elegant way.

Recently, I sat in with a colleague of mine while he interviewed a prospective employee.  The idea of using Battleship as the pseudo-coding exercise came to him while he was surfing articles on the Internet regarding good thought exercises to engage interviewees.  We work for a company where object-oriented programming is the flavor of choice, and so we were interested in how our prospie would arrange the battleship game to best leverage the features of object-oriented programming languages.

As this thought exercise was posited, I started thinking about how I would arrange the game to take advantage of the OO paradigm.  I imagined having a class Ship that would contain various parameters about itself, such as its size, X, Y, and orientation.  It could also potentially have an array consisting of the tiles it occupies rather than its own size, or Ship itself could even be an abstract class that has subclasses Size2Ship, Size3Ship, and Size4Ship.  The game board could consist of two ArrayList<Ship>s, one for each player, and the first player with an empty ArrayList would lose.  There seem to be a few valid ways to go about arranging the data, nevertheless.  Then, you have to consider exactly how you want to track what part of each ship has been hit, including iterating over each Ship to see if it has the desired point, not to mention checking for invalid inputs or configurations such as placing ships that overlap.

As we were watching our candidate think through the process of building a Battleship game using the tenets of OOP, we realized something fantastic about this particular problem.  Because of its grid nature, it lends well to being implemented with standard procedural paradigms where you simply track everything with a 2-dimensional array and don’t really pay a whole lot of attention to the concept of individual ships existing on the board.  To be honest, I think this sort of implementation for the Battleship game in particular is a bit easier since it reduces overhead (it’s certainly easier to implement it this way on a Zilog Z80 processor from 1979, for that matter).  Then instead of having to ask each ship if it has the desired square to hit, you just check one single foundation of truth — your 2-dimensional game board array.  Our prospie had many years’ experience with things like low-level firmware for embedded devices and writing drivers, so it’s understandable this would be their tendency too.  But since we did ask for something truly OO, we ended up witnessing something that really made us appreciate why Battleship was a good choice for an interview.

What came out of the thought experiment was a game where, instead of numerous Ship classes being generated, there was a single Ships class that would keep track of a fixed number of ships on the board using various arrays and tricks to ensure the validity of the data.  While the tricks were indeed cool, you can imagine this might as well have been a static class where one instance of it gets initialized and then procedural logic controls the game flow thereafter.  The nuances of objected-oriented design really weren’t explored at all during the thought experiment.

Battleship probably isn’t the only good test case.  There has got to be an entire set of problems or tasks one could solve easily in both procedural and object-oriented paradigms.  These problems, such as Battleship, make a great test to see if someone is truly an object-oriented thinker.  They “camouflage” themselves due to:

• Potential to solve the problem by simply using familiar data structures such as n-dimensional arrays
• Not having a hierarchical “is-a” or “has-a” structure that absolutely must be enforced for the logic to work

Now is where you can contribute!  Share your thoughts on any other good test problems you’ve come across that straddle this object-oriented versus procedural paradigm, or suggest additional bullet points for above as to what makes a good problem, or tell me how my design for object-oriented Battleship sucks because it wastes way more memory or CPU time than yours… in the comments.