Chapter 29, Problem 29.4PE

(Modify weight in the nine tails problem) In the text, we assign the number of the flips as the weight for each move. Assuming the weight is three times of the number of flips, revise the program.

Program Plan Intro

Program Plan:

• Create a package “main”.
  • Add a java class named “Edge” to the package which is used to get the edges from the graph.
  • Add a java class named “Graph” to the package which is used to add and remove vertices, edges.
  • Add a java class named “UnweightedGraph” to the package which is used to store vertices and neighbors.
  • Add a java class named “WeightedGraph” to the package which is used to get the weighted edges and print the edges.
  • Add a java class named “WeightedEdge” to the package which is used to compare edges.
  • Add a java class named “NineTailModel” to the package which is used to compare edges.
  • Add a java class named “Test” to the package.
    • Import the required packages.
    • Declare the main class.
      • Give the “main ()” method.
        • Allocate the memory for the “Test” class.
      • Define “Test”.
        • Get the initial nine coins from the user.
        • Create an object for the “ModifiedWeightedNineTailModel” class.
        • Create an array list.
        • Display the steps to flip the coin.
        • Display the number of flips.
      • Define “ModifiedWeightedNineTailModel” class.
        • Create an edges and graph.
        • Obtain a BSF tree rooted at the target node.
      • Define “getEdges” method.
        • Create an array list.
        • Create all the edges for the graph by calling “getFlippedNode” and “getNumberOfFlips” methods.
          • Add edge for a legal move from the node u to v.
        • Return the edge.
      • Define “getNumberOfFlips” method.
        • Declare the required variables.
        • Check if the “node1” is not equal to “node2” means increment the “count”.
        • Return the value.
      • Define “getNumberOfFlips” method.
        • Return the total number of flips.

Program Description Answer

The given program is used to modify weight in the nine tails problem is as follows:

Explanation of Solution

Program:

Edge.java: Refer book from chapter 28 – Listing 28.1.

Graph.java: Refer book from chapter 28 – Listing 28.3.

UnweightedGraph.java: Refer book from chapter 28 – Listing 28.4.

WeightedGraph.java: Refer book from chapter 29 – Listing 29.2.

WeightedEdge.java: Refer book from chapter 29 – Listing 29.1.

NineTailModel.java: Refer book from chapter – Listing 28.13.

Test.java:

//import the required statement

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

//definition of "Test" class

public class Test

{

//main method

public static void main(String[] args)

{

//memory allocation

new Test();

}

//definition of "Test"

public Test()

{

// get the input from the user

System.out.print("Enter an initial nine coin H’s and T's: ");

Scanner input = new Scanner(System.in);

String s = input.nextLine();

//declare the variable

char[] initialNode = s.toCharArray();

//create an object

ModifiedWeightedNineTailModel model = new ModifiedWeightedNineTailModel();

//create an ArrayList

java.util.List<Integer> path =

model.getShortestPath (NineTailModel.getIndex(initialNode));

//display the steps to flip the coin

System.out.println("The steps to flip the coins are ");

for (int i = 0; i < path.size(); i++)

NineTailModel.printNode(

NineTailModel.getNode (path.get(i).intValue()));

//display the number of flips

System.out.println("The number of flips is " +

model.getNumberOfFlips (NineTailModel.getIndex(initialNode)));

}

//definition of "ModifiedWeightedNineTailModel"

public static class ModifiedWeightedNineTailModel extends NineTailModel

{

//constructor

public ModifiedWeightedNineTailModel()

{

// create edges

List<WeightedEdge> edges = getEdges();

// create a graph

WeightedGraph<Integer> graph = new WeightedGraph<Integer>(

edges, NUMBER_OF_NODES);

/* obtain a BSF tree rooted at the target node*/

tree = graph.getShortestPath(511);

}

//definition of "getEdge" method

private List<WeightedEdge> getEdges()

{

// create an ArrayList

List<WeightedEdge> edges = new ArrayList<WeightedEdge>();

//check the condition

for (int u = 0; u < NUMBER_OF_NODES; u++)

{

//check the condition

for (int k = 0; k < 9; k++)

{

// get the node for vertex u

char[] node = getNode(u);

//check the condition

if (node[k] == 'H')

{

/*call the "getFlippedNode" method*/

int v = getFlippedNode(node, k);

int numberOfFlips = getNumberOfFlips(u, v);

/* add edge for a legal move from node u to node v*/

edges.add(new WeightedEdge(v, u, numberOfFlips));

}

}

}

//return statement

return edges;

}

//definition of "getNumberOfFlips" method

private static int getNumberOfFlips(int u, int v)

{

//declare the variables

char[] node1 = getNode(u);

char[] node2 = getNode(v);

int count = 0;

//check the condition

for (int i = 0; i < node1.length; i++)

//check the condition

if (node1[i] != node2[i]) count++;

//return statement

return 3 * count;

}

//definition of "getNumberOfFlips" method

public int getNumberOfFlips(int u)

{

//return statement

return (int)((WeightedGraph<Integer>.ShortestPathTree)tree).getCost(u);

}

}

}

Sample Output

Enter an initial nine coin H’s and T's: HHHTTTHHH

The steps to flip the coins are

HHH

TTT

HHH

HHH

THT

TTT

TTT

TTT

TTT

The number of flips is 24