Facebook sample puzzle: Towers of Hanoi

Question

Here is a question from Facebook hiring sample test.

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 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

There is no harm in discussing solution for this problem as it is a sample problem.

The solution to the classic Towers of Hanoi problem is really simple to code:

void hanoi(char s, char i, char d, int n)
{
     if(n>0)
     {
            hanoi(s, d, i, n-1);
            cout<<s<<":"<<d<<endl;
            hanoi(i, s, d, n-1);
     }        
}

The above can also be extended to a general 'k' pegs tower of hanoi. But, this knowledge is turning out to be not at all useful to design a solution to this sample puzzle. Any suggestions as to how to approach this and similar kind of problems in future?

Answer 1

Here's my dynamic programming solution that finds the optimal sequence of moves in at most O(K^N) steps, it runs in under a second for K = 5, N = 8. I hard coded the input data due to lazyness.

It is a BFS through the state space that never visits the same state twice. Then it gets the actual path by backtracking from the end to start (this part is linear with length of the optimal sequence). Basically, it is the "shortest path through a maze" algorithm, but the "maze" is the state space of the problem, the starting "location" is the initial state, and the ending "location" is the desired state.

Many similar problems can be solved this way, as long as you can define a finite state space, a "distance" between two states that your goal is to minimize, and a way to calculate which states you can move to from the current state.

For example, the "missionaries and cannibals" problem with an arbitrary number of each can be solved with this same algorithm.

Also, if you need "all optimal solutions" instead of "any optimal solution", it is easy to modify the algorithm to provide them.

class Program
{
    static int N = 8;
    static int K = 5;
    static List<int> StartState = new List<int> { 3, 3, 2, 1, 4, 1, 5, 2 };
    static List<int> EndState = new List<int> { 1, 4, 2, 2, 3, 4, 4, 3 };

    static LinkedList<int> StateQueue = new LinkedList<int>();
    static int[] MovesToState = new int[(int)Math.Pow(K, N)];


    static void Main(string[] args)
    {
        for (int i = 0; i < StartState.Count; i++)
        {
            StartState[i]--;
            EndState[i]--;
        }

        int startStateIndex = StateToNum(StartState);
        int endStateIndex = StateToNum(EndState);

        for (int i = 0; i < MovesToState.Length; i++)
            MovesToState[i] = -1;

        MovesToState[startStateIndex] = 0;

        StateQueue.AddFirst(startStateIndex);
        while (StateQueue.Count > 0 && MovesToState[endStateIndex] == -1)
        {
            var legalMoves = LegalMoves(StateQueue.Last.Value);
            foreach (var newStateIndex in legalMoves)
            {
                int currMoves = MovesToState[StateQueue.Last.Value];
                if (MovesToState[newStateIndex] == -1)
                {
                    MovesToState[newStateIndex] = currMoves + 1;
                    StateQueue.AddFirst(newStateIndex);
                }
            }
            StateQueue.RemoveLast();
        }

        var currStateIndex = endStateIndex;
        var moves = new List<Tuple<int, int>>();
        while (currStateIndex != startStateIndex)
        {
            var legalMoves = LegalMoves(currStateIndex);
            int currMoves = MovesToState[currStateIndex];
            foreach (var prevStateIndex in legalMoves)
            {
                if (MovesToState[prevStateIndex] == MovesToState[currStateIndex] - 1)
                {
                    var currState = NumToState(currStateIndex);
                    var prevState = NumToState(prevStateIndex);
                    for (int i = 0; i < N; i++)
                    {
                        if (currState[i] != prevState[i])
                        {
                            moves.Add(new Tuple<int, int>(prevState[i] + 1, currState[i] + 1));
                            currStateIndex = prevStateIndex;
                            break;
                        }
                    }
                }
            }
        }
        Console.WriteLine(MovesToState[endStateIndex]);
        moves.Reverse();
        foreach (var move in moves)
        {
            Console.WriteLine("{0} {1}", move.Item1, move.Item2);
        }

        Console.Read();
    }

    static List<int> LegalMoves(int stateIndex)
    {
        var legalMoves = new List<int>();

        var state = NumToState(stateIndex);

        int[] minOnPeg = new int[K];
        for (int i = 0; i < minOnPeg.Length; i++)
            minOnPeg[i] = N;
        for (int i = 0; i < N; i++)
            for (int j = 0; j < K; j++)
                if (state[i] == j && i < minOnPeg[j])
                    minOnPeg[j] = i;

        bool[] isTop = new bool[N];
        for (int i = 0; i < isTop.Length; i++)
            isTop[i] = false;
        for (int i = 0; i < K; i++)
            if (minOnPeg[i] < N)
                isTop[minOnPeg[i]] = true;

        for (int i = 0; i < N; i++)
        {
            if (!isTop[i])
                continue;

            for (int j = 0; j < K; j++)
            {
                if (minOnPeg[j] <= i)
                    continue;

                var tmp = state[i];
                state[i] = j;
                var newStateIndex = StateToNum(state);
                legalMoves.Add(newStateIndex);
                state[i] = tmp;
            }
        }
        return legalMoves;
    }

    static int StateToNum(List<int> state)
    {
        int r = 0;
        int f = 1;
        foreach (var peg in state)
        {
            r += f * peg;
            f *= K;
        }
        return r;
    }

    static List<int> NumToState(int num)
    {
        var r = new List<int>();
        for (int i = 0; i < N; i++)
        {
            r.Add(num % K);
            num = num / K;
        }
        return r;
    }
}

Answer 2

Found this solution in java. Basically it maps all the possible moves into a tree and performs a BFS.