Python Battleships

Battleship

In this assignment, you will be completing a Python program to play the game Battleship. If you're unfamiliar with Battleship, start this assignment by reading about Battleship on this Wikipedia page or on this board games page. You can play the game online at this games website and at many others. Note that some Battleship games on the Internet let you keep your turn after you hit a ship, but that isn't how our version works: a turn is over whether it's a hit or a miss.

Files to Download

You can download all the files for this assignment in this zip file. These files must all be placed in the same folder.

Here's a description of each of the files provided:

• battleship_functions.py: This file contains the starter code to which you will add the functions described in this handout. It also contains the constants for this assignment, a helper function, and an if __name__ == '__main__': block. Do not modify the print_sunk_message helper function.
• play_battleship.py: This file contains functions that are needed to be able to play a game of battleship. Do not make any changes to this file, other than in the if __name__ == 'main': block at the end. Note that the code in this file depends on the functions you will write for this assignment, so it won't run until those functions are completed. Reading the code in this file will help you understand how your functions are used.
• computer_functions.py: This file contains functions that are needed to play a two-player Battleship game against a computer opponent. Note that the code in this file also depends on the functions you will write for this assignment, and so it won't run until these functions are completed. You do not need to understand the code in this file.
• a2_type_checker.py: The typechecker for Assignment 2.
• Text (.txt) files: These files are sample game files. Some contain valid games, and some do not.

Terminology and Design

Terminology: Row, Column, and Cell

In this handout and in the starter code, we refer to "cell"s in a "grid", where a grid is a list of list of str and a cell is a str of length 1. A cell is a single grid element and its location is specified by its row and column indices. For example, grid[3][5] refers to the cell in row 3 and column 5. The first (top) row of a grid is row 0 and the first (leftmost) column is column 0. Increasing the row index moves down the grid; increasing the column index moves across the grid to the right.

Constants

Constants (fixed values) are variables whose values do not change once assigned. As you have seen, a different naming convention (uppercase pothole) is used for constants so that programmers know to not change their values. For example, in the Battleship starter code, the constant MAX_SHIP_SIZE is assigned the value 10 at the beginning of the module. The value of MAX_SHIP_SIZE should never change. When writing your code, if you need to refer to the maximum size of a ship, use MAX_SHIP_SIZE rather than 10. The same goes for the other constant values. They can be used anywhere in the battleship_functions.py module.

Note: do not change the values of the constants in the starter code, as the test cases may depend on them having the same values as in the starter code.

An Overview of the Design:

• Each player has two grids -- a "target grid" and a "fleet grid". Each is a list of list of str, where each inner list represents one row of the grid.
  • The "target grid" describes what you know about your targets, i.e., your opponent's placement of ships. It is initially made up entirely of unknown cells (i.e., cells containing UNKNOWN symbols).
  • The "fleet grid" describes your placement of your fleet of ships. It is initially made up of empty cells (i.e., cells containing EMPTY symbols) and cells containing ship characters.
• As the game progresses, a player's target grid is updated based on their guesses, and their fleet grid is updated when their opponent makes a guess that hits one of their ships.
• The module contains several constants:
  • MIN_SHIP_SIZE, MAX_SHIP_SIZE: the minimum and maximum length of a ship
  • MAX_GRID_SIZE: the maximum number of rows and columns in a grid
  • EMPTY: the symbol used to display a cell on a fleet grid that is not covered by a ship
  • UNKNOWN: a symbol used to display a cell on a target grid; used when the corresponding cell on the opponent's fleet grid is unknown
  • HIT: a symbol used to display a cell on a target grid; used when the corresponding cell on the opponent's fleet grid is known to contain part of a ship
  • MISS: a symbol used to display a cell on a target grid; used when the corresponding cell on the opponent's fleet grid is known to not contain part of a ship
• Each player has a "ships list" (a list of str) and a "sizes list" (a list of int). These are parallel lists. Each element in the ships list contains the single character label used to represent a ship on the fleet grid. Each element in the sizes list is the size of the corresponding ship in the ships list.
• Each player also has a "hits list", which is also a parallel list to the "ships list". It is a list of int, and each element contains the number of hits so far on each ship. A "hits list" is initialized as a list of 0s, one 0 for each ship. The game ends when one player's "hits list" shows that each ship has been completely hit (i.e., that the hits on each ship is the same as the size of each ship).
• Two different functions have been provided so that you can run the Python module and play the game. The play_single_player function involves only a single player and is included for testing purposes (we don't typically play against ourselves!). The play_versus_computer function allows a human player to play against the computer. (Our computer does not have a good strategy for playing the game, so you'll likely win most of the time.) If you complete the assignment and are up for another challenge, you could add a two-player (both human) play_ function (this is just for fun, not for marks!).

To gain a better understanding of how the functions you'll write are to be used, start by reading through the battleship_functions.py and play_battleship.py starter code to see where the functions are called and which values are passed as arguments. Reading and understanding the starter code is an important part of completing this assignment.

What to Do

In the starter code file battleship_functions.py, complete the following function definitions. Use the Function Design Recipe that you have been learning in class. We have included the type contracts in the following table; please read through the table to understand how the functions will be used. We will be evaluating your docstrings in addition to your code. Please include two examples in your docstrings. You will need to paraphrase the full descriptions of the functions to get an appropriate docstring description. Define these functions in battleship_functions.py only; do not include any new code in play_battleship.py.

• read_ship_data: (file open for reading) -> list of list of objects
  • The parameter represents a game file that is open for reading. This function returns a list where the first element is a list of strings containing the ship characters in the order they appear in the file, and the second element is a list of ints containing the ship sizes in the order they appear in the file.
  • Do not provide docstring examples for functions that have a file parameter.
• has_ship: (list of list of str, int, int, str, int) -> bool
  • The first parameter is a square potential fleet grid, the second and third parameters are the row and column index of the cell containing the top/left corner of the ship, the fourth parameter is a character representing a ship, and the fifth parameter is the size of the ship. This function returns True iff the ship appears with the correct size, completely in a row or a completely in a column at the given starting cell.
• validate_character_count: (list of list of str, list of str, list of int) -> bool
  • The first parameter is a square potential fleet grid, the second parameter is a list of ship characters, and the third parameter is a list of ship sizes. This function returns True iff the grid contains the correct number of ship characters for each ship, and the correct number of EMPTY characters.
• validate_ship_positions: (list of list of str, list of str, list of int) -> bool
  • The first parameter is a square potential fleet grid, the second parameter is a list of ship characters, and the third parameter is a list of ship sizes. This function returns True iff the grid contains each ship aligned completely in a row or column. That is, it should check that each ship is contained completely in consecutive cells all in the same row, or all in the same column, depending on if it is oriented horizontally or vertically (no other orientation).
• validate_fleet_grid: (list of list of str, list of str, list of int) -> bool
  • The first parameter is a square potential fleet grid, the second parameter is a list of ship characters, and the third parameter is a list of ship sizes. This function returns True iff the potential fleet grid is a valid fleet grid.
  • For a fleet grid to be valid, it must contain the correct number of ship characters (based on the second and third parameters) and the correct number of EMPTY characters, and must have ships placed in consecutive cells, either horizontally or vertically (no other orientation). Note that this means that each ship appears exactly once in the grid.
  • Use the bad*.txt files that you downloaded to help you test your validate_fleet_grid function, although you should not assume that those files test all possible invalid cases!
• valid_cell: (int, int, int) -> bool
  • The first parameter is a row index, the second parameter is a column index, and the third parameter is a grid size. This function returns True iff the cell specified by the row and the column is a valid cell inside a square grid of that size.
• is_not_given_char: (int, int, list of list of str, str) -> bool
  • The first parameter is a row index, the second parameter is a column index, the third parameter is a grid, and the fourth parameter is a single character. This function returns True iff the cell specified by the row and column is not the given character.
• update_fleet_grid: (int, int, list of list of str, list of str, list of int, list of int) -> NoneType
  • The first and second parameter are a row index and a column index, the third parameter is a fleet grid, the fourth and fifth parameters are a list of ship characters and a list of ship sizes, and the sixth parameter is a hits list. This function is called when there is a hit in the cell specified by the row and column. This function updates the fleet grid (by converting the ship character in the cell to upper-case), and also the hits list to indicate that there has been a hit.
  • If a ship is sunk (i.e. the value for that ship in the hits list reaches the size of that ship), then this function should make a call to print_sunk_message to indicate that a ship has been sunk. The code for print_sunk_message is included in battleship_functions.py. Review its docstring to see what it does.
• update_target_grid: (int, int, list of list of str, list of list of str) -> NoneType
  • The first and second parameters are the row and column indices of a cell, and the third and fourth parameters represent a target grid and a fleet grid, respectively. This function sets the element of the specified cell in the target grid to HIT or MISS using the information from the corresponding cell from the fleet grid.
• is_win: (list of int, list of int) -> bool
  • The first parameter is a list of ship sizes, and the second parameter is a hits list. This function returns True iff the number of hits for each ship in the hits list is the same as the size of each ship, i.e., if each ship has been sunk.

Format of Game Files

Each game file (e.g. game1.txt) contains the game parameters and the fleet grid for the player to use. The format of a game file is as follows:

• The first line holds the ship characters with a space between each pair of characters. Each ship character is a str of length 1 containing a lower-case letter.
• The second line holds the ship sizes. The first and second lines of a game file are parallel in the sense that the first ship on the first line has the size given by the first integer on the second line, the second ship on the first line has the size given by the second integer on the second line, and so on.
• Each remaining line of the file is one row of the fleet grid with no spaces between cells.

All files provided, and all files we will test your code on, will follow this format, although they may not define a valid game.

The files game1.txt, game2.txt, and game3.txt are valid games of varying sizes. The files bad*.txt are invalid game files.

Input and Output

Your battleship_functions.py file should contain the starter code, plus the function definitions specified above. Your battleship_functions.py file must not include any calls to function print, other than the call in the provided print_sunk_message function.

Do not call input or open in the code that you write. Notice that one of the required functions takes an open file, not a string.

Additional Requirements

• Do not change any of the existing code.
• Do not use any break or continue statements. Any functions that do will receive a mark of zero. We are imposing this restriction because using them tends to lead to badly-written code.
• Do not add any code in battleship_functions.py that is outside of a function definition or the if __name__ == '__main__': block.
• Do not add any import statements.

How to tackle this assignment

This program is much larger than what you wrote for Assignment 1, so you'll need a good strategy for how to tackle it.

• To avoid getting overwhelmed, deal with one function at a time. We are not suggesting an order in which you complete the functions, so you should spend some time organizing your plan ahead of time. Start by writing the simplest functions; i.e. the ones that you think can be implemented in a few lines without the use of helper functions.
• We expect that the three functions with names starting with validate_ are likely to be the most challenging for you to write. If you'd like to test your other code using play_battleship.py before you get the validate_ functions working, you can temporarily set their function bodies to only return True, and then play games using only the provided game files that contain valid boards.
• For each function that you write, start by adding the two example calls to the docstring before you write the function. This will help you understand what code you need to write, and produces some tests for the last step of the Design Recipe.
• Keep in mind throughout that any function you have might be a useful helper for another function. Part of your marks will be for taking advantage of opportunities to call an existing function.
• As you write each function, begin by designing it in English, using only a few sentences. If your design is longer than that, shorten it by describing the steps at a higher level that leaves out some of the details. When you translate your design into Python, look for steps that are described at such a high level that they don't translate directly into Python. Design a helper function for each of these, and put a call to the helpers into your code. Don't forget to follow the design recipe for each helper!

How you should verify your code

One way to test your code is to play the game using one of the play_ functions given in the starter code. However, you should also test each function individually by writing code to verify your functions in the if name == '__main__:' block in battleship_functions.py. In fact, playing the game is not a productive way to find bugs or problems you're writing, because it's difficult to see what leads to any problems that come up. Once you are confident that your functions are working as they should, then go ahead and play the game to discover more bugs. All verification code, including any calls to the starter code functions, should be entirely within the if __name__ == '__main__': block and not anywhere else in battleship_functions.py.

You can also uncomment the call to doctest.testmod() to run your doctests. Note that this requires your docstrings to be properly formatted!

Type checks

We are providing a type-check module that can be used to test whether your functions have the correct parameter and return types. To use the type checks, place a2_type_checker.py in the same directory as your battleship_functions.py and Run it.

If the type-checks pass: Then your function parameters and return types match the assignment specification. This does not mean that your code works correctly in all situations. We will do a thorough job of testing your code once you hand it in, so be sure to thoroughly test your code yourself before submitting.

If the type-checks fail: Look carefully at the message provided. One or more of your parameter or return types does not match the assignment specification. Fix your code and re-run the type-checks.

Make sure the type-check module tests pass on every function you have written before submitting your solution! Again, this doesn't mean your code works correctly in all situations, but it does mean we will be able to run our marking tests on your code.