Question

java programming

1 Solving the Game [30 Marks] The solution developed in assignment 2 was solving the game starting from a board that is completely OFF. We first need to generalize this work and be able to compute the solutions starting from any board positions.

1.1 GameModel The class GameModel is used to capture the current state of the board. Its specification is as follows: • GameModel(int width, int height): the constructor. Creates an all OFF game of width width and of height height. • int getHeight(): getter for height. • int getWidth(): getter for width. • boolean isON(int i, int j): returns true if the location at row i and column j is ON, false otherwise. • reset(): resets the model to all OFF. • set(int i, int j, boolean value): sets the location (i,j) of the model to “value” (be careful, that’s column i and row j). • String toString(): returns a String representation of the model.

1.2 Solution We need to adapt our class Solution to the new configuration. Important: here we want to add to our application, so all of the modifications that we make should not change any of the existing public methods or their behaviour. The new methods of our class are the following ones: • boolean stillPossible(boolean nextValue, GameModel model): this method returns false if the current so- lution would be impossible to finalize into a working solution for a board in the state specified by the GameM- odel instance model, should it be extended from its current state with the value nextvalue. Note that the method returns false if extending the current solution with nextvalue would never yield a working solution, and true otherwise. Returning true does not mean that the solution can necessarily be extended into a working solution. It merely means that we do not yet know if it is still possible. Note as well that this method should not modify the state of the object instance of Solution on which it is called. It does not extend that solution with nextvalue, it simply indicates if such an extension would annihilate its chance of leading to a working solution. • public boolean finish(GameModel model): this method assumes that the solution is currently still extend- able for a board in the state specified by the GameModel instance model, but only one way. It keeps extending that solution with the one correct way that it finds at each step, until the solution is complete and correct for a board in the state specified by the GameModel instance model, or shown to not be work. It returns true if and only if the solution is extended into a complete, working solution That method does change the state of the object instance of Solution on which it is called. If it returns true, then that instance is now a complete, working solution for a board in the state specified by the GameModel instance model • public boolean isSuccessful(GameModel model): this method returns true if the solution is completely specified and is indeed working, that is, if it will bring a board of the specified dimensions from the state specified by the GameModel instance model to being entirely “on”. • int getSize(): returns the “size” of the solution, that is, the number of positions that must be tapped. On an initially OFF 3x2 game, the solution that consists of tapping (1,1) and (3,2) is of size 2, while the solution that consists of tapping (1,1), (2,1), (1,2) and (2,2) is of size 4. . As you implement these new methods, you should avoid code duplication as much as possible in your class, so you may have to do a little bit of refactoring.

1.3 LightsOut Here are the methods to add to the class LightsOut • ArrayList solve(GameModel model): The class method solve finds all the solutions to the Lights Out game for a board in the state specified by the GameModel instance model, using a Breadth-First Search algorithm. It returns an ArrayList containing all the valid solutions to the problem. • Solution solveShortest(GameModel model): The class method solveShortest returns a reference to a mini- mum size solution to the Lights Out game for a board in the state specified by the GameModel instance model. Note that there could be more than one such minimum-size solution. The method can return a reference to any one of them Here as well, we do not want to change any of the existing public methods and behaviour, and you should avoid code duplication as much as possible.

1.4 Queue and a Queue Implementation In assignment 2, our application relied on an interface SolutionQueue, which was a queue specifically meant for instances of Solution. The implementation of that interface was using an ArrayList. We can now replace both interface and implementation with our own code. You need to provide a Queue interface that uses generics, and a queue implementation of your own making, also using generics. Make sure that your application now uses this interface and your implementation. Note that the methods solve of the class LightsOut still returns an instance of “java.util.ArrayList”.

1.5 Testing We provide a class TestQ1 which can help you to ensure that your code is working as expected. A sample run is provided in Appendix A. A Running TestQ1 This is the output of TestQ1 on our own implementation. You run should not generate any failure, obviously. The trace that you get might be different, and the “shortest” solution might be different (but of the same size).

$ java Q1Tests ************************************************************ ** ** ** ** ************************************************************ testSolver 8 Solution found in 0 ms Success! Starting from : [false,false] [false,false] Solution(s) : [[true,true], [true,true]] Solution found in 0 ms Success! Starting from : [false,false] [true,false] Solution(s) : [[false,true], [false,false]] Solution found in 0 ms Success! Starting from : [true,true] [true,true] Solution(s) : [[false,false], [false,false]] Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Success! Starting from : [false,false] [false,false] [false,false] Solution(s) : [[true,true], [true,true], [false,false]] [[true,false], [false,false], [false,true]] [[false,true], [false,false], [true,false]] [[false,false], [true,true], [true,true]] Success! Starting from : [true,false] [false,false] [false,false] Solution(s) : 9 Solution found in 0 ms Success! Starting from : [false,false,false] [false,false,false] [false,false,false] Solution(s) : [[true,false,true], [false,true,false], [true,false,true]] Solution found in 0 ms Success! Starting from : [true,false,false] [false,true,false] [false,false,true] Solution(s) : [[false,false,true], [false,false,false], [true,false,false]] testShortest For model : [false,false] [false,false] Solution found in 0 ms Success. Size found: 4 shortest solution found: [[true,true], [true,true]] For model : [false,false,false] [false,false,false] Solution found in 1 ms Solution found in 1 ms Solution found in 1 ms Solution found in 1 ms Success. Size found: 2 shortest solution found: [[true,false,false], [false,false,true]] For model : [false,false,true] [true,true,false] Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Success. Size found: 2 shortest solution found: [[false,true,false], [false,false,true]] 10 For model : [true,true,false] [true,false,false] Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Success. Size found: 1 shortest solution found: [[false,false,false], [false,false,true]] For model : [false,false,false,false] [false,false,false,false] [false,false,false,false] [false,false,false,false] Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Solution found in 0 ms Success. Size found: 4 shortest solution found: [[false,true,false,false], [false,false,false,true], [true,false,false,false], [false,false,true,false]] testModel Success $

Answer 1

Q1Tests.java

import java.util.ArrayList;

public class Q1Tests {

    private static void runSolverTest(GameModel model, int numberOfSolutions){
        ArrayList<Solution> results = LightsOut.solve(model);
        if(results.size()==numberOfSolutions) {
            System.out.println("Success!");
        } else {
            System.out.println("Failure! Expecting "
                + numberOfSolutions + " and got "
                + results.size());          
        }
        System.out.println("Starting from :");
        System.out.println(model);
        System.out.println("Solution(s) :");
        for(int i =0; i < results.size(); i++){
            System.out.println(results.get(i));          
        }
    }

    private static void testSolver(){

        System.out.println("\ntestSolver");

        GameModel model = new GameModel(2,2);
        runSolverTest(model,1);

        model.set(0,1,true);
        runSolverTest(model,1);

        model.set(0,0,true);
        model.set(1,0,true);
        model.set(1,1,true);
        runSolverTest(model,1);

        model = new GameModel(2,3);
        runSolverTest(model,4);

        model.set(0,0,true);
        runSolverTest(model,0);
     
        model = new GameModel(3,3);
        runSolverTest(model,1);

        model.set(0,0,true);
        model.set(1,1,true);
        model.set(2,2,true);
        runSolverTest(model,1);
   }

    public static void runShortestSolverTest(GameModel model, int size){

        System.out.println("\nFor model :");
        System.out.println(model);
        Solution s = LightsOut.solveShortest(model);
        if(s == null) {
            if(size == 0) {
                System.out.println("Success. No solution found.");
            } else {
                System.out.println("Failure. No solution found. Expected size " + size);
            }
            return;
        }
        else if (s.getSize() != size) {
            System.out.println("Failure. Size found: " + s.getSize()
                + ", expected size: " + size);

        } else {
            System.out.println("Success. Size found: " + size);

        }
        System.out.println("shortest solution found:");
        System.out.println(s);

    }

    private static void testShortest(){
        System.out.println("\ntestShortest");
        GameModel model = new GameModel(2,2);
        System.out.println("Starting test 1");
        runShortestSolverTest(model,4);
        System.out.println("done testshortest1");
      
        model = new GameModel(3,2);
        System.out.println("Starting test 2");
        runShortestSolverTest(model,2);
        System.out.println("done testshortest2");

        model.set(2,0,true);
        model.set(0,1,true);
        model.set(1,1,true);
        System.out.println("Starting test 3");
        runShortestSolverTest(model,2);
        System.out.println("done test 3");

        model.reset();
        model.set(0,0,true);
        model.set(1,0,true);
        model.set(0,1,true);
        runShortestSolverTest(model,1);

        model = new GameModel(4,4);
        runShortestSolverTest(model,4);
    }

    private static void testModel(){
  
        System.out.println("\ntestModel");
        GameModel g = new GameModel(6,3);
        if(g.getWidth() != 6){
            System.out.println("Failure. getWidth should be 6, it is: "
                + g.getWidth());
            return;
        }
        if(g.getHeight() != 3){
            System.out.println("Failure. getHeight should be 3, it is: "
                + g.getHeight());
            return;
        }

        // test default values
        for(int i = 0; i < g.getWidth(); i++) {
            for(int j = 0; j < g.getHeight(); j++) {
                if(g.isON(j,i)) {
                    System.out.println("Failure. default value of g.isON("
                        +j+", "+i+") should be false, it is true");
                    return;                  
                }
            }
        }

        // sets all values to true
        for(int i = 0; i < g.getWidth(); i++) {
            for(int j = 0; j < g.getHeight(); j++) {
                g.set(i,j,true);
            }
        }

        // test result
        for(int i = 0; i < g.getWidth(); i++) {
            for(int j = 0; j < g.getHeight(); j++) {
                if(!g.isON(j,i)) {
                    System.out.println("Failure. Value of g.isON("
                        +j+", "+i+") should be true, it is false");
                    return;                  
                }
            }
        }

        //test reset
        g.reset();
        for(int i = 0; i < g.getWidth(); i++) {
            for(int j = 0; j < g.getHeight(); j++) {
                if(g.isON(j,i)) {
                    System.out.println("Failure. after reset value of g.isON("
                        +j+", "+i+") should be false, it is true");
                    return;                  
                }
            }
        }

        // test setting a single value
        g.set(3,2,true);
        if(!g.isON(2,3)) {
            System.out.println("Failure. g.set(3,2,true), g.isON(2,3) is false. Should be true");
            return;                  
        }
        for(int i = 0; i < g.getWidth(); i++) {
            for(int j = 0; j < g.getHeight(); j++) {
                if((i!=3||j!=2)&& g.isON(j,i)) {
                    System.out.println("Failure. g.isON("
                        +j+", "+i+") should be false, it is true");
                    return;                  
                }
            }
        }
        System.out.println("Success");

    }

    public static void main(String[] args) {
        StudentInfo.display();
        testSolver();
        testShortest();
        testModel();

    }
}

LightsOut.java

import java.util.ArrayList;

public class LightsOut {

    public static final int DEFAULT_WIDTH = 3;
    public static final int DEFAULT_HEIGHT = 3;

    public static ArrayList<Solution> solve(int width, int height){

        Queue<Solution> q = new QueueImplementation<Solution>();
        ArrayList<Solution> solutions = new ArrayList<Solution>();
        Solution a = new Solution(width,height);
        q.enqueue(a);

        long start = System.currentTimeMillis();
        while(!q.isEmpty()){
            Solution s = q.dequeue();
            if(s.isReady()) {
                if(s.isSuccessful()) {
                    System.out.println("Solution found in " + (System.currentTimeMillis()-start) + " ms" );
                    solutions.add(s);
                }
            } else {
                Solution s2 = new Solution(s);
                s.setNext(true);
                q.enqueue(s);
                s2.setNext(false);
                q.enqueue(s2);
            }
        }
        return solutions;
    }
    public static void main(String[] args) {

        int width   = DEFAULT_WIDTH;
        int height = DEFAULT_HEIGHT;

        StudentInfo.display();

        if (args.length == 2) {

            try{
                width = Integer.parseInt(args[0]);
                if(width < 1) {
                    System.out.println("Invalid width, using default...");
                    width   = DEFAULT_WIDTH;
                }
                height = Integer.parseInt(args[1]);
                if(height < 1) {
                    System.out.println("Invalid height, using default...");
                    height = DEFAULT_HEIGHT;
                }
              
            } catch(NumberFormatException e){
                System.out.println("Invalid argument, using default...");
                width   = DEFAULT_WIDTH;
                height = DEFAULT_HEIGHT;
            }
        }
        ArrayList<Solution> results   = solve(width,height);
        for(int i =0; i < results.size(); i++){

            System.out.println("****");
            System.out.println(results.get(i));

        }
        System.out.println("In a board of "+ width + "x" + height +": " + results.size() + " solution" + (results.size() > 1 ? "s." : "."));

    }

    public static ArrayList<Solution> solve(GameModel model){

        // QueueImplementation q = new Queue();
        // ArrayList<Solution> solutions = new ArrayList<Solution>();

        // q.enqueue(new Solution(width,height));
        // long start = System.currentTimeMillis();
        // while(!q.isEmpty()){
        //     Solution s = q.dequeue();
        //     if(s.isReady()) {
        //         if(s.isSuccessful()) {
        //             System.out.println("Solution found in " + (System.currentTimeMillis()-start) + " ms" );
        //             solutions.add(s);
        //         }
        //     } else {
        //         Solution s2 = new Solution(s);
        //         s.setNext(true);
        //         q.enqueue(s);
        //         s2.setNext(false);
        //         q.enqueue(s2);
        //     }
        // }
        // return solutions;

        int height = model.getHeight();
        int width = model.getWidth();

        return solve(width,height);
    }

    static Solution solveShortest(GameModel model){

        int height = model.getHeight();
        int width = model.getWidth();

        ArrayList<Solution> solutions = solve(width,height);

        Solution minimum = solutions.get(0);

        for (int i = 1; i<solutions.size(); i++){

            if (solutions.get(i).getSize()<minimum.getSize()){
                minimum = solutions.get(i);
            }

        }

        return minimum;
      
    }
}

GameModel.java

public class GameModel {

   private int width, height, steps;
   private boolean[][] board;

   public GameModel(int width, int height){
       this.height = height;
       this.width = width;
       board = new boolean[height][width];
   }

   public int getHeight(){
       return this.height;
   }

   public int getWidth(){
       return this.width;
   }

   public boolean isON(int i, int j){
       boolean result = false;

       if (board[i][j] == true){
           result = true;
       }

       return result;
   }

   public void reset(){
       for(int j = 0; j < getHeight(); j++){
           for(int i = 0; i < getWidth(); i++){
               board[j][i] = false;
           }
       }
       this.steps = 0;
   }

   public void set(int i, int j, boolean value){
       board[j][i] = value;
   }

   public String toString(){

        String boardStr = "";
        for (int i = 0; i<height; i++){
           boardStr = boardStr + "[";

           for (int j = 0; j<width; j++){
               boardStr = boardStr + board[i][j];

               if (j != width-1){
                   boardStr = boardStr + ",";
               }
           }

           boardStr = boardStr + "]\n";
        }
        return boardStr;
    }
}

Solution.java

public class Solution {

    private boolean[][] board;

    /**
     * width of the game
     */
    private int width;

    private int height;
  
    private int currentIndex;

    private int row;
    private int col;
    public Solution(int width, int height) {

        this.width = width;
        this.height = height;
        this.row = 0;
        this.col = 0;

        board = new boolean[height][width];
        currentIndex = 0;

    }
     public Solution(Solution other) {

        this.width = other.width;
        this.height = other.height;
        this.currentIndex = other.currentIndex;
        this.col = other.col;
        this.row = other.row;

        board = new boolean[height][width];

        for(int i = 0; i < currentIndex; i++){
            board[i/width][i%width] = other.board[i/width][i%width];
        }

    }

    public boolean equals(Object other){

        if(other == null) {
            return false;
        }
        if(this.getClass() != other.getClass()) {
            return false;
        }

        Solution otherSolution = (Solution) other;

        if(width != otherSolution.width ||
            height != otherSolution.height ||
            currentIndex != otherSolution.currentIndex) {
            return false;
        }

        for(int i = 0; i < height ; i++){
            for(int j = 0; j < width; j++) {
                if(board[i][j] != otherSolution.board[i][j]){
                    return false;
                }
            }
        }

        return true;

    }
    public boolean isReady(){
        return currentIndex == width*height;
    }
    public void setNext(boolean nextValue) {

        if(currentIndex >= width*height) {
            System.out.println("Board already full");
            return;
        }
        board[currentIndex/width][currentIndex%width] = nextValue;
        currentIndex++;
    }
  

    public boolean isSuccessful(){

        if(currentIndex < width*height) {
            System.out.println("Board incomplete");
            return false;
        }

        for(int i=0; i<height; i++){
            for(int j = 0; j < width; j++) {
                if(!oddNeighborhood(i,j)){
                    return false;
                }
            }
        }
        return true;
    }

    public boolean stillPossible(boolean nextValue) {

        if(currentIndex >= width*height) {
            System.out.println("Board already full");
            return false;
        }

        int i = currentIndex/width;
        int j = currentIndex%width;
        boolean before = board[i][j];
        boolean possible = true;

        board[i][j] = nextValue;
      
        if((i > 0) && (!oddNeighborhood(i-1,j))){
            possible = false;
        }
        if(possible && (i == (height-1))) {
            if((j > 0) && (!oddNeighborhood(i,j-1))){
                possible = false;
            }
            if(possible && (j == (width-1))&& (!oddNeighborhood(i,j))){
                possible = false;          
            }
        }
        board[i][j] = before;
        return possible;
    }

    public boolean finish(){

        int i = currentIndex/width;
        int j = currentIndex%width;
      
/*
        if(i == 0 && height > 1) {
            System.out.println("First line incomplete, can't proceed");
            return false;
        }
*/

        while(currentIndex < height*width) {
            if(i < height - 1 ) {
                setNext(!oddNeighborhood(i-1,j));
                i = currentIndex/width;
                j = currentIndex%width;
            } else { //last raw
                if(j == 0){
                    setNext(!oddNeighborhood(i-1,j));
                } else {
                   if((height > 1) && oddNeighborhood(i-1,j) != oddNeighborhood(i,j-1)){
                     return false;
                   }
                   setNext(!oddNeighborhood(i,j-1));
                }
                i = currentIndex/width;
                j = currentIndex%width;
            }
        }
        if(!oddNeighborhood(height-1,width-1)){
            return false;
        }
      
        if(!isSuccessful()) {
            System.out.println("Warning, method called incorrectly");
            return false;
        }
     
        return true;

    }

    private boolean oddNeighborhood(int i, int j) {
      
        int total = 0;
        if(board[i][j]){
            total++;
        }
        if((i > 0) && (board[i-1][j])) {
            total++;
        }
        if((i < height -1 ) && (board[i+1][j])) {
            total++;
        }
        if((j > 0) && (board[i][j-1])) {
            total++;
        }
        if((j < (width - 1)) && (board[i][j+1])) {
            total++;
        }
        return (total%2)== 1 ;              
    }
    public String toString() {
        StringBuffer out = new StringBuffer();
        out.append("[");
        for(int i = 0; i < height; i++){
            out.append("[");
            for(int j = 0; j < width ; j++) {
                if (j>0) {
                    out.append(",");
                }
                out.append(board[i][j]);
            }
            out.append("]"+(i < height -1 ? ",\n" :""));
        }
        out.append("]");
        return out.toString();
    }

    public boolean stillPossible(boolean nextValue, GameModel model){

        board = new boolean[model.getHeight()][model.getWidth()];

        for (int i = 0; i<height; i++){
            for (int j = 0; j<width; j++){

                if (model.isON(i,j) == true){
                    board[i][j] = true;
                }
            }
        }

        return stillPossible(nextValue);
    }

    public boolean finish(GameModel model){

        board = new boolean[model.getHeight()][model.getWidth()];

        for (int i = 0; i<height; i++){
            for (int j = 0; j<width; j++){

                if (model.isON(i,j) == true){
                    board[j][i] = true;
                }
            }
        }
     
       return finish();
    }

    public boolean isSuccesful(GameModel model){
       if(currentIndex < model.getWidth()*model.getHeight()){
            System.out.println("Board incomplete");
            return false;
        }

        for(int i=0; i<model.getHeight(); i++){
            for(int j = 0; j < model.getWidth(); j++) {
                if(!oddNeighborhood(i,j)){
                    return false;
                }
            }
        }
        return true;
    }

    public int getSize(){

        int truCtr = 0;

        for (int i = 0; i<height; i++){
            for (int j = 0; j<width; j++){
                if (board[i][j] == true){
                    truCtr++;
                }
            }
        }
    return truCtr;
    }
}

QueueImplementation.java

public class QueueImplementation<T> implements Queue<T> {

   private static final int MAX_QUEUE_SIZE = 100;
   private T[] q;
   private int front, rear, count;

   @SuppressWarnings("unchecked")
   public QueueImplementation(){
       q = (T[]) new Object[MAX_QUEUE_SIZE];
       front = 0;
       rear = 0; // represents the empty queue
       count = 0;
   }

   @SuppressWarnings("unchecked")
   public QueueImplementation(int size){
       q = (T[]) new Object[size];
       front = 0;
       rear = 0; // represents the empty queue
       count = 0;
   }

   public T dequeue(){
       T item = q[front];
       q[front] = null;
       front = (front+1) % q.length;
       count --;
       return(item);
   }

   @SuppressWarnings("unchecked")
   public void enqueue(T element){
       if(size()<q.length){
           q[rear] = element;
           rear = ( rear+1 ) % q.length;
           count ++;
       }
       else{
           expand();
           enqueue(element);
       }      
      
   }

   @SuppressWarnings("unchecked")
   public void expand(){
       T[] newer = (T[]) new Object[q.length*2];

       for(int i=0; i<count; i++){
           newer[i]=q[front];
           front = (front+1) % q.length;
       front = 0;
       rear = count;
       q = newer;
       }
   }

   @SuppressWarnings("unchecked")
   public boolean isEmpty(){
       return(count == 0);
   }

   @SuppressWarnings("unchecked")
   public T peek(){
       return q[front];  

   }

   @SuppressWarnings("unchecked")
   public int size(){
       return count;
   }

}

Queue.java

public interface Queue<T> {

   T dequeue();

   void enqueue(T element);

   boolean isEmpty();
}

StudentInfo.java

public class StudentInfo {
    public static void display() {

        System.out.println("************************************************************");
        System.out.println("*                                                          *");
        System.out.println("*             Section B              *");
        System.out.println("*          Section B           *");
        System.out.println("*                      Assignment 3                        *");
        System.out.println("*                                                          *");
        System.out.println("************************************************************");
        System.out.println();

    }
}