Here is untested code. (It does run the two examples correctly,
though). If you see any problems, let me know.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.regex.Pattern;
public class SuperTowersOfHanoi {
class Instance {
/**
* Max number of moves to consider.
*/
public static final int MAX_MOVES = 6;
/**
* N and K from the problem.
*/
private final int n, k;
/**
* Initial and goal configurations.
*/
public final Configuration init, goal;
/**
* A* closed and open lists.
*/
private final HashSet<Configuration> closed;
private final PriorityQueue<Configuration> open;
Instance(int n, int k) {
this.n = n;
this.k = k;
init = new Configuration();
goal = new Configuration();
open = new PriorityQueue<Configuration>(256,
new Comparator<Configuration>() {
public int compare(Configuration a, Configuration
b) {
return a.f() - b.f();
}
});
closed = new HashSet<Configuration>();
}
class Configuration {
/**
* Configuration tree parent. Root is always init.
*/
Configuration parent;
/**
* The peg each disk 0 to n-1 lies upon.
*/
final int[] peg;
/**
* The disk that was moved to get to this config from the
parent.
*/
final int moved;
/**
* Construct init or goal configuration.
*/
public Configuration() {
this.peg = new int [n];
moved = -1;
}
/**
* Construct a child configuration that is one move from
its parent.
*
* @param parent parent configuration
* @param moved disk that was moved to reach this
configuration
* @param peg the disk was moved to
*/
public Configuration(Configuration parent, int moved, int
to) {
this.parent = parent;
this.peg = Arrays.copyOf(parent.peg, n);
this.peg[moved] = to;
this.moved = moved;
}
/**
* Path function: Number of steps from init. We could
cache this
* value for speed if needed.
*
* @return path length
*/
int g() {
int gVal = 0;
for (Configuration c = parent; c != null; c =
c.parent)
++gVal;
return gVal;
}
/**
* Heuristic function: number of disks out of place with
respect to
* goal. We could cache this value for speed if needed.
*
* @return heuristic value
*/
int h() {
int hVal = 0;
for (int i = 0; i < n; i++)
if (peg[i] != goal.peg[i])
++hVal;
return hVal;
}
/**
* Search function combines path and heuristic.
*
* @return search function
*/
int f() {
return g() + h();
}
/**
* Parse string fields to get peg locations.
* Correct for 1- vs. 0-based numbering.
*
* @param fields string fields containing peg locations
*/
public void parse(String [] fields) {
for (int i = 0; i < n; i++)
peg[i] = Integer.parseInt(fields[i]) - 1;
}
/**
* Fill the given array list with configurations that can
be
* "legally" reached from this one in a single move.
*
* @param s successor list
*/
public void getSuccessors(ArrayList<Configuration> s) {
s.clear();
// Only find successors if we're not already at the
limit.
if (g() < MAX_MOVES) {
// Top array will contain disk at top of
respective peg
// or n if no disk at all.
int [] top = new int [k];
Arrays.fill(top, n);
for (int i = n - 1; i >= 0; i--)
top[peg[i]] = i;
// Now check each top to see where it can move.
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++)
if (top[i] < top[j])
// A move is possible. Add its
configuration.
s.add(new Configuration(this, top[i],
j));
}
}
/**
* Traverse parent pointers in reverse to print the moves.
*
* @param n distance from leaf to this config
*/
public void printMoves(int n) {
if (parent == null)
System.out.println(n);
else {
parent.printMoves(n + 1);
int from = parent.peg[moved] + 1;
int to = peg[moved] + 1;
System.out.println(from + " " + to);
}
}
/**
* Support the closed list hash set.
*
* @param o other object for comparison
* @return true iff this is equal to the other object
*/
@Override
public boolean equals(Object o) {
return o instanceof Configuration
&& Arrays.equals(peg, ((Configuration)o).peg);
}
/**
* Support the closed list hash set.
*
* @return hash value likely to be unique for each
configuration
*/
@Override
public int hashCode() {
int h = 0x21421421;
for (int disk : peg)
h = h * 17 + disk;
return h;
}
}
/**
* Do A* search toward the goal state. If found, print and
return.
* Otherwise, print "No Solution."
*/
void search() {
open.clear();
open.add(init);
closed.clear();
ArrayList<Configuration> successors = new
ArrayList<Configuration>();
Configuration c = null;
while ((c = open.poll()) != null) {
closed.add(c);
c.getSuccessors(successors);
for (Configuration s : successors) {
if (s.equals(goal)) {
s.printMoves(0);
return;
}
if (!closed.contains(s))
open.add(s);
}
}
System.out.println("No solution.");
}
}
void run() throws IOException {
BufferedReader r = new BufferedReader(new
InputStreamReader(System.in));
Pattern p = Pattern.compile("\\s+");
String [] fields = p.split(r.readLine());
int n = Integer.parseInt(fields[0]);
int k = Integer.parseInt(fields[1]);
Instance inst = new Instance(n, k);
inst.init.parse(p.split(r.readLine()));
inst.goal.parse(p.split(r.readLine()));
inst.search();
}
public static void main(String[] args) {
try {
new SuperTowersOfHanoi().run();
} catch (IOException ex) {
System.err.println("Input format error.");
}
}
}
On May 30, 10:37 pm, Gene <[email protected]> wrote:
> Since the number of moves must be optimal, this seems to be a search
> problem. A-Star is the right search algorithm. This is an algorithm
> that's somewhere between depth first and breadth first. It expands the
> tree according to a heuristic that you choose, which can shrink the
> run time enormously. The Wikipedia page on this is not bad
>
> http://en.wikipedia.org/wiki/A*_search_algorithm#Pseudocode
>
> On May 30, 2:41 pm, g4ur4v <[email protected]> wrote:
>
>
>
>
>
>
>
> > 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
>
> > (question taken from facebook hiring sample test .)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
