Question

Java: Complete the methods marked TODO. Will rate your answer!

--------------------------------------------------------------------------------------------------

package search;

import java.util.ArrayList;
import java.util.List;

/**
* An abstraction over the idea of a search.
*
* @author liberato
*
* @param <T> : generic type.
*/
public abstract class Searcher<T> {
protected final SearchProblem<T> searchProblem;
protected final List<T> visited;
protected List<T> solution;

/**
   * Instantiates a searcher.
   *
   * @param searchProblem
   *            the search problem for which this searcher will find and
   *            validate solutions
   */
public Searcher(SearchProblem<T> searchProblem) {
    this.searchProblem = searchProblem;
    this.visited = new ArrayList<T>();
}

/**
   * Finds and return a solution to the problem, consisting of a list of
   * states.
   * The list should start with the initial state of the underlying problem.
   * Then, it should have one or more additional states. Each state should be
   * a successor of its predecessor. The last state should be a goal state of
   * the underlying problem.
   * If there is no solution, then this method should return an empty list.
   *
   * @return a solution to the problem (or an empty list)
   */
public abstract List<T> findSolution();

/**
   * Checks that a solution is valid.
   * A valid solution consists of a list of states. The list should start with
   * the initial state of the underlying problem. Then, it should have one or
   * more additional states. Each state should be a successor of its
   * predecessor. The last state should be a goal state of the underlying
   * problem.
   *
   * @param solution : solution
   * @return true iff this solution is a valid solution
   * @throws NullPointerException
   *             if solution is null
   */
public final boolean isValidSolution(List<T> solution) {
        // TODO
        return false;
}
}

--------------------------------------------------------------------------------------------------------

package search;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
* An implementation of a Searcher that performs an iterative search,
* storing the list of next states in a Stack. This results in a
* depth-first search.
*
*/
public class StackBasedDepthFirstSearcher<T> extends Searcher<T> {

/**
   * StackBasedDepthFirstSearcher.
   * @param searchProblem : search problem
   */
public StackBasedDepthFirstSearcher(SearchProblem<T> searchProblem) {
    super(searchProblem);
}

@Override
public List<T> findSolution() {
    // TODO
    return null;
}
}

----------------------------------------------------------------------------------------------------

package search;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
* An implementation of a Searcher that performs an iterative search,
* storing the list of next states in a Queue. This results in a
* breadth-first search.
*
*/
public class QueueBasedBreadthFirstSearcher<T> extends Searcher<T> {

/**
   * QueueBasedBreadthFirstSearcher.
   * @param searchProblem : search problem
   */
public QueueBasedBreadthFirstSearcher(SearchProblem<T> searchProblem) {
    super(searchProblem);
}

@Override
public List<T> findSolution() {
    // TODO
    return null;
}
}

---------------------------------------------------------------------------------

package mazes;

import java.util.List;

import search.Solver;

public class MazeDriver {

/**
   * Supproting main method.
   */
public static void main(String[] args) {
    MazeGenerator mg = new MazeGenerator(24, 8, 0);
    Maze m = mg.generateDFS();
    System.out.println(m.toString());
    Solver<Cell> s = new Solver<Cell>(m);
    List<Cell> r = s.solveWithRecursiveDFS();
    for (Cell cell : r) {
      System.out.println(cell);
    }
    System.out.println(r.size());
    // System.out.println("--------");
    // List<Cell> d = s.solveWithIterativeDFS();
    // for (Cell cell : d) {
    //    System.out.println(cell);
    // }
    // System.out.println(d.size());
    // System.out.println("--------");
    // List<Cell> q = s.solveWithBFS();
    // for (Cell cell : q) {
    //    System.out.println(cell);
    // }
    // System.out.println(q.size());
}
}

------------------------------------------------------------------------------------------------------------------

package puzzle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import search.SearchProblem;
import search.Solver;

/**
* A class to represent an instance of the eight-puzzle.
* The spaces in an 8-puzzle are indexed as follows:
* 0 | 1 | 2
* --+---+---
* 3 | 4 | 5
* --+---+---
* 6 | 7 | 8
* The puzzle contains the eight numbers 1-8, and an empty space.
* If we represent the empty space as 0, then the puzzle is solved
* when the values in the puzzle are as follows:
* 1 | 2 | 3
* --+---+---
* 4 | 5 | 6
* --+---+---
* 7 | 8 | 0
* That is, when the space at index 0 contains value 1, the space
* at index 1 contains value 2, and so on.
* From any given state, you can swap the empty space with a space
* adjacent to it (that is, above, below, left, or right of it,
* without wrapping around).
* For example, if the empty space is at index 2, you may swap
* it with the value at index 1 or 5, but not any other index.
* Only half of all possible puzzle states are solvable! See:
* https://en.wikipedia.org/wiki/15_puzzle
* for details.
*

* @author liberato
*
*/
public class EightPuzzle implements SearchProblem<List<Integer>> {

/**
   * Creates a new instance of the 8 puzzle with the given starting values.
   * The values are indexed as described above, and should contain exactly the
   * nine integers from 0 to 8.
   *
   * @param startingValues
   *            the starting values, 0 -- 8
   * @throws IllegalArgumentException
   *             if startingValues is invalid
   */
public EightPuzzle(List<Integer> startingValues) {
}

@Override
public List<Integer> getInitialState() {
    // TODO
    return null;
}

@Override
public List<List<Integer>> getSuccessors(List<Integer> currentState) {
    // TODO
    return null;
}

@Override
public boolean isGoal(List<Integer> state) {
    // TODO
    return false;
}

/**
   * supporting man method.
   */
public static void main(String[] args) {
    EightPuzzle e = new EightPuzzle(Arrays.asList(new Integer[] { 1, 2, 3,
        4, 0, 6, 7, 5, 8 }));

    List<List<Integer>> r = new Solver<List<Integer>>(e).solveWithBFS();
    for (List<Integer> l : r) {
      System.out.println(l);
    }
}
}

Answer 1

Code Implemented in Java

Note: Comments are written for code explanation

Code:

Filename: Searcher.java

package search;

import java.util.ArrayList;
import java.util.List;

/**
* An abstraction over the idea of a search.
*
* @author liberato
*
* @param <T>
*/
public abstract class Searcher<T> {
   protected final SearchProblem<T> searchProblem;
   protected final List<T> visited;
   protected List<T> solution;

   /**
   * Instantiates a searcher.
   *
   * @param searchProblem
   * the search problem for which this searcher will find and
   * validate solutions
   */
   public Searcher(SearchProblem<T> searchProblem) {
       this.searchProblem = searchProblem;
       this.visited = new ArrayList<T>();
   }

   /**
   * Finds and return a solution to the problem, consisting of a list of
   * states.
   *
   * The list should start with the initial state of the underlying problem.
   * Then, it should have one or more additional states. Each state should be
   * a successor of its predecessor. The last state should be a goal state of
   * the underlying problem.
   *
   * If there is no solution, then this method should return an empty list.
   *
   * @return a solution to the problem (or an empty list)
   */
   public abstract List<T> findSolution();

   /**
   * Checks that a solution is valid.
   *
   * A valid solution consists of a list of states. The list should start with
   * the initial state of the underlying problem. Then, it should have one or
   * more additional states. Each state should be a successor of its
   * predecessor. The last state should be a goal state of the underlying
   * problem.
   *
   * @param solution
   * @return true iff this solution is a valid solution
   * @throws NullPointerException
   * if solution is null
   */
   public final boolean isValidSolution(List<T> solution) throws NullPointerException {
if (solution == null) throw new NullPointerException();
if (solution.isEmpty()) return false;
       if (!searchProblem.getInitialState().equals(solution.get(0))) return false;
for (int i = 1; i < solution.size(); i++)
   if (!searchProblem.getSuccessors(solution.get(i)).contains(solution.get(i-1))) return false;
return searchProblem.isGoal(solution.get(solution.size()-1));
   }
}

Filename: StackBasedDepthFirstSearcher.java

package search;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
* An implementation of a Searcher that performs an iterative search,
* storing the list of next states in a Stack. This results in a
* depth-first search.
*
*/
public class StackBasedDepthFirstSearcher<T> extends Searcher<T> {
  
   public StackBasedDepthFirstSearcher(SearchProblem<T> searchProblem) {
       super(searchProblem);
   }

   @Override
   public List<T> findSolution() {
       Stack<T> stack = new Stack<T>();
       stack.push(searchProblem.getInitialState());
       visited.add(searchProblem.getInitialState());
       T t = null;
       while (!stack.isEmpty()) {
           t = getNextUnvisitedNeighbor(stack.peek());
           if (searchProblem.isGoal(t)){
               stack.push(t);
               return stack;
           }
           if (t == null) stack.pop();
           else {
               visited.add(t);
               stack.push(t);
           }
       }
       return stack;
   }

   private T getNextUnvisitedNeighbor(T t) {
       for (T node : searchProblem.getSuccessors(t)) {
           if (!visited.contains(node)) {
               return node;
           }
       }
       return null;
   }
}

Filename: MazeDriver.cpp

package mazes;

import java.util.List;

import search.Solver;

public class MazeDriver {
   public static void main(String[] args) {
       MazeGenerator mg = new MazeGenerator(24, 8, 0);
       Maze m = mg.generateDFS();
       System.out.println(m.toString());
       Solver<Cell> s = new Solver<Cell>(m);
       List<Cell> r = s.solveWithBFS();
       for (Cell cell : r) {
           System.out.println(cell);
       }
       System.out.println(r.size());
//       System.out.println("--------");
//       List<Cell> d = s.solveWithIterativeDFS();
//       for (Cell cell : d) {
//           System.out.println(cell);
//       }
//       System.out.println(d.size());
//       System.out.println("--------");
//       List<Cell> q = s.solveWithBFS();
//       for (Cell cell : q) {
//           System.out.println(cell);
//       }
//       System.out.println(q.size());
   }
}

Filename : EightPuzzle.java

package puzzle;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import search.SearchProblem;
import search.Solver;

/**
* A class to represent an instance of the eight-puzzle.
*
* The spaces in an 8-puzzle are indexed as follows:
*
* 0 | 1 | 2
* --+---+---
* 3 | 4 | 5
* --+---+---
* 6 | 7 | 8
*
* The puzzle contains the eight numbers 1-8, and an empty space.
* If we represent the empty space as 0, then the puzzle is solved
* when the values in the puzzle are as follows:
*
* 1 | 2 | 3
* --+---+---
* 4 | 5 | 6
* --+---+---
* 7 | 8 | 0
*
* That is, when the space at index 0 contains value 1, the space
* at index 1 contains value 2, and so on.
*
* From any given state, you can swap the empty space with a space
* adjacent to it (that is, above, below, left, or right of it,
* without wrapping around).
*
* For example, if the empty space is at index 2, you may swap
* it with the value at index 1 or 5, but not any other index.
*
* Only half of all possible puzzle states are solvable! See:
* for details.
*

* @author liberato
*
*/
public class EightPuzzle implements SearchProblem<List<Integer>> {

   /**
   * Creates a new instance of the 8 puzzle with the given starting values.
   *
   * The values are indexed as described above, and should contain exactly the
   * nine integers from 0 to 8.
   *
   * @param startingValues
   * the starting values, 0 -- 8
   * @throws IllegalArgumentException
   * if startingValues is invalid
   */

   private final List<Integer> startingValues;
   private final List<Integer> goal = Arrays.asList(1, 2, 3,
                                                   4, 5, 6,
                                                   7, 8, 0);
   private List<List<Integer>> successors;

   public EightPuzzle(List<Integer> startingValues) throws IllegalArgumentException {
       if (!startingValues.containsAll(goal) || startingValues.size() > 9) throw new IllegalArgumentException();
       this.startingValues = startingValues;
   }

   @Override
   public List<Integer> getInitialState() {
       return startingValues;
   }

   @Override
   public List<List<Integer>> getSuccessors(List<Integer> currentState) {
       successors = new ArrayList<List<Integer>>();
       int blankIndex = currentState.indexOf(0);
       int left = Arrays.asList(1, 2, 4, 5, 7, 8).contains(blankIndex)? blankIndex - 1 : -1;
       int right = Arrays.asList(0, 1, 3, 4, 6, 7).contains(blankIndex)? blankIndex + 1 : -1;
       int above = Arrays.asList(3, 4, 5, 6, 7, 8).contains(blankIndex)? blankIndex - 3 : -1;
       int below = Arrays.asList(0, 1, 2, 3, 4, 5).contains(blankIndex)? blankIndex + 3 : -1;
       addToSuccessors(left , currentState);
       addToSuccessors(right, currentState);
       addToSuccessors(above, currentState);
       addToSuccessors(below, currentState);
       return successors;
   }

   private void addToSuccessors(int index, List<Integer> state) {
       if (index == -1) return;
       List<Integer> copy = new ArrayList<Integer>(state);
       copy.set(state.indexOf(0), state.get(index));
       copy.set(index, 0);
       successors.add(copy);
   }

   @Override
   public boolean isGoal(List<Integer> state) {
       return goal.equals(state);
   }

   public static void main(String[] args) {
       EightPuzzle e = new EightPuzzle(Arrays.asList(new Integer[] { 1, 2, 3,
               4, 0, 6, 7, 5, 8 }));

       List<List<Integer>> r = new Solver<List<Integer>>(e).solveWithBFS();
       //List<List<Integer>> r = new Solver<List<Integer>>(e).solveWithIterativeDFS();
       //List<List<Integer>> r = new Solver<List<Integer>>(e).solveWithRecursiveDFS();
       for (List<Integer> l : r) {
           System.out.println(l);
       }
   }
}

If you like my answer, hit thumbs up. Thank you.