# Number of transformations until repeat

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).
• I meant more like a "closed formula" such as $f(a_{0},a_{1},a_{...}} = a_{0}^a_{1}+...$ where $a_{i}$ is the i-th element in the given sequence. Nov 18, 2018 at 20:04
• Are you sure such a "closed formula" exists? Nov 18, 2018 at 23:54
• "returns (or outputs) the number of steps until a permutation occurs that has already occured." This is inconsistent with just about everything that follows it. For a start, it makes a return value of 0 impossible... Nov 19, 2018 at 14:24
• Is the 3rd example correct? I see 3,0,1,2 should transform to 2,3,0,1
– kepe
Nov 19, 2018 at 17:02
• It's the number of transformations before a repeat. Nov 19, 2018 at 20:14

# JavaScript (ES6), 54 bytes

a=>~(g=a=>g[a]||~-g(g[a]=a.map(i=>a[i]).reverse()))(a)


Try it online!

• What does [] do on a function? Nov 18, 2018 at 20:24
• A function is an object. So, g[a] can be used on it to access the property a. Nov 18, 2018 at 20:27
• Ah I see. You're using g to store the state in. Nov 18, 2018 at 20:29

# Python 2, 67 bytes

f=lambda l,*h:len(h)-1if l in h else f([l[i]for i in l][::-1],l,*h)


Try it online!

# Pyth, 109 8 bytes

tl.u@LN_


Explanation:

t               One less than
l              the number of values achieved by
.u            repeating the following lambda N until already seen value:
@LN_N         composing permutation N with its reverse
Q      starting with the input.


([]#)
a#x|elem x a= -1|n<-x:a=1+n#reverse(map(x!!)x)


Try it online!

a # x                -- function '#' takes a list of all permutations
-- seen so far (-> 'a') and the current p. (-> 'x')
| elem x a = -1    -- if x has been seen before, return -1
| n<-x:a =         -- else let 'n' be the new list of seen p.s and return
1 +              -- 1 plus
n #           -- a recursive call of '#' with the 'n' and
reverse ...  -- the new p.



# Perl 6, 44 35 bytes

-9 bytes thanks to nwellnhof

{($_,{.[[R,] |$_]}...{%.{$_}++})-2}  Try it online! ### Explanation: { } # Anonymous code block ... # Create a sequence where:$_,  # The first element is the input list
{.[[R,] |$_]} # Subsequent elements are the previous element reverse indexed into itself { } # Until %.{$_}       # The index of the listt in an anonymous hash is non-zero
++     # Then post increment it
(                            )-2  # Return the length of the sequence minus 2


# J, 3327 26 bytes

-7 thanks to bubbler

_1(+~:i.0:)|.@C.~^:(<@!@#)


Try it online!

## how

original explanation. my last improvement only changes the piece which finds "the index of the first element we've seen already". it now uses the "nub sieve" to do it in fewer bytes.

1 <:@i.~ [: ({: e. }:)\ |.@C.~^:(<@!@#)
|.@C.~          NB. self-apply permutation and reverse
^:        NB. this many times:
(<@!@#) NB. the box of the factorial of the
NB. the list len.  this guarantees
NB. we terminate, and the box means
NB. we collect all the results
[: ({: e. }:)\                 NB. apply this to those results:
\                 NB. for each prefix
{: e. }:                   NB. is the last item contained in
NB. the list of previous items?
1 <:@i.~                                NB. in that result find:
1    i.~                                NB. the index of the first 1
<:@                                   NB. and subtract 1


Note the entire final phrase 1<:@i.~[:({:e.}:)\ is devoted to finding "the index of the first element which has already been seen." This seems awfully long for obtaining that, but I wasn't able to golf it more. Suggestions welcome.

Ṛị$ƬL’  Try it online! 1-indexed. # Dyalog APL, 2928 27 bytes ¯2∘+∘≢{⍵,⍨⊂⌽(⍋⍳⊢)⊃⍵}⍣{⍺≢∪⍺}  Takes boxed arrays. Will trainify and explain later. # Clean, 90 bytes import StdEnv$l=length(until(\[h:t]=any((==)h)t)(\[h:t]=[reverse(map((!!)h)h),h:t])[l])-2


Try it online!