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.
