The weighted nine tails problem can be reduced to the weighted shortest path problem.

Section presented the nine tails problem and solved it using the BFS algorithm. This section presents a variation of the problem and solves it using the shortest-path algorithm.

The nine tails problem is to find the minimum number of the moves that lead to all coins facing down. Each move flips a head coin and its neighbors. The weighted nine tails problem assigns the number of flips as a weight on each move. For example, you can change the coins in Figure below a to those in Figure below b by flipping the first coin in the first row and its two neighbors. Thus, the weight for this move is **3**. You can change the coins in Figure below c to Figure below d by flipping the center coin and its four neighbors. So the weight for this move is **5**.

The weighted nine tails problem can be reduced to finding a shortest path from a starting node to the target node in an edge-weighted graph. The graph has 512 nodes. Create an edge from node **v** to **u** if there is a move from node **u** to node **v**. Assign the number of flips to be the weight of the edge.

Recall that in Section we defined a class **NineTailModel** for modeling the nine tails problem. We now define a new class named **WeightedNineTailModel** that extends **NineTailModel**, as shown in Figure below.

The **NineTailModel** class creates a **Graph** and obtains a **Tree** rooted at the target node **511**. **WeightedNineTailModel** is the same as **NineTailModel** except that it creates a **WeightedGraph** and obtains a **ShortestPathTree** rooted at the target node **511**. **WeightedNineTailModel** extends **NineTailModel**. The method **getEdges()** finds all edges in the graph. The **getNumberOfFlips(int u, int v)** method returns the number of flips from node **u** to node **v**. The **getNumberOfFlips(int u)** method returns the number of flips from node **u** to the target node.

The code below implements **WeightedNineTailModel**.

```
package demo;
import java.util.*;
public class WeightedNineTailModel extends NineTailModel {
/** Construct a model */
public WeightedNineTailModel() {
// Create edges
List<WeightedEdge> edges = getEdges();
// Create a graph
WeightedGraph<Integer> graph = new WeightedGraph<>(edges, NUMBER_OF_NODES);
// Obtain a shortest path tree rooted at the target node
tree = graph.getShortestPath(511);
}
/** Create all edges for the graph */
private List<WeightedEdge> getEdges() {
// Store edges
List<WeightedEdge> edges = new ArrayList<>();
for(int u = 0; u < NUMBER_OF_NODES; u++) {
for(int k = 0; k < 9; k++) {
char[] node = getNode(u); // Get the node for vertex u
if(node[k] == 'H') {
int v = getFlippedNode(node, k);
int numberOfFlips = getNumberOfFlips(u, v);
// Add edge (v, u) for a legal move from node u to node v
edges.add(new WeightedEdge(v, u, numberOfFlips));
}
}
}
return edges;
}
private static int getNumberOfFlips(int u, int v) {
char[] node1 = getNode(u);
char[] node2 = getNode(v);
int count = 0; // Count the number of different cells
for(int i = 0; i < node1.length; i++)
if(node1[i] != node2[i]) count++;
return count;
}
public int getNumberOfFlips(int u) {
return (int)((WeightedGraph<Integer>.ShortestPathTree)tree).getCost(u);
}
}
```

**WeightedNineTailModel** extends **NineTailModel** to build a **WeightedGraph** to model the weighted nine tails problem (lines 10–11). For each node **u**, the **getEdges()** method finds a flipped node **v** and assigns the number of flips as the weight for edge (**v**, **u**) (line 30). The **getNumberOfFlips(int u, int v)** method returns the number of flips from node **u** to node **v** (lines 38–47). The number of flips is the number of the different cells between the

two nodes (line 44).

The **WeightedNineTailModel** obtains a **ShortestPathTree** rooted at the target node **511** (line 14). Note that **tree** is a protected data field defined in **NineTailModel** and **ShortestPathTree** is a subclass of **Tree**. The methods defined in **NineTailModel** use the **tree** property.

The **getNumberOfFlips(int u)** method (lines 49–52) returns the number of flips from node **u** to the target node, which is the cost of the path from node **u** to the target node. This cost can be obtained by invoking the **getCost(u)** method defined in the **ShortestPathTree** class (line 51).

The code below gives a program that prompts the user to enter an initial node and displays the minimum number of flips to reach the target node.

```
package demo;
import java.util.Scanner;
public class WeightedNineTail {
public static void main(String[] args) {
// Prompt the user to enter nine coins' Hs and Ts
System.out.print("Enter the initial nine coins Hs and Ts: ");
Scanner input = new Scanner(System.in);
String s = input.nextLine();
char[] initialNode = s.toCharArray();
WeightedNineTailModel model = new WeightedNineTailModel();
java.util.List<Integer> path = model.getShortestPath(NineTailModel.getIndex(initialNode));
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()));
System.out.println("The number of flips is " + model.getNumberOfFlips(NineTailModel.getIndex(initialNode)));
}
}
```

`Enter an initial nine coins Hs and Ts: HHHTTTHHH`

`The steps to flip the coins are`

`HHH`

TTT

HHH

`HHH`

THT

TTT

`TTT`

TTT

TTT

`The number of flips is 8`

The program prompts the user to enter an initial node with nine letters with a combination of **H**s and **T**s as a string in line 8, obtains an array of characters from the string (line 9), creates a model (line 11), obtains the shortest path from the initial node to the target node (lines 12–13), displays the nodes in the path (lines 16–17), and invokes **getNumberOfFlips** to get the number of flips needed to reach the target node (line 20).

## Top comments (0)