dc360
BAN USER 0of 0 votes
AnswersQuestion 1 / 1
 dc360 in United States
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 ith 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
If you are using "Java", the classname is "Solution" Report Duplicate  Flag  PURGE
Facebook Algorithm
I don't think its that straightforward. Consider
[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
Rotate right by 3
[80, 90, 100, 10, 20, 30, 40, 50, 60, 70]
10 goes to 40's place, but 40 does not go to 10's place. That means it is a chain of replacements. You could say reverse_40_first, then reverse_10. Replacements should be done recursively then.
 dc360 August 10, 2012If you are allowed to encapsulate this array, then you don't need to rotate. Just remember k and then every get/set operation for an index i goes to a mapping logic to map to the real index. Caller thinks that the array has been rotated.
array[convert(i)] will return an element from the rotated array.
private int convert(int i)
{
int x = i  rotatedBy;
x = x % a.length;
if (x < 0)
x = x + a.length;
return x;
}

dc360
August 10, 2012 I assume 100 numbers are stored such that it can't be sorted inplace. Otherwise quicksort can sort them without even needing additional 20 space. So with that assumption, take 20 from the source and move to the additional space, sort in n log n (n=20). Copy it back to the original place. Repeat 4 more times for each block of 20. Now we have 5 sorted blocks of 20 in the original space. Now merge first block with second using the additional space as the temp storage. After this step, block 1 and block 2 are merged and sorted. Then merge 3 block with the first+second block. Then 4th and then 5th.
 dc360 August 10, 2012BFS can be done on a graph that has loops. Just keep track of nodes that you visited before.
Eugene, in your other posts i didn't understand why the algorithm is faster if you search from both the sides. Isn't it still traversing the same tree + additional effort to find the intersection.
I was able to write a program with a recursive "move" method which moves disks starting from the largest to the smallest to its corresponding target keg. But in that method, several other disks need to be moved as well. How can we tell which move will result in minimum moves? and how to not run into an infinite loop of moves?
 dc360 May 21, 2012Open Chat in New Window
I see. Looks like the recursion handles it automatically
 dc360 August 11, 2012