There are many applications that involve searching for a solution where there ar
ID: 653227 • Letter: T
Question
There are many applications that involve searching for a solution where there are choices at various steps. At a choice point, you try one of the options. This may lead to another choice where you try one of the options, and so on. But you might eventually reach a dead end in which case, you can back up to the last choice point and try a different option. The next option you try may not lead to a solution either in which case you again need to back up, perhaps to an earlier choice point, and take another option. To handle this, you need to store the untried options so that you can back up and take them. A stack is a perfect data structure for storing these untried options. If you push untried options onto a stack as you go, the top of the stack will always contain the untried option that was most recently encountered. Hence we you reach a dead end, popping the stack will you restore your situation to the most recently encountered untried option
Explanation / Answer
Game class:
package Nim;
import java.util.Scanner;
import java.util.Random;
public class Game {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Random rand = new Random();
System.out.println(welcome());
Pile marbles = new Pile();
Player human = new Player(Player.HUMAN);
Player computer = new Player(Player.COMPUTER);
marbles.setPile();
System.out.println("There are total: " + marbles.getPile()
+ " marbles in the Pile.");
System.out.println("Time for a toin coss to see who goes first!");
System.out.println("Please Select heads(0) or Tails(1): ");
int choice = in.nextInt();
int tossResult = rand.nextInt(2);
boolean playerTurn = false;
boolean computerTurn = false;
if (choice == tossResult) {
System.out.println("You have won the Coin Toss! You will go first!");
human.updateTurn(0);
playerTurn = true;
}
else {
System.out.println("Computer has won the coin toss! Computer will go first");
computer.updateTurn(1);
computerTurn = true;
}
while (marbles.getPile() > 0 && marbles.hasStick()) {
while (playerTurn) {
int removeMarbles = human.makeMove(marbles.getPile());
marbles.reducePile(removeMarbles);
computerTurn = true;
playerTurn = false;
}
while (computerTurn) {
int removeMarbles = computer.makeMove(marbles.getPile());
marbles.reducePile(removeMarbles);
playerTurn = true;
computerTurn = false;
}
}
}
private static String welcome() {
return "Welcome to the Game of Nim";
}
}
player class
package Nim;
import java.util.Scanner;
import java.util.Random;
public class Player {
public static final int HUMAN = 0;
public static final int COMPUTER = 1;
private int type;
public Player(int theType) {
type = theType;
}
Scanner in = new Scanner(System.in);
// n is number of marbles left in the pile
public int makeMove(int n) {
int max = n / 2;
int grab;
if (type == HUMAN) {
System.out.println("There are " + n
+ " marbles in total. However you can only"
+ "grab no more than " + max + " marbles");
System.out.println("Please Enter the number of marbles to grab: ");
grab = in.nextInt();
while (grab > max || grab < 0) {
System.out.println("You have entered a illelgal value. Please enter a legal value: ");
grab = in.nextInt();
}
return grab;
}
else {
Random rand = new Random();
grab = (rand.nextInt(n / 2 - 1) + 1);
System.out.println("Computer has grabbed: " + grab + " marbles");
return grab;
}
}
public void updateTurn(int n) {
type = n;
}
}
pile class
:
package Nim;
import java.util.Random;
public class Pile {
private int initialSize;
public Pile() {
}
Random rand = new Random();
public void setPile() {
initialSize = (rand.nextInt(100 - 10) + 10);
}
public void reducePile(int x) {
initialSize = initialSize - x;
}
public int getPile() {
return initialSize;
}
public boolean hasStick() {
if (initialSize > 0) {
return true;
}
else {
return false;
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.