@above.. In case the no of nodes that are placed at the certain height from the start node are growing at an extremely fast rate, we can instead use a dfs approach as well.
On 30 July, 18:13, Lucifer <sourabhd2...@gmail.com> wrote: > @Mahendra Sengar.. > > We can solve it by interpreting it as a graph problem (as N and K are > small). > > Lets say that :- > a) Each node in the graph defines a particular state of the disks and > the pegs. > b) Each edge in the graph defines a valid transition from one state to > another and weight of each edge is 1. > > Now, we can choose to do a on-the-fly bfs to find the minimum path > from start node to the end node, where end node is nothing but the > state of the final configuration. > The on-the-fly approach works fine because we know that a solution > exists and is < 7, that the the total path cannot be >=7. and hence we > don't need to initially generate all the valid states of the > (disks,pegs) and then create a graph out of it. Rather, we can select > the start node and then figure out the nodes that a 1-edge far from > it, to carry on with the bfs approach. > > On 30 July, 15:17, Mahendra Sengar <sengar.m...@gmail.com> 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 -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
