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 any other peg. At any point 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
NOTE: You need to write the full code taking all inputs are from stdin and outputs to stdout
I came up with a solution doing a combinatorial search using breath-first search, basically looking for the shortest path from the initial state to the goal. I learned this technique in the class Design of Computer Programs with Peter Norvig at Udacity.com Here it is the code in Java.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class DisksAndRods {
private static final int EMPTY = -1;
private int n;
private int k;
private int[] initial;
private int[] goal;
public DisksAndRods(int n, int k, int[] initial, int[] goal) {
this.n = n;
this.k = k;
this.initial = initial;
this.goal = goal;
validate();
}
/**
* Validate the input
*/
private void validate() {
if (n < 1 || n > 8) throw new IllegalArgumentException("1 <= N <= 8");
if (k < 3 || k > 5) throw new IllegalArgumentException("3 <= K <= 5");
if (initial.length != n || goal.length != n) {
throw new IllegalArgumentException("Initial and goal disks configuration must be equal to N");
}
for (int i = 0; i < n; i++) {
if ((initial[i] < 1 || initial[i] > k) || (goal[i] < 1 || goal[i] > k)) {
throw new IllegalArgumentException("Invalid rod number!");
}
}
}
/**
* Checks if a given state is the goal that we are looking for.
*
* @param state The state to check
* @return True if we reached the goal, false otherwise.
*/
private boolean isGoal(State state) {
return Arrays.equals(goal, state.disks);
}
/**
* Checks if given a configuration of the disks and rods if the disk can be moved.
*
* @param disk The disk to check
* @param disks The configuration for the disks
* @param rodTops What are the disks tops in each rod
* @return True if it can be moved, false otherwise.
*/
private boolean canMoveDisk(int disk, int[] disks, int[] rodTops) {
if (disk == 0) return true; // It is the smallest disk
// Check if the disk is under a smaller disk
for (int i = disk - 1; i >= 0; i--) {
if (disks[i] == disks[disk]) {
return false;
}
}
// Check if there are rods where the disk can be placed
// i.e. a rod that is empty or with a bigger disk
int count = 0;
for (int i = 0; i < k; i++) {
if (rodTops[i] == EMPTY || rodTops[i] > disk) {
count++;
}
}
return count > 0;
}
/**
* Given a configuration of the disks, calculates what is the top disk in each rod, -1 if the rod is empty.
*
* @param disks The configuration of disks.
* @return An array of k rods with the tops.
*/
private int[] getRodsTop(int[] disks) {
int[] rods = new int[k];
Arrays.fill(rods, EMPTY);
for (int i = 0; i < n; i++) {
if (rods[disks[i] - 1] == EMPTY || i < rods[disks[i] - 1]) {
rods[disks[i] - 1] = i;
}
}
return rods;
}
/**
* Given a state determines its successors.
*
* @param current The state to get the successors from.
* @return A set with the successor states.
*/
private Set<State> successors(State current) {
Set<State> successors = new HashSet<State>();
int[] tops = getRodsTop(current.disks);
for (int i = 0; i < n; i++) {
if (canMoveDisk(i, current.disks, tops)) {
for (int j = 0; j < k; j++) {
if (tops[j] == EMPTY || tops[j] > i) {
int[] newDisks = Arrays.copyOf(current.disks, n);
newDisks[i] = j + 1;
successors.add(new State(newDisks, current.disks[i], j + 1));
}
}
}
}
return successors;
}
/**
* Solves the problem using shortest path problem.
*
* @return A list of State objects indicating the steps to follow to solve the problem.
*/
public List<State> solve() {
State start = new State(initial);
if (isGoal(start)) {
return Arrays.asList(start);
}
// Keep track of the states already explored
Set<State> explored = new HashSet<State>();
// Keep track of the paths that we are evaluating
Queue<List<State>> frontier = new LinkedList<List<State>>();
// First path starts from the start state
frontier.add(Arrays.asList(start));
// Evaluate all paths until done or until we found the goal
while (!frontier.isEmpty()) {
List<State> path = frontier.poll();
State lastStatePath = path.get(path.size() - 1);
// Get the successor states for the last state in the current path state
for (State state : successors(lastStatePath)) {
// Don't explore states that we have already explored
if (!explored.contains(state)) {
explored.add(state);
List<State> newPath = new ArrayList<State>(path);
newPath.add(state);
if (isGoal(state)) {
return newPath;
} else {
frontier.add(newPath);
}
}
}
}
return new ArrayList<State>();
}
/**
* Class to represent a state.
*/
public static class State {
private int[] disks;
private int from;
private int to;
public State(int[] disks) {
this.disks = disks;
}
public State(int[] disks, int from, int to) {
this.disks = disks;
this.from = from;
this.to = to;
}
public int getFrom() {
return from;
}
public int getTo() {
return to;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof State)) return false;
State state = (State) o;
if (from != state.from) return false;
if (to != state.to) return false;
if (!Arrays.equals(disks, state.disks)) return false;
return true;
}
@Override
public int hashCode() {
int result = 17;
result = 31 * result + (disks != null ? Arrays.hashCode(disks) : 0);
result = 31 * result + from;
result = 31 * result + to;
return result;
}
@Override
public String toString() {
return "State{" +
"disks=" + Arrays.toString(disks) +
", from=" + from +
", to=" + to +
'}';
}
}
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
int k = reader.nextInt();
int[] initial = new int[n];
for (int i = 0; i < n; i++) {
initial[i] = reader.nextInt();
}
int[] goal = new int[n];
for (int i = 0; i < n; i++) {
goal[i] = reader.nextInt();
}
DisksAndRods disksAndRods = new DisksAndRods(n, k, initial, goal);
List<State> path = disksAndRods.solve();
if (path.size() > 0) {
System.out.println(path.size() - 1);
for (int i = 1; i < path.size(); i++) {
State step = path.get(i);
System.out.printf("%d %d\n", step.getFrom(), step.getTo());
}
}
}
}
Have fun!
