URGENT: I need help with this!!!!! Thank you so much!!!!!!!!!! So this is an ass
ID: 3703385 • Letter: U
Question
URGENT: I need help with this!!!!! Thank you so much!!!!!!!!!! So this is an assignment that is due next week with two packages and ten questions in it.
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.
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 nish this nal 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 specic 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 rst 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 elds. 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 eld available is an array int[7] such that available[i] is the rst available row in the i-th column. If the i-th column is already full, its value is 6. Finally the eld 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 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 nished 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 Conguration
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 rst 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 |
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 conguration c with the following board :
| 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 conguration 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 conguration c with the following board :
| 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 conguration 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 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/.
package assignment4Graph;
public class Graph {
boolean[][] adjacency;
int nbNodes;
public Graph (int nb){
this.nbNodes = nb;
this.adjacency = new boolean [nb][nb];
for (int i = 0; i < nb; i++){
for (int j = 0; j < nb; j++){
this.adjacency[i][j] = false;
}
}
}
public void addEdge (int i, int j){
// ADD YOUR CODE HERE
}
public void removeEdge (int i, int j){
// ADD YOUR CODE HERE
}
public int nbEdges(){
// ADD YOUR CODE HERE
return 0; // DON'T FORGET TO CHANGE THE RETURN
}
public boolean cycle(int start){
// ADD YOUR CODE HERE
return false; // DON'T FORGET TO CHANGE THE RETURN
}
public int shortestPath(int start, int end){
// ADD YOUR CODE HERE
return 0; // DON'T FORGET TO CHANGE THE RETURN
}
}
package assignment4Graph;
public class Tester {
public static void main(String[] args) {
// TODO Auto-generated method stub
Graph g1 = new Graph(6);
// TEST ADDEDGE
g1.addEdge(0, 1);
g1.addEdge(1, 2);
g1.addEdge(1, 3);
g1.addEdge(2, 3);
g1.addEdge(2, 4);
g1.addEdge(3, 4);
if (g1.adjacency[2][3] && ! g1.adjacency[2][5]){
System.out.println("addEdge seems to work, test it further though, this is testing only 1/18 of a single example !");
}
else{
System.out.println("addEdge does not work.");
}
// TEST REMOVEEDGE
Graph g2 = new Graph(6);
g2.adjacency = new boolean[][]{new boolean[]{false, true, false, false, false, true},
new boolean[]{true, false, true, true, false, false},
new boolean[]{false, true, false, true, true, true},
new boolean[]{false, true, true, false, true, false},
new boolean[]{false, false, true, true, false, false},
new boolean[]{true, false, true, false, false, false}};
g2.removeEdge(0, 5);
g2.removeEdge(2, 5);
boolean areEqual = true;
for (int i = 0; i< 6; i++){
for (int j = 0; j < 6; j++){
areEqual = areEqual && (g1.adjacency[i][j] == g2.adjacency[i][j]);
}
}
if (areEqual){
System.out.println("removeEdge seems to work, test it further though.");
}
else{
System.out.println("removeEdge does not work.");
}
// TEST NBEDGES
g1.adjacency = new boolean[][]{new boolean[]{false, true, false, false, false, false},
new boolean[]{true, false, true, true, false, false},
new boolean[]{false, true, false, true, true, false},
new boolean[]{false, true, true, false, true, false},
new boolean[]{false, false, true, true, false, false},
new boolean[]{false, false, false, false, false, false}};
if (g1.nbEdges() == 6){
System.out.println("nbEdges seems to work, test it further though.");
}
else{
System.out.println("nbEdges does not work.");
}
// TEST CYCLE
if (!g1.cycle(0) && g1.cycle(2)){
System.out.println("cycle seems to work, test it further though.");
}
else{
System.out.println("cycle does not work.");
}
// TEST SHORTESTPATH
if (g1.shortestPath(0, 4) == 3 && g1.shortestPath(0, 5) == 7 && g1.shortestPath(2, 4) == 1){
System.out.println("shortestPath seems to work, test it further though.");
}
else{
System.out.println("shortestPath does not work.");
}
}
}
package assignment4Game;
public class Configuration {
public int[][] board;
public int[] available;
boolean spaceLeft;
public Configuration(){
board = new int[7][6];
available = new int[7];
spaceLeft = true;
}
public void print(){
System.out.println("| 0 | 1 | 2 | 3 | 4 | 5 | 6 |");
System.out.println("+---+---+---+---+---+---+---+");
for (int i = 0; i < 6; i++){
System.out.print("|");
for (int j = 0; j < 7; j++){
if (board[j][5-i] == 0){
System.out.print(" |");
}
else{
System.out.print(" "+ board[j][5-i]+" |");
}
}
System.out.println();
}
}
public void addDisk (int index, int player){
// ADD YOUR CODE HERE
}
public boolean isWinning (int lastColumnPlayed, int player){
// ADD YOUR CODE HERE
return false; // DON'T FORGET TO CHANGE THE RETURN
}
public int canWinNextRound (int player){
// ADD YOUR CODE HERE
return 0; // DON'T FORGET TO CHANGE THE RETURN
}
public int canWinTwoTurns (int player){
// ADD YOUR CODE HERE
return 0; // DON'T FORGET TO CHANGE THE RETURN
}
}
package assignment4Game;
import java.io.*;
public class Game {
public static int play(InputStreamReader input){
BufferedReader keyboard = new BufferedReader(input);
Configuration c = new Configuration();
int columnPlayed = 3; int player;
// first move for player 1 (played by computer) : in the middle of the grid
c.addDisk(firstMovePlayer1(), 1);
int nbTurn = 1;
while (nbTurn < 42){ // maximum of turns allowed by the size of the grid
player = nbTurn %2 + 1;
if (player == 2){
columnPlayed = getNextMove(keyboard, c, 2);
}
if (player == 1){
columnPlayed = movePlayer1(columnPlayed, c);
}
System.out.println(columnPlayed);
c.addDisk(columnPlayed, player);
if (c.isWinning(columnPlayed, player)){
c.print();
System.out.println("Congrats to player " + player + " !");
return(player);
}
nbTurn++;
}
return -1;
}
public static int getNextMove(BufferedReader keyboard, Configuration c, int player){
// ADD YOUR CODE HERE
return 0; // DON'T FORGET TO CHANGE THE RETURN
}
public static int firstMovePlayer1 (){
return 3;
}
public static int movePlayer1 (int columnPlayed2, Configuration c){
// ADD YOUR CODE HERE
return 0; // DON'T FORGET TO CHANGE THE RETURN
}
}
package assignment4Game;
import java.io.*;
public class Tester {
public static void main(String[] args) {
// TEST ADD DISK
Configuration c = new Configuration();
c.addDisk(0, 2);
c.addDisk(3, 1);
c.addDisk(1, 1);
c.addDisk(2, 1);
c.addDisk(3, 1);
c.addDisk(3, 2);
c.addDisk(3, 1);
boolean correct = (c.board[0][0] == 2) && (c.board[1][0] == 1) && (c.board[2][0] == 1)
&& (c.board[3][0] == 1) &&(c.board[3][1] == 1)&& (c.board[3][3] == 1)&& (c.board[3][2] == 2);
for (int i = 0; i < 7; i++){
correct = correct && c.available[i] < 6;
}
if (correct && c.spaceLeft){
System.out.println("addDisk seems to work, test it further though.");
}
else{
System.out.println("addDisk does not work.");
}
// TEST IS WINNING
Configuration c2 = new Configuration();
c2.board[0][0] = 2; c2.board[1][0] = 1; c2.board[2][0] = 1; c2.board[3][0] = 1;
c2.board[3][1] = 1; c2.board[3][3] = 1; c2.board[3][2] = 2;
c2.available[0] = 1; c2.available[1] = 1; c2.available[2] = 1; c2.available[3] = 4;
correct = ! c2.isWinning(2, 1);
c2.board[4][0] = 1; c2.available[4] = 1;
correct = correct && c2.isWinning(4, 1);
if (correct){
System.out.println("isWinning seems to work, test it further though.");
}
else{
System.out.println("isWinning does not work.");
}
// TEST CAN WIN NEXT ROUND
c2.board[4][0] = 0; c2.available[4] = 0;
correct = c2.canWinNextRound(1) == 4;
c2.board[4][0] = 2; c2.available[4] = 1;
correct = correct && c2.canWinNextRound(1) == -1;
if (correct){
System.out.println("canWinNextRound seems to work, test it further though.");
}
else{
System.out.println("canWinNextRound does not work.");
}
// TEST CAN WIN TWO TURNS
c2.board[0][3] = 1; c2.board[0][2] = 1; c2.board[0][1] = 2; c2.available[0] = 4;
c2.board[2][3] = 1; c2.board[2][2] = 2; c2.board[2][1] = 1; c2.available[2] = 4;
correct = c2.canWinTwoTurns(1) == 1 && c2.canWinTwoTurns(2) == -1;
if (correct){
System.out.println("canWinInTwoTurns seems to work, test it further though.");
}
else{
System.out.println("canWinInTwoTurns does not work.");
}
// TESTING GET NEXT MOVE
// you have to uncomment what comes next when you test this method
// you probably want to comment it again once you are done, otherwise you will be asked each time
c2.board[0][4] = 1; c2.board[0][5] = 2; c2.available[0] = 6;
c2.board[2][4] = 1; c2.board[2][5] = 2; c2.available[2] = 6;
/*int result = -1;
try{
InputStreamReader input = new InputStreamReader(System.in);
BufferedReader keyboard = new BufferedReader(input);
result = Game.getNextMove(keyboard, c2, 1);
keyboard.close();
}
catch(Throwable e){
System.out.println("something somewhere went horribly wrong");
}
System.out.println("does it return what you requested ? " + result);*/
// TESTING MOVE PLAYER 1
c2.board[1][1] = 2; c2.available[1]= 2;
correct = Game.movePlayer1(2, c2) == 1;
c2.board[1][1] = 0; c2.available[1]= 1;
correct = correct && Game.movePlayer1(2, c2) == 1;
c2.board[0][3] = 2;
correct = correct && Game.movePlayer1(2, c2) == 1;
correct = correct && Game.movePlayer1(0, c2) == 1;
c2.board[3][4] = 2; c2.board[3][5] = 2; c2.available[3]= 6;
correct = correct && Game.movePlayer1(3, c2) == 4;
if (correct){
System.out.println("movePlayer1 seems to work, you can now uncomment the last two lines of the tester and play against your AI !");
}
else{
System.out.println("movePlayer1 does not work.");
}
// When you want to play the game, uncomment the two lines down this comment
/*InputStreamReader input2 = new InputStreamReader(System.in);
System.out.println(Game.play(input2));*/
}
}
Explanation / Answer
Ans1. public void addEdge(int i,int j)
{
if(i>nbNodes)
{
System.out.println("source node: not exist");
}
if(j>nbNodes)
{
System.out.println(" destination node: not exist");
}
adjacency[i][j]=adjacency[j][i]=1;
}
public void removeEdge(int i,int j) {
if(i>nbNodes||j>nbNodes||adjacency[i][j]==0||adjacency[j][i]==0)
System.out.println("Edge :not exist");
adjacency[i][j]=adjacency[j][i]=0;
}
Ans2. public int nbEdges(){
int sum=0;
for(i=0;i<nbNodes;i++)
sum+=adjacency.length;
return sum/2;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.