On 6/11/07, Oleg Kobchenko <[EMAIL PROTECTED]> wrote:
Given a scrambled line, return the shortest sequence of
rotations to restore the original position.
Examples:
solve 1 3 2 6 5 4
1 2 1
solve 5 6 2 1 4 3
0 2
solve 6 5 4 1 2 3
0 1 2
Here's a brute force approach:
init=: 3 :0
n=.,:1 2 3 4 5 6
o=. 3 2 1 0 4 5,0 4 3 2 1 5,:0 1 5 4 3 2
p=. o (] ~.@, ,/@:({"1/))^:_ n
r=. a:#~#p
b=.1{.~#p
while.0 <#k=.I.-.b do.
j=. p i. o {"1/ b#p
i=. 0 1 2,~&.>~/r{~I.b
ok=.,j e.k
r=.(ok#&,i) (ok#&,j)} r
b=. 1 (,j)} b
assert. (-:~.) b#r
end.
solve=: r {::~ p i. ]
r
)
init''
This could probably be made simpler, but I think it's fast enough.
Note also that Roger's solution provides answers of the same length
in all cases other than 1 2 3 4 5 6.
--
Raul
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
