[SOLVED] haskell代写：COMP1100 Assignment 1 – Battleship Game

Assignment 1 – Battleship Game

COMP1100 2017 Semester 2 11 August 2017

DUE DATE AND TIME: Monday Week 6 (August 28), 9am sharp. No late submissions will be accepted.

Start working on the assigment as soon as possible. The completion may require several sessions of work.

Note: The Assignment 1 webpage always contains the most recent version of the assignment. We advise you to open/refresh this page every time you recommence working on the assignment. In case of changes and corrections in the assignment, we will make an announcement in piazza. Make sure you check piazza regularly.

Last updated at 19 August 2017, 05:13 PM

1

Academic Integrity

Do not plagiarise.

Do not show your code to anyone. Do not view anybody else’s code.
Do not share your code.
Do not copy anybody else’s code.
Do not read anybody else’s report. Do not show your report to anybody.

You are required to sign a Pledge of Academic Integrity and return it to us no later than 11:00PM on 20 August 2017. Your tutors will provide you with this document in Lab 4 and collect the signed pledge during the same lab. If you are unable to attend your lab during Week 4, you are required to sign and send it back to your tutor via email with the same deadline applying.

If you do not sign and submit the pledge of academic integrity, your assignment will not be assessed and will attract a zero mark.

2

Introduction

Battleship is a two-player move-based guessing game. The version that we are going to use is the 1990 Milton Bradley version. Each player has a 10×10 board, and starts by putting their “ships” around the board. The ships are always 1 cell wide, but vary in length. Note that the ship configurations might be different in different versions of the game.

Traditionally the game is played with pen-and-paper. Each player has a large “primary” grid, on which they place their own ships and mark them if they have been hit, and a “tracking” grid, on which they mark a hit/miss to record what they have

tried to hit on the other person’s grid.

Nowadays, with the introduction of computers and internet, the game is more popular in its online form. If you are interested, you can try an online version of the game here (https://battleship-game.org/en/). Keep in mind that the ship configuration of the online game is different from ours. However, the mechanics and the rules are very similar.

Skills Needed

Below are the essentials skills you need to complete this assignment:

• Built-in functions from basic Haskell libraries • Conditional Programming
• Recursion
• List Operation

• Git Operations
• Professional Report Writing

3

Game Rules

Ship Placement

1. There are 5 different ships on the grid: Carrier, Battleship, Submarine, Cruiser, and Destroyer.
2. No ship may overlap another.
3. Ships cannot be directly adjacent to each other. There must be a gap of size of

   at least 1 cell between ships.

4. All ships must be present on the map.

Gameplay

1. Player enters a coordinate to bomb.
2. If the target coordinate is a hit, the move counter stays unchanged, and the

   cell is marked as “Hit”.

3. If the target coordinate is a miss, the move counter increases by one, and the

   cell is marked as “Miss”.

4. If the target coordinate has already been checked, the move counter increases

   by one, and everything else remains unchanged.

5. Game is won when all ships are sunk (a ship is defined as sunk when all of its

   parts have been hit).

6. Game is lost when the move counter reaches 20 (>= 20).

4

Framework

We have provided a basic framework for you to work upon. You can find most of it in the file Battleship.hs which contains the Battleship module.

Boards

There are two grids defined in this module:

type Board = Matrix Cell type Ships = Matrix Bool

The type Board refers to the “tracking” grid. Cell can be one of three values, which are also defined in the same file.

The type Ships refers to the “primary” grid, on which your ships are placed. If there is a ship present, the cell should have the value True, otherwise False.

The grids are designed with a matrix as their underlying data structure. The top left corner cell of the grid has coordinate (0, 0). The bottom left corner cell has the coordinate (0, 9). The bottom right corner cell of the grid has the coordinate (9, 9).

Ships

The ships have already been defined in the framework:

data ShipType = Carrier | Battleship | Submarine | Cruiser | Destroyer The dimension of the ships are as follows:

• Carrier-1×5
• Battleship – 1 x 4 • Cruiser-1×3
• Submarine – 1 x 3 • Destroyer – 1 x 2

Each ship can face one of four directions:

data Direction = Up | Down | Left | Right

However, the directions are only used while generating the Ships grid. Once the ships have been placed on the grid, the direction does not matter. What this means is, a destroyer at (0, 0) extending down occupies the cells (0, 0) and (0, 1). This configuration is identical to a destroyer at (0, 1) extending up, therefore also occupying the cells (0, 0) and (0, 1).

5

State & GenShips

Since pure Haskell is free from side effects, we need to utilise a custom type State in order to store the current Board, the placement of the Ships, the Condition of the gameplay (Won/Lost/Playing), and the number of moves. A state is passed around every time there is a transition. State is defined as follows:

data Condition = Won | Lost | Playing data State = State {board :: Board, ships :: Ships,

condition :: Condition,numMoves:: Integer}

Since Haskell does not have mutable variables, every time you want to change something, you will need to create a new instance of it. For example, if you want to increase the numMoves counter by one in a state, leaving everything else constant, you can define a function such as the following:

oneMoreMove :: State -> StateoneMoreMove (State b s c m) = State b s c (m + 1)

The framework contains a grid of type Ships that is a matrix of booleans and a record data type GenShips useful for generating the ships grid. GenShips contains a grid of type Ships, a list of ships that are already on the grid, and a boolean to indicate if the grid has been completely generated.

type ShipsOnGrid = [ShipType]
data GenShips = GenShips {gsShips :: Ships,

existingShips :: ShipsOnGrid, finished :: Bool} deriving (Show)

In the Main.hs file, we have created a random number generator for you, which generates a random coordinate, a random type of ship, and a random direction. It feeds these data into your placeShip function. We have provided you with the validPlacement function, which should be used in your placeShip function, to check if the new ship can be placed on the grid. If the placement is valid, the ship is placed on the grid.

Every time you place a ship, you should create a new grid of type Ships. When all the ships are present on the ships grid, simply change the boolean inside GenShips to True. Then the random generator will stop feeding more data and will go to the next stage, which is to play the game.

6

Tasks

We have modularised the assignment for you into two parts. Part A requires you to generate the grid for playing the game, and part B requires you to implement the game mechanics so that the game can be played. All you need to edit is Battleship.hs file. Feel free to look at Main.hs, if you are interested in how the backend works.

Preliminaries

There should be a nice way to show the board. We have already made a start in the function showBoard, which takes a board and converts it to a string. This string can be printed out nicely onto the screen. You can use the following function to print out the board:

putStrLn (showBoard board)
where board is of type Board. Your job is to finish the local function cStateToCell,

which should return a space if the Cell is Unchecked, a o for Hit, and a x for Miss. You should also complete the shipLength function, as well as the coordInBound

function that returns True, if a given coordinate is inside our map. Part A – Board Generation

Side-effect free means that a random number generator is impossible to implement in pure Haskell. We have utilised the IO type in the Main.hs file in order to take care of randomness generation. You can assume that the random numbers generated are uniformly random.

This function recurses and keeps feeding random data into your placeShip function until the boolean inside the type GenShips is set to True, at which point it stops. You should implement the placeShip function.

If all ships have been placed, you should return the type GenShips with the boolean set to True. By the end, the function feeds the newly generated grid into your transitionState function and starts the game with the new Ships grid.

7

Part B – Gameplay

We have designed the framework such that after the Ships grid is generated, the program will ask the user to input a coordinate to target. After pressing <Enter>, the coordinate and the current state are passed into the function transitionState. You need to complete the function transitionState.

The transition process can be described as below:

1. If the condition of the state is Won or Lost, return the original state unchanged.
2. If the move counter is equal to 20, change the condition to Lost, and return

   the new state.

3. If the target coordinate is outside of the coordinate range, e.g. (10, 10), return

   the original state unchanged.

4. If the target coordinate has a ship present:

   • Mark the coordinate as Hit
   • If all ships are sunk, change the Condition to Won, and return the new

   state.
   • If there are still remaining ships, return the new state.

5. If the target coordinate does not have a ship present:
   • Mark the coordinate as Miss
   • Increase the moves counter by one, and return the new state.

8

Technical Tips

Once you have Haskell and doctest installed on your computer, this assignment should require no external libraries that need to be manually installed. Therefore, technically you should be able to complete this assignment with a text editor and a bare-bone Haskell installation. However, we encourage you to use IntelliJ to manage your projects. Here are some instructional steps that you can take to get started.

IntelliJ – New Project

1. Open IntelliJ
2. Top left corner -> File -> New -> Project
3. Select Haskell on the left, and click Next
4. Select “Build with cabal”, and click Next
5. Deselect initialise cabal package (This step is crucial.) 6. Give your project a name (e.g. comp1100-ass01)

Git – Fork the repository

1. GotoCOMP1100’sGitLabRepository(https://gitlab.cecs.anu.edu.au/comp1100/ass01.git)
2. Click on “Fork”, and select your user.
3. Give your tutor Reporter access to your new repository.
4. Go to IntelliJ terminal.
5. Initialise the folder as a git repository (Make sure you are in the project you created earlier. Likely in ~/IdeaProjects/comp1100-ass01)
6. Add your assignment 1 repository as the origin
7. Add comp1100 assignment 1 repository as the upstream
8. Pull the origin remote to your local computer

Running the program

On all platforms, type in the following in the Terminal:

ghc Main.hs -O2 -Wall -o Battleship
This will compile the game, and generate an executable, called Battleship. If you

want to run the game, on Linux/Mac systems, simply type in:

./Battleship

On Windows, just type in:

Battleship.exe

9

This will start the program. It will ask you to choose from one of three modes: f mode generates the Ships grid and starts the game using your functions; g mode generates the Ships grid and prints it to the Terminal; and p mode enables you to enter a pre-defined Ships grid configuration. Examples of grid configurations can be found in the folder named “Grids”.

Note that backspace does not work under GHCi. Technical Problems

There is no doubt that you will run into technical problems while writing your code. When you are faced with an error, it is easy to get frustrated, but it is important to calm down. Sometimes keep trying might not be the best solution. Here are some of the things you can do to keep your mind of the problem for a while:

• Go for a walk
• Watch a movie
• Get some food
• Play with your pet • Have a nap

Read the error messages and try to figure out what they mean. Try to fix them yourself, and if you still have not fixed them the second day, post them on Piazza with what you have tried, what you think is wrong, so what others can help you more effectively.

Note: If you are posting code on Piazza, make sure the visibility is set to “Private” so that only instructors can see it.

10

Hints

If after looking at the code you have absolutely no idea where to start, below are some hints for you. Feel free to skip this section entirely, if you already know what to do.

At the heart of this assignment is the management a state that consists of several components. Below we look at each one of them individually.

Board

The first component of a state is a board, which is defined as below:

data Board = Matrix Cell data Matrix a = [Row a] data Row a = [a]

From these three lines we can deduce that type Board is represented as [[Cell]]. The game should start with a list of size 10 of a list of size 10 of Unchecked :: Cell. As the game plays, the coordinates that are targeted will be turned into either a Hit or a Miss. This data structure is probably better represented if printed out as a 2D structure. For demonstration purposes, we use U to denote Unchecked, H to denote Hit, and M to denote Miss:

[ [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U],

]

If, for example, the target is (4, 0), and there is no ship underneath that cell in the corresponding coordinate on the Ships grid, the board will turn into:

11

[ [U, U, U, U, M, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U], [U, U, U, U, U, U, U, U, U, U],

]

In order to achieve this, it might be useful to look at the function updateList :: [a] -> Int -> a -> [a], which takes in an original list, the index at which the old element will be replaced by a new one, the new element, and returns a new list. For example:

> updateList ['a', 'b', 'c', 'd', 'e'] 3 'i'['a', 'b', 'c', 'i', 'e']

Using this function, you may find creating another function updateGrid :: Matrix a -> Coordinate -> a -> Matrix a useful when you are trying to update specific cells to a new value (such as a cell to Hit/Miss, or a cell to True/False when generating the ships grid).

Ships

Type Ships is a matrix, as type Board, but it is a matrix of booleans instead of a matrix of cells. This means each element can be either True, which means there is a ship occupying that cell, or False if not. Your updateList function might be of use in this data structure as well.

When reading data from a matrix (which you have to do to check if there is an underlying ship or not in a certain coordinate of the Ships grid), you might find the function (!!) useful. An example usage of this function is:

> ['a', 'b', 'c', 'd', 'e'] !! 2'c'

Condition & Move Counter

Condition is a very simple sum type that can be one of three values. The move counter is used to keep track of the number of moves already made in the game.

12

Board Generation

This section focuses on Part A of your assignment, which is to generate a valid Battleship board. We have already provided you with a hint in the Battleship.hs file – function validPlacement. This function checks the validity of the placement of the new ship (with its own coordinate, direction, and type). The first thing it needs to check is whether the ship would be placed inside the grid. For example, if the following happens:

> validPlacement someState (0, 8) Left Cruiser

no matter what someState is, the function should always return False when the ship goes out of grid bounds. In the example above, if the ship is placed, it would occupy the coordinates (0, 8), (-1, 8), (-2, 8). Therefore, it would go beyond the left barrier.

The order in which the ship placement rules are checked does not matter. However, your program may run faster or slower depending on the order.

GenShips

As discussed at the start of the specification, we have defined the GenShips type and have partially written the validPlacement function. This function returns True if the given inputs comply with all of the rules of ship placement. Feel free to utilise this function if you would like, but you do not have to. In fact, we encourage you to come up with your own ways to check the validity of the placement.

Let’s go through this function:

not (s `elem` (existingShips board))
This checks if there is already a ship of the input type that exists on the map, as

there should only be one of each type of ship on the map and no more.

all coordInBound onCoords

This checks if all the coordinates that the ship were to occupy, if placed on the board, are within the boundary. If a ship occupies (0, 0), (0, -1), (0, -2), then it should not be allowed to be placed on the board as it extends beyond the bounds of the board which is from (0, 0) to (9, 9).

all (x -> not $ isShipAtCoord x (gsShips gs) $filter coordInBound $ nub $ concatMap getNeighbours onCoords)

This is the most complicated part of the function, both in terms of comprehension and computation. This code checks if all of the cells occupied by the proposed ship as well as all the cells that are directly adjacent to the proposed ship are all False. This means there is no ships overlapping or right next to it. Take some time to understand this code.

13

Report

For this assignment, we require you to write a professional technical report. It is an essential part of the assignment, and as such, it is a hurdle for this assignment.

A technical report is a tool for you to communicate effectively with your clients (which in this case are your tutors) by demonstrating your understanding of the

problem and providing the description of your solution.
The report should be in PDF format, located at the root of your assignment repository

and named Report.pdf. Otherwise, it may not be marked.
The report should have a title page with the following items * your name * your

university id * collaborators, if any

You can discuss conceptual ideas of the assignment with others. Mention them as collaborators in your title page.

What should be in it?

Before starting your report, you should consider who the audience is. If it were for people who are not familiar with programming, it would not have to be very technical and a very descriptive language could be used. However, it is for your tutors and the lecturer, who are proficient at programming and understand the concept of recursion, list operations, and other programming concepts. Therefore, describing how recursion works in your report is not a great idea, for example.

After reading a technical report, the reader should be comprehensively aware of what problem the program is trying to solve, the reasons for major design choices in the program, as well as how it was tested. Below is a list of questions that could be discussed in your report:

• What are the objectives of your functions?
• What were the conceptual or technical issues that you encountered whilst doing

  the assignment, and how did you get past them?

• What were the assumptions that you had to make during the assignment?
• What would you have done differently if you were to do it again?
• What are the major design choices you have made in your program?
• Why have you made those choices?
• How would you make your program better?
• How did you test your program? What were the results?
• Which parts of your program can be confusing for the reader? Explain them if

  so.

• How fast is your program? What makes it fast/slow?

  14

What should NOT be in it?

You absolutely should not copy any content of anyone’s report from anywhere. This is absolutely non-negotiable. Your report should be your own content written by yourself alone.

You should avoid having grammatical errors or misspellings in your report. Check your report for lexical errors (you can use spell check tools) and proof-read it before submission.

Do not use informal language in the report. This includes unnecessary abbreviations (atm, btw, ps, etc.), emojis and emoticons.

Any diagrams, graphs or charts must be relevant. Any unnecessary graphs will distract the readers from the actual content.

How long should it be?

Your report should be as long as it needs to be whilst being succinct yet descriptive. In other words, if you submit a 7000 word report on this assignment, unless you have done something that is completely new and revolutionary, you probably were not succinct enough. On the other hand, if your report is only 500 words, you probably were not descriptive enough.

The report should convey all that the readers who are familiar with programming and Haskell need to know about your work. There should not be any further clarifications required after reading the report.

15

What should it look like?

You do not need to follow any specific styling guide (such as APA or Harvard).

Colours should be kept minimal. If graphs are necessary, make sure they are vector graphics as your report might be marked on different resolution/size of screens. A stretched out, pixelated graph is very unappealing.

You can use word processors, such as as Microsoft Word and Apple Pages for writing your report. We will be glad to see a report written in LaTeX, if you know how to produce LaTeX documents.

Below is a list of requirements that you should follow:

• Any code that appears in your document should have a fixed-width font (such as Consolas, or Courier New, Lucida Console and Monaco).
• Any other text should be set in serif-fonts. Popular choices are Palatino, Sabon, Minion and Caslon.
• When available, automatic ligatures should be activated.
• Do not use underscore to highlight your text.
• Texts should be at least 1.5 spaced.
• Paragraphs should be justified with automatic hyphenation.

16

Marks

This assignment is non-redeemable and worth 10% of your total marks. It is marked out of 100 with your report as the hurdle. The marks distribution is as follows:

• code – 70 marks • testing – 10 marks • report – 20 marks

If you do not have a report, your maximum mark will be capped at 49.

The following provides a rough guide of your marks based on your progress in the assignment. However, the actual decision of your mark may deviate from the description below.

Fail

Under any of the conditions listed below, your assignment will be automatically marked as failure.

• There is no report submitted. • Part B is not functional.
• The code does not compile.

This is an incomplete list. Other reasons for failure are possible.

Pass

The code compiles, and the game is playable given a pre-generated board. The random board generation is not functional. Code submitted is of basic quality. The discussions in the report are mediocre and demonstrate basic understanding of the problem and solution.

Credit

The code compiles, and the random board generation is able to generate a valid board which complies with all the rules of the ship placement. The game is playable. Code submitted is of good quality. The discussion in the report is sufficient but not comprehensive, and demonstrates good understanding of the problem and solution. Both source file and the report contain records of testing procedures and results. There is some discussion of the speed and efficiency of your program.

17

Distinction

The code should compile (with -Wall flag) without any warnings. Both random board generation and game play should be functional and comply with all rules of the game. Winning/Losing state should be achievable at the correct stage of the game. The functions are well tested and there are some good doctest examples in your code that are discussed in the report. Code submitted is of great quality with explanatory comments in the source file. The report is of great quality, and includes sufficient details to convey in detail and depth your understanding of the assignment. There is some discussion of the speed and efficiency of your program.

High Distinction

The code should compile (with -Wall flag) without any warnings. Both random board generation and game play should be functional and comply with all rules of the game. Winning/Losing state should be achievable at the correct time, and any further input should not modify the stare. In other words, the game should be complete and functional. Code submitted is of excellent quality with appropriate comments in the source file. The functions are comprehensively tested and the test cases (doctest) are well designed in the source code (e.g. essential edge cases are considered), and thoroughly discussed in the report. There are also tests which involve quickCheck. The report is of excellent quality, and includes sufficient details to illustrate your understanding of the assignment. There is in-depth discussion of the speed and efficiency of your program.

18

Comms

Do not post your code publicly, either on Piazza or via other forums. If by mistake you post your code publicly on Piazza, an email containing your post with your code will be sent to all students. This means that others will have access to your code and you may be held responsible for plagiarism.

Once again, and we cannot stress this enough: do not post your code publicly. If you need help with your code, post it privately to the instructors.

When brainstorming with your friends, do not show your code to them. There might be some pressure from your friends and even some judgements that you are not sharing the code, but it is for both your and their benefits. Anything that constitutes as plagiarism will be dealt with extremely seriously and you can end up being expelled from the university if you do so.

Sharing ideas is perfectly fine, but the sharing should stop at ideas.
Tutors and the lecturer will not look at your assignment code unless it is posted

privately in piazza.
Tutors and the lecturer will only give assistance by directing you to relevant exercises

from the labs, or definitions and examples from the lectures.

Before the assignment is due, tutors and the lecturer will not give individual tips how to write functions for the assignment or suggestions how your code can be improved. You will receive their feedback when the mark is released.

19

Submission Checklist

Preferably 24 hours prior to the due time of the assignment (Monday week 6, 9am), you should make sure that:

• you have fully read and understand the meaning of the pledge of academic integrity.
• you have fully read and understand the entire specification of the assignment
• your work is pushed to GitLab and your repository is shared with your tutor

  with Reporter permission.
  – Do not email your tutor to ask if they can see your repository. If you can

  see it on GitLab, and it is shared with your tutor (which you can check through Settings -> Members) with Reporter access, they will be able to see it.

• the relevant Pipeline tests are passed. If you have only completed the random board generation or the playing mode, some tests will fail. However, tests that are related to your completed work should pass.
• your program works on the lab machines – if the program does not work on the lab machines, it might fail the tests
• the report is in PDF format, located at the root of your assignment repository and named Report.pdf. Otherwise, it may not be marked.

20

Written by Steven X. Han with assistance from Katya

21