See attached picture for the question. Below are the requirements for this solut
ID: 3599505 • Letter: S
Question
See attached picture for the question. Below are the requirements for this solution.
Requirements:
In this programming assignment, you will design in Java code the RightMagnetic game. Your solution must use a stack, queue, list or vector.
Your solution takes a starting position of the marker along with the list of squares. Your solution should return true if it is possible to solve the game from the starting configuration and false if it is impossible. Your solution should also work for any size of the game’s row, and a random value in each square. You may assume all the integers in the row are positive except for the last entry, the goal square. At the end of the game, the values of the elements in the list must be the same after calling your solution as they are beforehand, (that is, if you change them during processing, you need to change them back.).
a) Briefly explain the time and space complexity.
b) For the second part of your solution, justify why you choose that particular data structure (e.g. why you choose a stack and not a queue, etc.)
c) Explain how one can detect unsolvable array configurations and whether there exists a way to speed up the execution time.
In this programming part you are asked to implement a game called RightMagnetic Cave RightMagnetic Cave is a 1-player game consisting of a row of squares of any sizes each containing an integer, like this | 16 | 10 | 4 | 6|10| The rules of the game are simple. The circle on the initial square is a marker that can move to other squares along the row. At each step in the game, you may move the marker the number of squares indicated by the integer in the square it currently occupies divided by 2 if the number is even, and moved (n/2+1) if the number is odd. The marker may move either left or right along the row but may not move past either end. For example, the only legal first move is to move the marker four squares (8/2) to the right because there is no room to move four spaces to the left. The goal of the game is to move the marker to the magnetic cave, the "O" at the far end of the row In this configuration, you can solve the game by making the following set of moves: Starting position 8 16 10 4 6 102 12 8 O Step 1 Move right 8 1610 4 6 10 2 12 8 0 Step 2 Move right |16 | 10 | 4 . 6 | 10 | 2 |8Io Step 3 Move left 8 10 4 6 10 212 8 O Step 4 Move right 8 16 10 4 6 10 2 12 8 (O Though the RightMagnetic Cave game is solvable, actually with more than one solution-some configurations of this form may be impossible, such as the following one: 10) 16 46 210 O In this configuration, you will bounce between the two 10's, but you cannot reach any other squareExplanation / Answer
import java.util.*;
//Class definition RightMagneticGame
public class RightMagneticGame
{
// To store size of array
int size;
// Declares an array list
ArrayList<Integer> arr;
// To store path
String path = "";
// Method to create an array
void createArray()
{
// Creates an array list of size entered by the user
arr = new ArrayList<Integer>(size);
// Loops till size -2 times
for(int x = 0; x < size - 1; x++)
{
// Random class object declared
Random rand = new Random();
// Generates a random number and stores it in array
arr.add(rand.nextInt(10) + 1);
}// End of loop
// Stores zero at the end
arr.add(0);
}// End of method
// Method to display the original array
void displayArray()
{
// Loops till size -1 times
for(int x = 0; x < size; x++)
System.out.print(arr.get(x) + " ");
System.out.println();
}// End of method
// Method to play game
boolean playGame()
{
// Stores the initial value
int currentValue = arr.get(0);
// To store number of moves
int move = 0;
// To store current position
int currentPosition = 0;
// Counter for infinite loop initialized to zero
int c = 0;
// Loops till solution or stop if it exceed 100 times
do
{
// Stores the path of move
path += String.valueOf(arr.get(currentPosition)) + ", ";
// Checks if the currentValue is zero then stop solution found
if(currentValue == 0)
break;
// Otherwise check the current value is even
else if(currentValue % 2 == 0)
{
// Calculates the move by dividing the current value by two
move = (currentValue / 2);
// Adds the current value with move value
currentPosition += move;
}// End of else if
// Otherwise current value is odd
else
{
// Calculates the move by dividing the current value by two and add one to it
move = (currentValue/ 2 + 1);
// Adds the current value with move value
currentPosition += move;
}// End of else
// Checks if the current position is greater than size
if(currentPosition > size)
// Reset the current position to move left
currentPosition = (currentPosition - move) - move;
// Extracts the value at current position
currentValue = arr.get(currentPosition);
// Increase the counter for infinite loop
c++;
}while(c < 100);
// Checks if c value is less than 100
if(c < 100)
// Return true for success
return true;
// Otherwise return false for not success
else
return false;
}// End of method
// Main method definition
public static void main(String[] args)
{
// RightMagneticGame class object created
RightMagneticGame rmg = new RightMagneticGame();
// Scanner class object created
Scanner sc = new Scanner(System.in);
// Accepts the size
System.out.println(" Enter the size: ");
rmg.size = sc.nextInt();
// Calls the method to create the array
rmg.createArray();
// Calls the method to display the array
rmg.displayArray();
// Calls the method to start play
// Checks if the return result is true or false
if(rmg.playGame())
System.out.println("Solution found: Path = " + rmg.path);
else
System.out.println("Solution not found");
sc.close();
}// End of main method
}// End of class
Sample Run 1:
Enter the size: 10
1 6 7 7 6 5 6 10 3 0
Solution found:
Path = 1, 6, 6, 10, 7, 6, 0,
Sample Run 2:
Enter the size: 20
3 1 6 3 2 1 9 3 1 8 8 9 7 4 9 4 1 3 1 0
Solution found:
Path = 3, 6, 1, 9, 9, 1, 3, 0,
Sample Run 3:
Enter the size: 20
10 9 5 9 3 7 5 6 7 8 6 8 1 9 7 9 10 1 10 0
Solution not found