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. – mroman Nov 18 at 20:04
  • Are you sure such a "closed formula" exists? – Todd Sewell Nov 18 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... – Peter Taylor Nov 19 at 14:24
  • Is the 3rd example correct? I see 3,0,1,2 should transform to 2,3,0,1 – FireCubez Nov 19 at 17:02
  • It's the number of transformations before a repeat. – mroman Nov 19 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? – mroman Nov 18 at 20:24
  • A function is an object. So, g[a] can be used on it to access the property a. – Arnauld Nov 18 at 20:27
  • Ah I see. You're using g to store the state in. – mroman Nov 18 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, 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.

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 

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

Jelly, 6 bytes

Ṛị$ƬL’

Try it online!

1-indexed.

Dyalog APL, 29 28 27 bytes

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

Takes boxed arrays. Will trainify and explain later.

Try it here as a test suite.

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!

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.