(5/5)

The objective of this assignment is to practice (1) defining functions (being a callee) and (2) calling functions (being a caller). You will write a program to play a paper-and-pencil game called Dots and Triangles.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

Dots and Triangles

Introduction

The objective of this assignment is to practice (1) defining functions (being a callee) and (2) calling functions (being a caller). You will write a program to play a paper-and-pencil game called Dots and Triangles. Starting with an empty triangular grid of dots, two players take turns adding one line between two un-joined adjacent dots. A player who completes the third side of a triangle owns that triangle, earns one point, and takes an extra turn. A player will not get a third consecutive turn even if (s)he makes triangle(s) in the extra turn. The game ends when the grid is full, and the player with more points wins. It is a draw if two players have the same points. The triangular grid, when full, consists of six triangles. Figure 1 shows an example grid. We use the symbol o to denote a dot, the symbols ---, /, and \ to denote the lines in three directions, and numbers 1 and 2 inside a completed triangle to denote the player who owns it. In the figure, two triangles are already formed in the lower level (assumed to be both by Player 2).

Figure 1: An Example Dots and Triangles Configuration

Program Specification

This section describes the requirements, program design, function decomposition, game flow, etc.

Basic Requirements

You cannot declare any global variables (variables declared outside any functions). You cannot use any functions in the library. You cannot use any arrays in your code.

Grid Representation

There are 12 possible positions that we can place a line in a triangular grid. Therefore, we use integers 1–12 to denote these positions, as illustrated in Figure 2. The positions are basically ordered top-to-bottom, left-to-right.

3 1 4

o---o

2 /

6 o---o o 7

8 \2/2\ Player 1 score: 0

9 o---o Player 2 score: 2

12 10 11

Figure 2: Numbers for Line Positions

To encode the whole grid and the players’ scores in a game, we use an 18-digit integer

𝑑1𝑑2𝑑3𝑑4𝑑5𝑑6𝑑7𝑑8𝑑9𝑑10𝑑11𝑑12𝑑13𝑑14𝑑15𝑑16𝑑17𝑑18. The first 12 digits 𝑑1 … 𝑑12 are either 0 or 1, denoting whether the corresponding positions 1 to 12 are empty or filled. The next six digits

𝑑13𝑑14𝑑15𝑑16𝑑17𝑑18 denote the six triangles in the grid. Digits 𝑑13𝑑14𝑑15 are the upper three triangles left-to-right. Digits 𝑑16𝑑17𝑑18 are the lower triangles left-to-right. The digits’ values are 0–2, where 0 means the triangle is not completed, and 1 or 2 mean a completed triangle with the player who owns it. For example, the grid in Figure 1 can be encoded by the integer 110001011101000220. Using this representation, an empty grid (with no lines filled) is simply encoded as the integer 000000000000000000. (Note: in C++, integer constants should NOT contain leading zeroes, otherwise, they will be treated as octal numbers. Therefore, an empty grid is specified as 0 only in C++.) As another example, 111111111111222111 represents a full grid where each player owns three triangles, and thus a draw game.

The data type int in C++ is typically 32-bit and thus not big enough to store an 18-digit integer. In your program, you have to use a bigger integer type called long long. In Visual Studio, long long is a 64-bit signed integer type, whose range is -9,223,372,036,854,775,808 … 9,223,372,036,854,775,807.

Provided and Required Functions

Your program must contain the following functions. Some of them are written for you already (Provided) and you should not modify their contents. The others will be written by you (Required). These functions must be called somewhere in your program. You must not modify the prototypes of all these functions. You can design extra functions if you find necessary.

In the functions below, you can assume that (a) parameter grid is always a proper encoding of a triangular grid; (b) the parameter pos is always 1–12; and (c) the parameter p is always 1 or 2.

void printGrid(long long grid)

(Provided) This function prints grid to the screen using the format in Figure 1.

bool isFilled(long long grid, int pos)

(Provided) Returns true if position pos of grid is filled with a line; returns false otherwise.

int playerScore(long long grid, int p)

(Required) Returns the score of Player p in grid. This is done by counting how many triangles Player

p owns in grid.

void updateGrid(long long &grid, int pos, int p)

(Required) This function updates the pos^th digit of the reference parameter grid to 1, modeling the game play of Player p putting a line in position pos in grid. Moreover, if any new triangles are completed, the digit of the corresponding triangle in grid shall be marked as Player p. The other digits of grid remain unchanged. The following shows some sample function calls and the expected results.

grid	pos	p	Value of grid after calling updateGrid(grid, pos, p)
110001011101000220	3	1	111001011101100220 (one new triangle completed)
100000001001000000	10	2	100000001101000020 (one new triangle completed)
0	8	1	10000000000 (no new triangle completed)

At the end of this function, the value of grid becomes the new grid configuration after a player move. Note that putting one line can complete at most two triangles. You do not have to check in this function whether the player move is valid or not. (You check validity elsewhere. See step 3 of the next section.) To check if a new triangle is formed, calling the isFilled(…) function is useful.

Program Flow

The program flow of the game is described as follows. You should call the functions above to aid your implementation. All user inputs mentioned below are assumed to be always integers.

The program starts the game with an empty grid, and Player 1 takes the first
Prompt the current player to enter a position to put a line
In case the player makes an invalid input (outside the range 1–12 or the input position was already filled), display a warning message and go back to step 2.
Update the grid by putting a line in the position, and mark any possible completed
If the current player has completed triangle(s) and this turn is not his/her second consecutive turn, keep him/her the current player. Otherwise, swap the other player to become the current player. (Recall that a player cannot have three consecutive )
Repeat steps 2 to 5 until the grid is full. (That is, until game is )
Once the grid is full, determine the winner or a draw and display the message “Player 1 wins!”, “Player 2 wins!”, or “Draw game!”

Sample Run

In the following sample run, the blue text is user input and the other text is the program printout. You can try the provided sample program for other input. Your program output should be exactly the same as the sample program (same text, symbols, letter case, spacings, etc.). Note that there is a space after ‘:’ in the printout.

o o o o o	Player 1 score:	0
o o	Player 2 score:	0
Player 1's	turn (1-12): 2↵
o o
/
o o o
	Player 1 score:	0
o o	Player 2 score:	0
Player 2's	turn (1-12): 11↵
o o
/ o o o / Player 1 score: 0 o o Player 2 score: 0 Player 1's turn (1-12): 0↵ Invalid move! Try again. Player 1's turn (1-12): -3↵ Invalid move! Try again.

Player 1's turn (1-12): 12↵ o o

o o o

Player 1 score:

o---o

Player 2's

Player 2 score:

turn (1-12): 20↵

Invalid move! Try again.

Player 2's turn (1-12): 2↵ Invalid move! Try again.

Player 2's turn (1-12): 5↵ o o

/ \

o o o

Player 1 score:

o---o

Player 1's

Player 2 score:

turn (1-12): 1↵

o---o

/ \

o o o

/ Player 1 score: 0

o---o Player 2 score: 0 Player 2's turn (1-12): 9↵

o---o

/ \

o o o

/ / Player 1 score: 0

o---o Player 2 score: 0 Player 1's turn (1-12): 10↵

o---o

/ \

o o o

/1\ / Player 1 score: 1

o---o Player 2 score: 0 Player 1's turn (1-12): 7↵

o---o

/ \

o o---o

/1\1/

Player 1 score:

o---o

Player 2's o---o

/ /2\

o o---o

/1\1/

Player 2 score:

turn (1-12): 4↵

Player 1 score:

o---o

Player 2's o---o

/ \2/2\ o o---o

/1\1/

Player 2 score:

turn (1-12): 3↵

Player 1 score:

o---o

Player 1's

Player 2 score:

turn (1-12): 6↵

Submission and Marking

Your program file name should be cpp. Submit the file in Blackboard (https://elearn.cuhk.edu.hk/).
Insert your name, student ID, and e-mail as comments at the beginning of your source
You can submit your assignment multiple times. Only the latest submission
Your program should be free of compilation errors and warnings.
Your program should include suitable comments as documentation.
Do NOT plagiarize. Sending your work to others is subjected to the same penalty as the

(5/5)

Use CA10RAM to get 10%* Discount.

The objective of this assignment is to practice (1) defining functions (being a callee) and (2) calling functions (being a caller). You will write a program to play a paper-and-pencil game called Dots and Triangles.

ANSWER ALL QUESTIONS

Dots and Triangles

Introduction

Program Specification

Basic Requirements

Grid Representation