Given a sequence of integers or to be more specific a permutation of 0..N
transform this sequence as following:
- output[x] = reverse(input[input[x]])
- repeat
For example: [2,1,0]
becomes [0,1,2]
and reversed is [2,1,0]
. [0,2,1]
becomes [0,1,2]
and reversed [2,1,0]
.
Example 1
In: 0 1 2
S#1: 2 1 0
S#2: 2 1 0
Output: 1
Example 2
In: 2 1 0
S#1: 2 1 0
Output: 0
Example 3
In: 3 0 1 2
S#1: 1 0 3 2
S#2: 3 2 1 0
S#3: 3 2 1 0
Output: 2
Example 4
In: 3 0 2 1
S#1: 0 2 3 1
S#2: 2 1 3 0
S#3: 2 0 1 3
S#4: 3 0 2 1
Output: 3
Your task is to define a function (or program) that takes a permutation of
integers 0..N
and returns (or outputs) the number of steps until a permutation occurs that has already occured. If X
transforms to X
then the output should be zero, If X
transforms to Y
and Y
to X
(or Y
) then the output should be 1.
Y -> Y: 0 steps
Y -> X -> X: 1 step
Y -> X -> Y: 1 step
A -> B -> C -> D -> C: 3 steps
A -> B -> C -> D -> A: 3 steps
A -> B -> C -> A: 2 steps
A -> B -> C -> C: 2 steps
A -> B -> C -> B: also 2 steps
Testcases:
4 3 0 1 2 -> 0 3 4 1 2 -> 4 3 2 1 0 -> 4 3 2 1 0: 2 steps
4 3 2 1 0 -> 4 3 2 1 0: 0 steps
4 3 1 2 0 -> 4 1 3 2 0 -> 4 3 2 1 0 -> 4 3 2 1 0: 2 steps
1 2 3 0 4 -> 4 1 0 3 2 -> 0 3 4 1 2 -> 4 3 2 1 0 -> 4 3 2 1 0: 3 steps
5 1 2 3 0 4 -> 0 5 3 2 1 4 -> 1 5 3 2 4 0 -> 1 4 3 2 0 5 ->
5 1 3 2 0 4 -> 0 5 3 2 1 4: 4 steps
If your language doesn't support "functions" you may assume that the sequence is given as whitespace seperated list of integers such as 0 1 2
or 3 1 0 2
on a single line.
Fun facts:
- the sequence 0,1,2,3,..,N will always transform to N,...,3,2,1,0
- the sequence N,..,3,2,1,0 will always transform to N,..,3,2,1,0
- the sequence 0,1,3,2,...,N+1,N will always transform to N,...,3,2,1,0
Bonus task: Figure out a mathematical formula.
Optional rules:
- If your language's first index is 1 instead of 0 you can use permutations
1..N
(you can just add one to every integer in the example and testcases).
3,0,1,2
should transform to2,3,0,1
\$\endgroup\$