## Tuesday, 21 February 2017

### Chapter 28 Exercise 14, Introduction to Java Programming, Tenth Edition Y. Daniel LiangY.

28.14 (4 * 4 16 tails problem) Listing 28.14, NineTail.java, presents a solution for the nine tails problem. Revise this program for the 4 * 4 16 tails problem.
Note that it is possible that a solution may not exist for a starting pattern. If so,
report that no solution exists.

import java.io.Serializable;
import java.util.ArrayList;
import java.util.List;

public class Exercise14 {
public static void main(String[] args) {
TailModel model = new TailModel();
System.out.println("The number of the starting patterns that have a solution: "
+ model.tree.getNumberOfVerticesFound());
System.out.println("The number of the starting patterns that don't have a solution: "
+ (model.NUMBER_OF_NODES - model.tree.getNumberOfVerticesFound()));
}

static class TailModel {
public final static int DIMENSION = 4;
// 1 << 9 is 512; 1 << 16 is 65536;
public final static int NUMBER_OF_NODES = 1 << DIMENSION * DIMENSION;
protected AbstractGraph<Integer>.Tree tree; // Define a tree

/** Construct a model */
public TailModel() {
// Create edges
List<AbstractGraph.Edge> edges = getEdges();

// Create a graph
UnweightedGraph<Integer> graph = new UnweightedGraph<Integer>(
edges, NUMBER_OF_NODES);

// Obtain a BSF tree rooted at the target node
tree = graph.bfs(NUMBER_OF_NODES - 1);
}

/** Create all edges for the graph */
private List<AbstractGraph.Edge> getEdges() {
List<AbstractGraph.Edge> edges =
new ArrayList<AbstractGraph.Edge>(); // Store edges

for (int u = 0; u < NUMBER_OF_NODES; u++) {
for (int k = 0; k < DIMENSION * DIMENSION; k++) {
char[] node = getNode(u); // Get the node for vertex u
if (node[k] == 'H') {
int v = getFlippedNode(node, k);
// Add edge (v, u) for a legal move from node u to node v
}
}
}

return edges;
}

public static int getFlippedNode(char[] node, int position) {
int row = position / DIMENSION;
int column = position % DIMENSION;

flipACell(node, row, column);
flipACell(node, row - 1, column);
flipACell(node, row + 1, column);
flipACell(node, row, column - 1);
flipACell(node, row, column + 1);

return getIndex(node);
}

public static void flipACell(char[] node, int row, int column) {
if (row >= 0 && row < DIMENSION && column >= 0 && column < DIMENSION) {
// Within the boundary
if (node[row * DIMENSION + column] == 'H')
node[row * DIMENSION + column] = 'T'; // Flip from H to T
else
node[row * DIMENSION + column] = 'H'; // Flip from T to H
}
}

public static int getIndex(char[] node) {
int result = 0;

for (int i = 0; i < DIMENSION * DIMENSION; i++)
if (node[i] == 'T')
result = result * 2 + 1;
else
result = result * 2 + 0;

return result;
}

public static char[] getNode(int index) {
char[] result = new char[DIMENSION * DIMENSION];

for (int i = 0; i < DIMENSION * DIMENSION; i++) {
int digit = index % 2;
if (digit == 0)
result[DIMENSION * DIMENSION - 1 - i] = 'H';
else
result[DIMENSION * DIMENSION - 1 - i] = 'T';
index = index / 2;
}

return result;
}

public List<Integer> getShortestPath(int nodeIndex) {
List<Integer> path = tree.getPath(nodeIndex);

if (path.size() == 1 && path.get(0) != DIMENSION * DIMENSION - 1)
return null;
else
return path;
}

public static void printNode(char[] node) {
for (int i = 0; i < DIMENSION * DIMENSION; i++)
if (i % DIMENSION != DIMENSION - 1)
System.out.print(node[i]);
else
System.out.println(node[i]);

System.out.println();
}
}
}


import java.util.*;

public abstract class AbstractGraph<V> implements Graph<V> {
protected List<V> vertices = new ArrayList<>(); // Store vertices
protected List<List<Edge>> neighbors
= new ArrayList<>(); // Adjacency lists

/** Construct an empty graph */
protected AbstractGraph() {
}

/** Construct a graph from vertices and edges stored in arrays */
protected AbstractGraph(V[] vertices, int[][] edges) {
for (int i = 0; i < vertices.length; i++)

}

/** Construct a graph from vertices and edges stored in List */
protected AbstractGraph(List<V> vertices, List<Edge> edges) {
for (int i = 0; i < vertices.size(); i++)

}

/** Construct a graph for integer vertices 0, 1, 2 and edge list */
protected AbstractGraph(List<Edge> edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
addVertex((V)(new Integer(i))); // vertices is {0, 1, ...}

}

/** Construct a graph from integer vertices 0, 1, and edge array */
protected AbstractGraph(int[][] edges, int numberOfVertices) {
for (int i = 0; i < numberOfVertices; i++)
addVertex((V)(new Integer(i))); // vertices is {0, 1, ...}

}

/** Create adjacency lists for each vertex */
int[][] edges, int numberOfVertices) {
for (int i = 0; i < edges.length; i++) {
}
}

/** Create adjacency lists for each vertex */
List<Edge> edges, int numberOfVertices) {
for (Edge edge: edges) {
}
}

@Override /** Return the number of vertices in the graph */
public int getSize() {
return vertices.size();
}

@Override /** Return the vertices in the graph */
public List<V> getVertices() {
return vertices;
}

@Override /** Return the object for the specified vertex */
public V getVertex(int index) {
return vertices.get(index);
}

@Override /** Return the index for the specified vertex object */
public int getIndex(V v) {
return vertices.indexOf(v);
}

@Override /** Return the neighbors of the specified vertex */
public List<Integer> getNeighbors(int index) {
List<Integer> result = new ArrayList<>();
for (Edge e: neighbors.get(index))

return result;
}

@Override /** Return the degree for a specified vertex */
public int getDegree(int v) {
return neighbors.get(v).size();
}

@Override /** Print the edges */
public void printEdges() {
for (int u = 0; u < neighbors.size(); u++) {
System.out.print(getVertex(u) + " (" + u + "): ");
for (Edge e: neighbors.get(u)) {
System.out.print("(" + getVertex(e.u) + ", " +
getVertex(e.v) + ") ");
}
System.out.println();
}
}

@Override /** Clear graph */
public void clear() {
vertices.clear();
neighbors.clear();
}

@Override /** Add a vertex to the graph */
if (!vertices.contains(vertex)) {
return true;
}
else {
return false;
}
}

/** Add an edge to the graph */
if (e.u < 0 || e.u > getSize() - 1)
throw new IllegalArgumentException("No such index: " + e.u);

if (e.v < 0 || e.v > getSize() - 1)
throw new IllegalArgumentException("No such index: " + e.v);

if (!neighbors.get(e.u).contains(e)) {
return true;
}
else {
return false;
}
}

@Override /** Add an edge to the graph */
public boolean addEdge(int u, int v) {
}

/** Edge inner class inside the AbstractGraph class */
public static class Edge {
public int u; // Starting vertex of the edge
public int v; // Ending vertex of the edge

/** Construct an edge for (u, v) */
public Edge(int u, int v) {
this.u = u;
this.v = v;
}

public boolean equals(Object o) {
return u == ((Edge)o).u && v == ((Edge)o).v;
}
}

@Override /** Obtain a DFS tree starting from vertex v */
/** To be discussed in Section 30.6 */
public Tree dfs(int v) {
List<Integer> searchOrder = new ArrayList<>();
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++)
parent[i] = -1; // Initialize parent[i] to -1

// Mark visited vertices
boolean[] isVisited = new boolean[vertices.size()];

// Recursively search
dfs(v, parent, searchOrder, isVisited);

// Return a search tree
return new Tree(v, parent, searchOrder);
}

/** Recursive method for DFS search */
private void dfs(int u, int[] parent, List<Integer> searchOrder,
boolean[] isVisited) {
// Store the visited vertex
isVisited[u] = true; // Vertex v visited

for (Edge e : neighbors.get(u)) {
if (!isVisited[e.v]) {
parent[e.v] = u; // The parent of vertex e.v is u
dfs(e.v, parent, searchOrder, isVisited); // Recursive search
}
}
}

@Override /** Starting bfs search from vertex v */
/** To be discussed in Section 28.7 */
public Tree bfs(int v) {
List<Integer> searchOrder = new ArrayList<>();
int[] parent = new int[vertices.size()];
for (int i = 0; i < parent.length; i++)
parent[i] = -1; // Initialize parent[i] to -1

new java.util.LinkedList<>(); // list used as a queue
boolean[] isVisited = new boolean[vertices.size()];
queue.offer(v); // Enqueue v
isVisited[v] = true; // Mark it visited

while (!queue.isEmpty()) {
int u = queue.poll(); // Dequeue to u
for (Edge e: neighbors.get(u)) {
if (!isVisited[e.v]) {
queue.offer(e.v); // Enqueue w
parent[e.v] = u; // The parent of w is u
isVisited[e.v] = true; // Mark it visited
}
}
}

return new Tree(v, parent, searchOrder);
}

/** Tree inner class inside the AbstractGraph class */
/** To be discussed in Section 28.5 */
public class Tree {
private int root; // The root of the tree
private int[] parent; // Store the parent of each vertex
private List<Integer> searchOrder; // Store the search order

/** Construct a tree with root, parent, and searchOrder */
public Tree(int root, int[] parent, List<Integer> searchOrder) {
this.root = root;
this.parent = parent;
this.searchOrder = searchOrder;
}

/** Return the root of the tree */
public int getRoot() {
return root;
}

/** Return the parent of vertex v */
public int getParent(int v) {
return parent[v];
}

/** Return an array representing search order */
public List<Integer> getSearchOrder() {
return searchOrder;
}

/** Return number of vertices found */
public int getNumberOfVerticesFound() {
return searchOrder.size();
}

/** Return the path of vertices from a vertex to the root */
public List<V> getPath(int index) {
ArrayList<V> path = new ArrayList<>();

do {
index = parent[index];
}
while (index != -1);

return path;
}

/** Print a path from the root to vertex v */
public void printPath(int index) {
List<V> path = getPath(index);
System.out.print("A path from " + vertices.get(root) + " to " +
vertices.get(index) + ": ");
for (int i = path.size() - 1; i >= 0; i--)
System.out.print(path.get(i) + " ");
}

/** Print the whole tree */
public void printTree() {
System.out.println("Root is: " + vertices.get(root));
System.out.print("Edges: ");
for (int i = 0; i < parent.length; i++) {
if (parent[i] != -1) {
// Display an edge
System.out.print("(" + vertices.get(parent[i]) + ", " +
vertices.get(i) + ") ");
}
}
System.out.println();
}
}
}


public interface Graph<V> {
/** Return the number of vertices in the graph */
public int getSize();

/** Return the vertices in the graph */
public java.util.List<V> getVertices();

/** Return the object for the specified vertex index */
public V getVertex(int index);

/** Return the index for the specified vertex object */
public int getIndex(V v);

/** Return the neighbors of vertex with the specified index */
public java.util.List<Integer> getNeighbors(int index);

/** Return the degree for a specified vertex */
public int getDegree(int v);

/** Print the edges */
public void printEdges();

/** Clear graph */
public void clear();

/** Add a vertex to the graph */

/** Add an edge to the graph */
public boolean addEdge(int u, int v);

/** Obtain a depth-first search tree */
public AbstractGraph<V>.Tree dfs(int v);

/** Obtain a breadth-first search tree */
public AbstractGraph<V>.Tree bfs(int v);
}


import java.util.*;

public class UnweightedGraph<V> extends AbstractGraph<V> {
/** Construct an empty graph */
public UnweightedGraph() {
}

/** Construct a graph from vertices and edges stored in arrays */
public UnweightedGraph(V[] vertices, int[][] edges) {
super(vertices, edges);
}

/** Construct a graph from vertices and edges stored in List */
public UnweightedGraph(List<V> vertices, List<Edge> edges) {
super(vertices, edges);
}

/** Construct a graph for integer vertices 0, 1, 2 and edge list */
public UnweightedGraph(List<Edge> edges, int numberOfVertices) {
super(edges, numberOfVertices);
}

/** Construct a graph from integer vertices 0, 1, and edge array */
public UnweightedGraph(int[][] edges, int numberOfVertices) {
super(edges, numberOfVertices);
}
}