Short Exercises #4¶

Due: Friday, Nov 5th at 4:30pm CDT (Note the non-standard due date)

The following short exercises are intended to help you practice some of the programming concepts introduced in the first four weeks of the quarter. These exercises should not take more than 1-2 hours in total to complete.

Fetching the instructor files¶

To get the files for this set of short exercises, first set the GITHUB_USERNAME environment variable by running the following command at the Linux command line (replacing replace_me with your GitHub username):

GITHUB_USERNAME=replace_me

(remember you can double-check whether the variable is properly set by running echo $GITHUB_USERNAME)

Then navigate to your Short Exercises repository and pull the new material:

cd ~/cmsc12100
cd short-exercises-$GITHUB_USERNAME
git pull upstream main

You will find the files you need in the se4 directory.

IMPORTANT: If you are unable to obtain the instructor files by running the commands above do not try to add the files in some other way. Doing so will likely prevent you from submitting your code. Instead, please seek assistance on Ed Discussion or at office hours.

Testing¶

As usual, you will want to test your solution manually before you try the automated tests. (See below for examples.) Remember to set up auto reload before you start testing.

$ ipython3

In [1]: %load_ext autoreload

In [2]: %autoreload 2

In [3]: import se4

A Game¶

Battleship is a strategy game normally played by two people. Each player lays out a fleet of ships on a board (a 10x10 grid) that is hidden from the other player, and then the players take turns calling shots in an attempt to sink each other’s ships. The game ends when one player has no ships left on the board (that is, they’ve all been sunk).

In this set of short exercises, you are going to implement several methods for managing a player’s board (that is, the grid) for a simplified version of this game.

Initially, the every cell in the board will contain water (represented as "Water"). Using just the first letter to represent the values in the cells, the board would look like this:

W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W

After creating the initial board, a player can deploy up to five ships drawn from the following list of ships: Battleship, Carrier, Destroyer, Patrol Boat, and Submarine. Each ship occupies a certain number of cell in the board:

Battleship: 4
Carrier: 5
Destroyer: 3
Patrol Boat: 2
Submarine: 3

In our version of the game, ships can only be oriented horizontally on the board. (In the board game Battleship, ships can be oriented horizontally and vertically.) To deploy a ship, the user specifies a ship and a starting grid cell. For example, let’s say we start from an empty board and deploy a Destroyer at location (3, 2). The resulting board would be: (D stands for for Destroyer):

W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W D D D W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W

The user will specify a fleet using a dictionary. Here’s a fleet that contains four ships:

{'Carrier': (0, 4),
 'Battleship': (1, 0),
 'Destroyer': (3, 2),
 'Patrol Boat': (9, 8)},

The Carrier will occupy grid spots (0, 4), (0, 5), (0, 6), (0, 7), and (0, 8) because it starts at (0, 4) and has width 5. The Battleship will occupy grid spots (1, 0) through (1, 3) and so, on. Here’s the board after these ships have been deployed (again using the first letter of the string to represent a given value, B for "Battleship" etc.

W W W W C C C C C W
B B B B W W W W W W
W W W W W W W W W W
W W D D D W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W S S S W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W P P

We will refer to the part of a ship in a specific grid cell as a fragment. So, in the figure above there are fragments of the Patrol Boat in locations (9, 8) and (9, 9), for example.

Once the ships have been deployed, the game can start. In our game, a single player (who we will call the shooter) will attempt to sink the ships on a board. The shooter will call out shot locations. For example, they might choose location (0, 3). This shot would land in the water and so, the board’s owner would reply with Miss. If the shooter called out (0, 4), the board’s owner would reply with Hit. The shot hit a ship, but the ship has not yet sunk. The shooter might then call out (0, 5) (yields Hit), (0, 6) (yields Hit), (0, 7) (yields Hit), and finally, (0, 8) which yields Carrier to indicate the shooter has sunk the Carrier. In general, if the shooter hits the last fragment of the ship, then the result will be the name of the ship. If the player hits a ship fragment, but not the last one, the shot will yield Hit.

The game ends when there are no ships left on the board.

Representation¶

We will represent the board as a list of list of strings. The strings will be one of "Water", 'Battleship', 'Carrier', 'Destroyer', 'Patrol Boat', 'Submarine', and 'Hit'.

Locations will be represent by tuples.

Exercises¶

The Board class encapsulates information about the 10 by 10 board and contains methods for interacting with the board. In these exercises, you will implement the Board class.

Important: The Game class and our tests access attributes and call methods of your Board class. It is important that you use the required names for attributes and methods.

Magic numbers: Near the top of se4.py, you will see the global constant SIZE = 10. You should use this constant in your implementation to avoid the use of the “magic number” 10 throughout your code. We’ve used it in Game, too.

Exercise 1

Implement a Board class with the following attributes:

board (list of list of string): the 10 by 10 board, with all locations initially set to contain “Water”.
num_ships (int): the number of ships currently on the board. This value will be zero initially.

Here’s a sample use of this class:

In [7]: from se4 import Board

In [8]: b1 = Board()

In [9]: len(b1.board) # Number of rows
Out[9]: 10

In [10]: len(b1.board[0]) # Number of columns
Out[10]: 10

In [11]: b1.board
Out[11]:
[['Water',
  'Water',
  'Water',
  'Water',
  'Water',
  'Water',
  'Water',
  'Water',
  'Water',
  'Water'],

  ... eight more rows containing "Water" ...

 ['Water',
  'Water',
  'Water',
  'Water',
  'Water',
  'Water',
  'Water',
  'Water',
  'Water',
  'Water']]

In [12]: b1.num_ships                                                         Out[12]: 0

To run the automated tests for this exercise, run the command:

py.test -xvk constructor

Exercise 2

Implement the __str__ method. This method should return a string representation of the board.

A row should be represented a string that contains the first letter from each of the elements in the row separated by space. For example, a row of all "Water" would be represented with: 'W W W W W W W W W W'. (The string join method will be very useful for this task.)

The rows in turn should be terminated by newlines "\n". The initial board would yield the string: 'W W W W W W W W W W\nW W W W W W W W W W\nW W W W W W W W W W\nW W W W W W W W W W\nW W W W W W W W W W\nW W W W W W W W W W\nW W W W W W W W W W\nW W W W W W W W W W\nW W W W W W W W W W\nW W W W W W W W W W\n'.

Printing this string yields:

W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W W W

To run the automated tests for this exercise, run the command:

py.test -xvk str

Exercise 3

Implement the deploy_fleet method. This method takes a dictionary of that maps ships to locations (as shown above) and adds the ships to the board (replacing the initial "Water" values as needed). It also updates the num_ships attribute to reflect the number of ships now on the board.

In se4.py, we have included a constant SHIP_SIZES that maps a ship ("Carrier", for example) to its width.

You can assume that the input will be valid. The ships used in the input will appear in SHIP_SIZES and the ship will fit in the row starting at the specified location (that is, it won’t run off the end of the board).

Here’s a sample use of this method:

In [19]: b1 = se4.Board()

In [20]: fleet1 = {'Carrier': (0, 4),
                   'Battleship': (1, 0),
                   'Destroyer': (3, 2),
                   'Submarine': (6, 4),
                   'Patrol Boat': (9, 8)},

In [20]: b1.deploy_fleet(fleet1)

In [21]: print(b1)
W W W W C C C C C W
B B B B W W W W W W
W W W W W W W W W W
W W D D D W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W S S S W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W P P


In [22]: b1.num_ships
Out[22]: 5

To run the automated tests for this exercise, run the command:

py.test -xvk deploy

Exercise 4

Implement the method is_game_over that will return True if there are no ships left on the board and False otherwise.

In [19]: b1 = se4.Board()

In [20]: b1.deploy_fleet(fleet1)   # deploy the full fleet

In [23]: b1.is_game_over()
Out[23]: False

In [24]: b2 = Board()         # don't deploy any ships!
In [25]: b2.is_game_over()
Out[25]: True

To run the automated tests for this exercise, run the command:

py.test -xvk over

Exercise 5

Implement the method play_move, which takes a shot location, updates the board, if needed, and returns one of 'Hit', 'Miss', or the name of a ship depending on the success of the shot.

The shot will be a 'Miss' if the location contains "Water" or 'Hit' (from a previously successful shot.) In this case, play_move will just return 'Miss'. It will not update the board.

The shot will be a 'Hit' if it contains a ship fragment. In this case, play_move should update the board to set the location to 'Hit' and check if the cell contained the last piece of the ship. If so, the ship has sunk and play_move should return the name of the ship. If there is cell with the ship’s name remaining in the row, then play_move should return 'Hit'.

Here’s sample use:

In [19]: b1 = se4.Board()

In [20]: b1.deploy_fleet(fleet1)   # deploy the full fleet

In [27]: b1.play_move((9, 7))
Out[27]: 'Miss'

In [42]: b1.play_move((9, 8))
Out[42]: 'Hit'

In [43]: print(b1)
W W W W C C C C C W
B B B B W W W W W W
W W W W W W W W W W
W W D D D W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W S S S W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W H P      ### Notice that location (9, 8) has an H

In [44]: b1.play_move((9, 9))
Out[44]: 'Patrol Boat'

In [45]: print(b1)
W W W W C C C C C W
B B B B W W W W W W
W W W W W W W W W W
W W D D D W W W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W S S S W W W
W W W W W W W W W W
W W W W W W W W W W
W W W W W W W W H H

The first shot lands in water and so, the method returns 'Miss'. The second shot hits a patrol boat, but there are still parts of the patrol boat on the board, so the method updates the board to replace 'Patrol Boat' with 'Hit' and returns 'Hit'. The third shot sinks the boat and, so the method updates the board to replace 'Patrol Boat' with 'Hit' and returns 'Patrol Boat'.

To run the automated tests for this exercise, run the command:

py.test -xvk play

Playing the Game¶

We have included code to allow you to play against the computer. Our code randomly chooses a fleet and configuration for that fleet and then offers you the change to take shots. To run it, run:

python3 se4.py

Please note that this program won’t produce meaningful results until you are passing all the tests.

The program will ask you to enter a move, which you can specify as two integers separated by a single space. For example:

$ python3 se4.py
Ready to play?
Enter your move: 6 5
Miss
Enter your move: 7 4
Hit
Enter your move: 7 3
Hit
Enter your move: 7 2
Miss
Enter your move: 7 5
Destroyer

If you’d like to exit the game, just enter concede instead of a move. By the way, like all good games, our game includes a cheat code that will reveal the board. We encourage you to read through our code to see if you can figure out how to enter the cheat code.

Note

Wondering how we’re able to run a game by running python3 se4.py? Confused about the line if __name__ == "__main__": in our code? Now might be a good moment to read the textbook chapter on the Basics of Code Organization, which explains the difference between importing a Python file and running a Python file.

Submitting your work¶

Once you’ve completed the exercises, you must submit your work through Gradescope (linked from our Canvas site). Gradescope will fetch your files directly from your GitHub repository, so it is important that you remember to commit and push your work!

To submit your work, go to the “Gradescope” section on our Canvas site. Then, click on “Short Exercises #4”. Then, under “Repository”, make sure to select your uchicago-cmsc12100-aut-21/short-exercises-$GITHUB_USERNAME.git repository. Under “Branch”, just select “main”.

Finally, click on “Upload”. An autograder will run, and will report back a score. Please note that this autograder runs the exact same tests (and the exact same grading script) described in Testing Your Code. If there is a discrepancy between the tests when you run them on your computer, and when you submit your code to Gradescope, please let us know.

Your ESNU score on this set of exercises will be determined solely on the basis of these automated tests:

Grade	Percent tests passed
Exemplary	at least 95%
Satisfactory	at least 80%
Needs Improvement	at least 60%
Ungradable	less than 60%

If there is a discrepancy between the tests when you run them on your computer, and when you submit your code to Gradescope, please let us know. Please remember that you can submit as many times as you want before the deadline. We will only look at your last submission, and the number of submissions you make has no bearing on your score.