Assignment 4 Graphs Solution

Assignment 4

2 Introduction
There are two exercises in this assignment. Be very careful about what files you submit on myCourses and where you upload them. You will be less constrained for this assignment than for the previous ones. For many of the questions, there are more than one solution possible. You can write as many auxiliary methods as you want. However, you are not allowed to import any additional code (and you don’t need it anyways). The testers you are provided with are very partial. We have said it for every assignment, but let us repeat it for this one too : you need to expand this tester. Each question has a weight associated to it. This is only to serve as an indicator and may be later changed without notice.
3 Exercise 1 : Graphs (28 points)
3.1 Structure of the code provided to you
A Graph has a number of nodes nbNodes and is characterized by its adjacency matrix adjacency. adjacency[i][j] states whether or not there is an edge from the i-th node to the j-th node. The Graphs you will be dealing with are undirected, i.e. adjacency[i][j] == adjacency[j][i] is always true. They may contain self-loops and they may be non-connected.
3.2 Questions
Question 1. (2 points each) Code addEdge and removeEdge. It takes as input a pair of nodes and adds / removes the edge between the i-th and the j-th nodes.
Question 2. (4 points) Code nbEdges. g.nbEdges() returns the number of edges of g.
Question 3. (10 points) Code cycle. It takes as input an integer, g.cycle(i) returns true if the i-th node is part of a cycle (and false otherwise).
Question 4. (10 points) Code shortestPath. It takes as input a pair of integers, g.shortestPath(i,j) returns the length of the shortest path joining the i-th node to the j-h node. If there is no such path, it returns g.nbNodes +1.
3
4 Exercise 2 : Connect 4 (72 points)
I hope you have learnt things that are of interest to you during this class and in particular throughout the assignments. We are going to finish this final assignment by a small game that I used to play a lot with my sister when we were younger : Connect 4 (Puissance 4 pour les francophones). For those of you who don’t know about this game, I refer you to the wikipedia page for more details but let me sum up how the game works : you have a vertical grid that is 7-cell-long and 6-cell-high. Each player has some disks of a specific color (yellow for one player, red for the other one). At each round, the player whose turn it is picks a column and puts a disk in that column. The disk falls to the lowest available cell. After one player has played, it is the other player’s turn. The game can end in two cases. First, if one player has won, i.e. he is the first one to have four disks of his colour aligned (either horizontally, vertically or diagonally). Second, if there is no space left in the grid, in which case there is no winner.
4.1 Structure of the code that is provided to you
You have two classes provided to you : Configuration and Game. The class Configuration corresponds to the grid. It has three fields. First board is the grid per say. It is initiated in the constructor to an array int[7][6] (containing only 0’s by default). The field available is an array int[7] such that available[i] is the first available row in the i-th column. If the i-th column is already full, its value is 6. Finally the field spaceLeft is true if you still have some place somewhere on the grid to put a disk. The class Configuration already has a method print() coded for you. It prints the grid, the disks that are contained in it and the number of the columns. For instance, it could print :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | +---+---+---+---+---+---+---+ | | | | | | | | | | | | | | | | | | | | | 1 | | | | | | | 1 | 2 | | | | | | 1 | 2 | 1 | | | | 1 | 2 | 2 | 2 | 1 | 1 | 2 |
The row at the bottom is the 0-th row. So for instance the disk of the 2nd player in the 6th column corresponds to board[6][0] and the disks of the
4
1st player that are in column 4 correspond to board[4][0], board[4][1] and board[4][3]. The class Game corresponds to the game per say. It does not have any fields. You will have several methods to code in it. However, you are already provided with the method play that you can use at the end. At the end of the tester, there are two lines that are commented. Once you have finished coding every methods, you can uncomment these two lines, these will allow you to play against the computer. It is a very good way of testing further your code.
4.2 Questions in Configuration
Question 5. (8 points) First code addDisk in Configuration. As the name suggests, c.addDisk(5,1) adds a disk corresponding to player 1 in the column 5 and at the first row available. addDisk takes as input the number of the column in which to add a disk and the number of the player whose disk is to be added. Here you can assume that the column has space left. For instance, the grid showed in previous subsection would be updated to
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | +---+---+---+---+---+---+---+ | | | | | | | | | | | | | | | | | | | | | 1 | | | | | | | 1 | 2 | | | | | | 1 | 2 | 1 | 1 | | | 1 | 2 | 2 | 2 | 1 | 1 | 2 |
Don’t forget to update the other fields.
Question 6. (16 points) You can now code isWinning. It takes as argument the last column that was played and the player who played last (so you know that the disk that is last in that column belongs to said player) and it returns true if, and only if, the player managed to make a line of four disk in the last round. The line can be horizontal, vertical or diagonal. For example, consider a configuration c with the following board :
5
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | +---+---+---+---+---+---+---+ | | | | | | | | | | | | | | | | | | | | | 1 | 2 | | | | | | 1 | 2 | 1 | | | | | 1 | 2 | 1 | 1 | | | 1 | 2 | 2 | 2 | 1 | 1 | 2 |
c.isWinning(5,2) should return true, but c.isWinning(3,1) should return false.
Question 7. (8 points) Code canWinNextRound. It takes as argument the player p whose turn it is and returns i such that if player p places its disk in column i, he wins the game. If there are no such column, i is equal to -1. If there are two such columns, it returns the smallest one. For example, consider a configuration c with the following board :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | +---+---+---+---+---+---+---+ | | | | | | | | | | | | | | | | | | | | | 1 | | | | | | | 1 | 2 | 2 | | | | | 1 | 2 | 1 | 1 | | | 1 | 2 | 2 | 2 | 1 | 1 | 2 |
c.canWinNextRound(2) should return 5 but c.canWinNextRound(1) should return -1.
Question 8. (16 points) Code canWinTwoTurns. It takes as argument the player p whose turn it is and returns i such that if player p places its disk in column i, whatever the other player does on next round, player p can win when it’s his turn again. Note that this requires that the other player does not win in between. You can assume here that player p has no winning move at this turn. For instance, consider a configuration c with the following board :
6
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | +---+---+---+---+---+---+---+ | | | | | | | | | | | | | | | | | 2 | | 2 | 2 | | | | | 1 | | 1 | 2 | | | | | 1 | | 2 | 1 | 1 | | | | 1 | 1 | 2 | 2 | 1 | | |
c.canWinTwoTurns(1) should return -1 because player 1 has no way of making sure he is going to win in two rounds. c.canWinTwoTurns(2) should return 1 because if player 2 plays column 1, then there are two cases : either player 1 plays also in column 1 in which case by playing (again) in column 1, player 2 will complete a horizontal line, or player 1 does not play in column 1, in which case player 2 can play again in column 1 and complete a diagonal line.
4.3 Questions in Game
Question 9. (10 points) Code getNextMove. This method asks in which column the player wants to add his disk. It takes as argument a BufferedReader (where the player is writing his answer), a Configuration (the grid on which the player is playing) and an integer (the number of the player whose turn it is). You are allowed to print whatever you want on the screen (the grid, a warning if the other player has a winning move that should be prevented etc). But what is important is that if the player asks for a column with no space left, you should keep asking him until he gives a valid one. Consider a configuration c with the following board :
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | +---+---+---+---+---+---+---+ | | | | 1 | 2 | | | | | | 1 | 2 | 1 | 1 | | | | | 2 | 2 | 1 | 1 | 2 | | | | 1 | 1 | 2 | 2 | 1 | | | | 2 | 2 | 1 | 1 | 2 | | | | 1 | 2 | 2 | 1 | 2 |
Consider a BufferedReader keyboard, then getNextMove(keyboard, c, 2) should ask player 2 for his move. If player 2 requests column 3, you should ask again. If player 2 then requests column 4, ask again. If player 2 then
7
requests column 3 (again), ask (again). If then player 2 requests column 2, return 2. To test it, you should uncomment the corresponding lines in the tester.
Question 10. (14 points) Code movePlayer1. Player 1 is played by the computer. It takes as input an integer which is the column that the other player played last and a Configuration which is the current state of the grid. Here is the strategy that the player 1 is following :
1. if player 1 has a winning move, he plays that winning move.
2. if player 1 has a move that can make him win in two rounds, he plays that move.
3. if none of these are possible, player 1 tries to put his disk right above the one player 2 played last (call it last). If there is no more space left in column last, he tries the column on the left (last -1), then on the right (last +1). If that is still not possible, he plays the columns last -2 then last +2 etc. Player 1 skips every step that would correspond to a non-existing column. For instance, if last = 5, he would try the columns in the following order : 5, 4, 6, 3, 2, 1, 0.
You have just coded an AI ! It is not a very clever AI, but it is one nonetheless. You can now play against this AI \o/
8