Question

Some two-player games are played with a pile of pebbles. The first player can take a certain number of pebbles that depends on the current number of pebbles, leaving a smaller number of pebbles. The permissible moves depend on the game rules. Then the second player takes a turn, and again the first, until one of them is unable to make another legal move and loses.

The Game interface below describes the game rules-the number of pebbles that are permitted after making a legal move from a given number of pebbles.
A common game of this type is called Nim. A player must take at least one pebble and can take at most half of the pebbles. The NimGame class below provides the game rules for this game. The TwoThreeGame class provides rules for a different game. As long as there are at least four pebbles, a player can take two or three of them.
A position (that is, a given number of pebbles) is winning if it isn't an immediate loss, and at least one of the moves yields a losing position for the other player.
A position is losing if it is an immediate loss, or all of the moves lead to a winning position for the other player.
In the Nim game, it happens that positions of the form 2k−1 are losing positions, and all others are winning positions.
Implement the mutually recursive methods isWinningPosition and isLosingPosition.
The nextPositions method of the Game interface returns the positions that result from legal moves.
import java.util.Scanner;
public class Games
{
public static boolean isWinningPosition(int n, Game g)
{
int[] positions = g.nextPositions(n);
if (positions.length == 0) /* Your code goes here */
for (int i : positions)
{
/* Your code goes here */
}
/* Your code goes here */
}public static boolean isLosingPosition(int n, Game g)
{
int[] positions = g.nextPositions(n);
if (positions.length == 0) /* Your code goes here */
for (int i : g.nextPositions(n))
{
/* Your code goes here */
}
/* Your code goes here */

}

public static void main (String [] args)
{
Scanner in = new Scanner(System.in);
String gameType = in.nextLine();
String positionType = in.nextLine();
int n = in.nextInt();
if (gameType.equals("NimGame"))
{
if(positionType.equals("isWinningPosition"))
{
System.out.println(isWinningPosition(n, new NimGame()));
}
else // isLosingPosition
{
System.out.println(isLosingPosition(n, new NimGame()));
}
}
else //TwoThreeGame
{
if(positionType.equals("isWinningPosition")) // isWinningPosition
{
System.out.println(isWinningPosition(n, new TwoThreeGame()));
}
else // isLosingPosition
{
System.out.println(isLosingPosition(n, new TwoThreeGame()));
}
}
}
}
____
public interface Game {
int[] nextPositions(int n);
}
-------
public class NimGame implements Game {
public int[] nextPositions(int n) {
int[] result = new int[n / 2];
for (int i = 0; i < result.length; i++)
result[i] = n - i - 1;return result;
}
}
--------
public class TwoThreeGame implements Game {
public int[] nextPositions(int n) {
if (n >= 4)
return new int[] { n - 3, n - 2 };
else
return new int[] {};
}
}

Answer 1

The isWinningPosition method checks if a position in a game is a winning position by checking if it is of the form 2k-1. The isLosingPosition method checks if a position is a losing position by checking if it is of the form 2k-1. Both methods iterate through the next positions and use recursion to determine if they are winning or losing positions.

Step-by-step explanation:

The isWinningPosition method checks if a position in a game is a winning position. In the Nim game, positions of the form 2k-1 are losing positions, while all others are winning positions. To implement this method, you can check if the given position is of the form 2k-1. If it is, return false since it is a losing position. Otherwise, iterate through all the next positions and check if any of them are losing positions by calling the isLosingPosition method recursively. If at least one of the next positions is a losing position, then the current position is a winning position. Return true in this case.

The isLosingPosition method checks if a position in a game is a losing position. In the Nim game, positions of the form 2k-1 are losing positions, and all others are winning positions. To implement this method, you can check if the given position is of the form 2k-1. If it is, return true since it is a losing position. Otherwise, iterate through all the next positions and check if all of them are winning positions by calling the isWinningPosition method recursively. If all of the next positions are winning positions, then the current position is a losing position. Return true in this case.

Here is an example implementation of the isWinningPosition and isLosingPosition methods:

public static boolean isWinningPosition(int n, Game g) {
int[] positions = g.nextPositions(n);
if (positions.length == 0)
return false;
for (int i : positions) {
if (!isLosingPosition(i, g))
return true;
}
return false;
}

public static boolean isLosingPosition(int n, Game g) {
int[] positions = g.nextPositions(n);
if (positions.length == 0)
return true;
for (int i : positions) {
if (isWinningPosition(i, g))
return false;
}
return true;
}