Case Study: The Weighted Nine Tails Problem

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 Hs and Ts 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).