Number of transformations until repeat

Question

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).

Answer 1

JavaScript (ES6), 54 bytes

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

Try it online!

Answer 2

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!

Answer 3

Pyth, 10 9 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.

Test suite.

Answer 4

Haskell, 52 bytes

([]#)
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.

([]#)                -- start with an empty list of seen p.s 

Answer 5

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

Answer 6

J, 33 27 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.

Answer 7

Jelly, 6 bytes

Ṛị$ƬL’

Try it online!

1-indexed.

Answer 8

Dyalog APL, 29 28 27 bytes

¯2∘+∘≢{⍵,⍨⊂⌽(⍋⍳⊢)⊃⍵}⍣{⍺≢∪⍺}

Takes boxed arrays. Will trainify and explain later.

Try it here as a test suite.

Answer 9

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!