This is the Towers of Hanoi problem in which you’ve to find the minimum number of moves required to move from one configuration to another.(Not the classical.Thats easy).I’ve been stranded on this for a complete day.
There are K pegs. Each peg can hold
discs in decreasing order of radius
when looked from bottom to top of the
peg. There are N discs which have
radius 1 to N; Given the initial
configuration of the pegs and the
final configuration of the pegs,
output the moves required to transform
from the initial to final
configuration. You are required to do
the transformations in minimal number
of moves.
A move consists of picking the topmost
disc of any one of the pegs and
placing it on top of anyother peg. At
anypoint of time, the decreasing
radius property of all the pegs must
be maintained.
Constraints: 1<= N<=8 3<= K<=5
Input Format: N K 2nd line contains N
integers. Each integer in the second
line is in the range 1 to K where the
i-th integer denotes the peg to which
disc of radius i is present in the
initial configuration. 3rd line
denotes the final configuration in a
format similar to the initial
configuration.
Output Format: The first line contains
M - The minimal number of moves
required to complete the
transformation. The following M lines
describe a move, by a peg number to
pick from and a peg number to place
on. If there are more than one
solutions, it’s sufficient to output
any one of them. You can assume, there
is always a solution with less than 7
moves and the initial confirguration
will not be same as the final one.
Sample Input #00:
2 3 1 1 2 2 Sample Output #00:
3 1 3 1 2 3 2
Sample Input #01:
6 4 4 2 4 3 1 1 1 1 1 1 1 1 Sample
Output #01:
5 3 1 4 3 4 1 2 1 3 1
My approach for this problem **was to find out a graph for the state space and then do a BFS on it to find out the shortest path.However, the problem is how to create this graph . I’ve thought of recursively implementing it though I’m facing great difficulty here ie how to connect the nodes of the sub-graphs recursively.**If anybody has a better insight or approach to this problem kindly share it along with the algorithm.A similar solution used is on http://en.wikipedia.org/wiki/Tower_of_Hanoi
1 Like
I think this link can help you:
3 Likes
Here is a Java code which prepares the graph with neighboring configurations and solves it. I tried to use Object-Oriented way, but I still feel there might be better hack way to solve this faster. Hope it helps.
import FBSample.Node.Move;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
/**
*
* @author Sada Kurapati <[email protected]>
*/
public class FBSample {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
//pegs initial config
Node source = readPegsConfiguration(k, n, sc);
//read target configuration
Node target = readPegsConfiguration(k, n, sc);
//To keep track what config we visited and avoid cycles
Set<Node> visited = new HashSet<Node>();
try {
minMovesToTarget(source, target, visited);
} catch (Exception ex) {
System.out.println("Exception = " + ex);
}
}
private static void minMovesToTarget(Node source, Node target, Set<Node> visited) throws CloneNotSupportedException {
//Perform BFS
//add soource node to Queue
Queue<Node> q = new LinkedList<Node>();
q.add(source);
Node current = source;
while (!q.isEmpty()) {
current = q.poll();
if (current.equals(target)) { //found the target configuration
break;
}
List<Node> neighbors = current.neighbors();
if (neighbors.size() > 0) {
for (Node n : neighbors) {
if (!visited.contains(n)) {//if not visited, put it in queue
q.offer(n);
visited.add(n);
}
}
}
}
//Printing path and moves if target config found
if (current.equals(target)) {
printOutput(current);
}
}
private static Node readPegsConfiguration(int k, int n, Scanner sc) {
Stack<Integer>[] initialState = new Stack[k];
for (int i = 0; i < k; i++) {
initialState[i] = new Stack<Integer>();
}
//reading and reversing the line as we need to put the elements in decresing size
//disc is key and peg is value.
TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>(Collections.reverseOrder());
for (int i = 0; i < n; i++) {
map.put(i, sc.nextInt());
}
//prepare pegs
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
initialState[entry.getValue() - 1].push(entry.getKey());
}
return new Node(initialState);
}
static void printOutput(Node target) {
Stack<Move> stack = new Stack<>(); //using stack as we need to print the trail from Source - target config
while (target.parent != null) {
stack.add(target.move);
target = target.parent;
}
System.out.println(stack.size());
while (!stack.isEmpty()) {
System.out.println(stack.pop());
}
}
static class Node implements Cloneable {
//pegs
Stack<Integer>[] state = null;
Node parent = null; //for backtracking trail
Move move = null; // The move we made to go to next neighbor config
public Node(Stack<Integer>[] st) {
state = st;
}
@Override
protected Node clone() throws CloneNotSupportedException {
Stack<Integer>[] cloneStacks = new Stack[state.length];
for (int i = 0; i < state.length; i++) {
cloneStacks[i] = (Stack) state[i].clone();
}
Node clone = new Node(cloneStacks);
return clone;
}
//returns the neghboring configurations.
//What all configurations we can get based on current config.
public List<Node> neighbors() throws CloneNotSupportedException {
List<Node> neighbors = new ArrayList<>();
int k = state.length;
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
if (i != j && !state[i].isEmpty()) {
Node child = this.clone();
//make a move
if (canWeMove(child.state[i], child.state[j])) {
child.state[j].push(child.state[i].pop());
//this is required to backtrack the trail once we find the target config
child.parent = this;
//the move we made to get to this neighbor
child.move = new Move(i, j);
neighbors.add(child);
}
}
}
}
return neighbors;
}
public boolean canWeMove(Stack<Integer> fromTower, Stack<Integer> toTower) {
boolean answer = false;
if (toTower.isEmpty()) {// if destination peg is empty, then we can move any disc
return true;
}
int toDisc = toTower.peek();
int fromDisc = fromTower.peek();
if (fromDisc < toDisc) { //we can only place small disc on top
answer = true;
}
return answer;
}
@Override
public int hashCode() {
int hash = 7;
return hash;
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final Node other = (Node) obj;
if (!Arrays.deepEquals(this.state, other.state)) {
return false;
}
return true;
}
class Move {
int pegFrom, pegTo;
public Move(int f, int t) {
pegFrom = f + 1;
pegTo = t + 1;
}
@Override
public String toString() {
return pegFrom + " " + pegTo;
}
}
}
}