Number of transformations until repeat

up vote
12
down vote

favorite

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

code-golf

share|improve this question

edited yesterday

asked yesterday

mroman

977511

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Are you sure such a "closed formula" exists?
  – Todd Sewell
  20 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  "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
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is the 3rd example correct? I see 3,0,1,2 should transform to 2,3,0,1
  – FireCubez
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It's the number of transformations before a repeat.
  – mroman
  26 mins ago
  

  
  
  
  

 | 
show 1 more comment

up vote
12
down vote

favorite

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

code-golf

share|improve this question

edited yesterday

asked yesterday

mroman

977511

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Are you sure such a "closed formula" exists?
  – Todd Sewell
  20 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  "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
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is the 3rd example correct? I see 3,0,1,2 should transform to 2,3,0,1
  – FireCubez
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It's the number of transformations before a repeat.
  – mroman
  26 mins ago
  

  
  
  
  

 | 
show 1 more comment

up vote
12
down vote

favorite

up vote
12
down vote

favorite

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

code-golf

share|improve this question

edited yesterday

asked yesterday

mroman

977511

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

code-golf

code-golf

share|improve this question

edited yesterday

asked yesterday

mroman

977511

share|improve this question

edited yesterday

asked yesterday

mroman

977511

share|improve this question

share|improve this question

edited yesterday

edited yesterday

edited yesterday

asked yesterday

mroman

977511

asked yesterday

mroman

977511

asked yesterday

mroman

977511

977511

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Are you sure such a "closed formula" exists?
  – Todd Sewell
  20 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  "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
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is the 3rd example correct? I see 3,0,1,2 should transform to 2,3,0,1
  – FireCubez
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It's the number of transformations before a repeat.
  – mroman
  26 mins ago
  

  
  
  
  

 | 
show 1 more comment

• 
  
  
  

  
  

  
  
  
  
  
  

  
  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
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Are you sure such a "closed formula" exists?
  – Todd Sewell
  20 hours ago
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  "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
  6 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Is the 3rd example correct? I see 3,0,1,2 should transform to 2,3,0,1
  – FireCubez
  3 hours ago
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It's the number of transformations before a repeat.
  – mroman
  26 mins ago
  

  
  
  
  

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
yesterday

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
yesterday

Are you sure such a "closed formula" exists?
– Todd Sewell
20 hours ago

Are you sure such a "closed formula" exists?
– Todd Sewell
20 hours ago

"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
6 hours ago

"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
6 hours ago

Is the 3rd example correct? I see 3,0,1,2 should transform to 2,3,0,1
– FireCubez
3 hours ago

Is the 3rd example correct? I see 3,0,1,2 should transform to 2,3,0,1
– FireCubez
3 hours ago

It's the number of transformations before a repeat.
– mroman
26 mins ago

It's the number of transformations before a repeat.
– mroman
26 mins ago

 | 
show 1 more comment

9 Answers
9

active

oldest

votes

up vote
4
down vote

JavaScript (ES6), 54 bytes

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

Try it online!

share|improve this answer

answered yesterday

Arnauld

69k584291

• 
  
  
  

  
  

  
  
  
  
  
  

  
  What does do on a function?
  – mroman
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  A function is an object. So, g[a] can be used on it to access the property a.
  – Arnauld
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Ah I see. You're using g to store the state in.
  – mroman
  yesterday
  

  
  
  
  

add a comment | 

up vote
4
down vote

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!

share|improve this answer

answered yesterday

Erik the Outgolfer

30.7k429102

add a comment | 

up vote
3
down vote

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.

share|improve this answer

edited 23 hours ago

answered yesterday

lirtosiast

15.4k436104

add a comment | 

up vote
3
down vote

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 

share|improve this answer

edited 21 hours ago

answered 22 hours ago

nimi

30.8k31985

add a comment | 

up vote
3
down vote

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

share|improve this answer

edited 8 hours ago

answered 22 hours ago

Jo King

19.2k244102

add a comment | 

up vote
2
down vote

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.

share|improve this answer

edited 16 hours ago

answered 20 hours ago

Jonah

1,921816

add a comment | 

up vote
1
down vote

Jelly, 6 bytes

Ṛị$ƬL’

Try it online!

1-indexed.

share|improve this answer

edited yesterday

answered yesterday

Erik the Outgolfer

30.7k429102

add a comment | 

up vote
1
down vote

Dyalog APL, 29 28 27 bytes

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

Takes boxed arrays. Will trainify and explain later.

Try it here as a test suite.

share|improve this answer

edited 13 hours ago

answered 19 hours ago

lirtosiast

15.4k436104

add a comment | 

up vote
0
down vote

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!

share|improve this answer

answered 22 hours ago

Οurous

5,77311031

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "200"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f176196%2fnumber-of-transformations-until-repeat%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

9 Answers
9

active

oldest

votes

9 Answers
9

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
4
down vote

JavaScript (ES6), 54 bytes

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

Try it online!

share|improve this answer

answered yesterday

Arnauld

69k584291

• 
  
  
  

  
  

  
  
  
  
  
  

  
  What does do on a function?
  – mroman
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  A function is an object. So, g[a] can be used on it to access the property a.
  – Arnauld
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Ah I see. You're using g to store the state in.
  – mroman
  yesterday
  

  
  
  
  

add a comment | 

up vote
4
down vote

JavaScript (ES6), 54 bytes

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

Try it online!

share|improve this answer

answered yesterday

Arnauld

69k584291

• 
  
  
  

  
  

  
  
  
  
  
  

  
  What does do on a function?
  – mroman
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  A function is an object. So, g[a] can be used on it to access the property a.
  – Arnauld
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Ah I see. You're using g to store the state in.
  – mroman
  yesterday
  

  
  
  
  

add a comment | 

up vote
4
down vote

up vote
4
down vote

JavaScript (ES6), 54 bytes

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

Try it online!

share|improve this answer

answered yesterday

Arnauld

69k584291

JavaScript (ES6), 54 bytes

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

Try it online!

share|improve this answer

answered yesterday

Arnauld

69k584291

share|improve this answer

share|improve this answer

answered yesterday

Arnauld

69k584291

answered yesterday

Arnauld

69k584291

answered yesterday

Arnauld

69k584291

69k584291

• 
  
  
  

  
  

  
  
  
  
  
  

  
  What does do on a function?
  – mroman
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  A function is an object. So, g[a] can be used on it to access the property a.
  – Arnauld
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Ah I see. You're using g to store the state in.
  – mroman
  yesterday
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  What does do on a function?
  – mroman
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  A function is an object. So, g[a] can be used on it to access the property a.
  – Arnauld
  yesterday
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Ah I see. You're using g to store the state in.
  – mroman
  yesterday
  

  
  
  
  

What does do on a function?
– mroman
yesterday

What does do on a function?
– mroman
yesterday

A function is an object. So, g[a] can be used on it to access the property a.
– Arnauld
yesterday

A function is an object. So, g[a] can be used on it to access the property a.
– Arnauld
yesterday

Ah I see. You're using g to store the state in.
– mroman
yesterday

Ah I see. You're using g to store the state in.
– mroman
yesterday

add a comment | 

up vote
4
down vote

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!

share|improve this answer

answered yesterday

Erik the Outgolfer

30.7k429102

add a comment | 

up vote
4
down vote

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!

share|improve this answer

answered yesterday

Erik the Outgolfer

30.7k429102

add a comment | 

up vote
4
down vote

up vote
4
down vote

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!

share|improve this answer

answered yesterday

Erik the Outgolfer

30.7k429102

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!

share|improve this answer

answered yesterday

Erik the Outgolfer

30.7k429102

share|improve this answer

share|improve this answer

answered yesterday

Erik the Outgolfer

30.7k429102

answered yesterday

Erik the Outgolfer

30.7k429102

answered yesterday

Erik the Outgolfer

30.7k429102

30.7k429102

add a comment | 

add a comment | 

up vote
3
down vote

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.

share|improve this answer

edited 23 hours ago

answered yesterday

lirtosiast

15.4k436104

add a comment | 

up vote
3
down vote

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.

share|improve this answer

edited 23 hours ago

answered yesterday

lirtosiast

15.4k436104

add a comment | 

up vote
3
down vote

up vote
3
down vote

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.

share|improve this answer

edited 23 hours ago

answered yesterday

lirtosiast

15.4k436104

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.

share|improve this answer

edited 23 hours ago

answered yesterday

lirtosiast

15.4k436104

share|improve this answer

share|improve this answer

edited 23 hours ago

edited 23 hours ago

edited 23 hours ago

answered yesterday

lirtosiast

15.4k436104

answered yesterday

lirtosiast

15.4k436104

answered yesterday

lirtosiast

15.4k436104

15.4k436104

add a comment | 

add a comment | 

up vote
3
down vote

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 

share|improve this answer

edited 21 hours ago

answered 22 hours ago

nimi

30.8k31985

add a comment | 

up vote
3
down vote

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 

share|improve this answer

edited 21 hours ago

answered 22 hours ago

nimi

30.8k31985

add a comment | 

up vote
3
down vote

up vote
3
down vote

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 

share|improve this answer

edited 21 hours ago

answered 22 hours ago

nimi

30.8k31985

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 

share|improve this answer

edited 21 hours ago

answered 22 hours ago

nimi

30.8k31985

share|improve this answer

share|improve this answer

edited 21 hours ago

edited 21 hours ago

edited 21 hours ago

answered 22 hours ago

nimi

30.8k31985

answered 22 hours ago

nimi

30.8k31985

answered 22 hours ago

nimi

30.8k31985

30.8k31985

add a comment | 

add a comment | 

up vote
3
down vote

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

share|improve this answer

edited 8 hours ago

answered 22 hours ago

Jo King

19.2k244102

add a comment | 

up vote
3
down vote

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

share|improve this answer

edited 8 hours ago

answered 22 hours ago

Jo King

19.2k244102

add a comment | 

up vote
3
down vote

up vote
3
down vote

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

share|improve this answer

edited 8 hours ago

answered 22 hours ago

Jo King

19.2k244102

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

share|improve this answer

edited 8 hours ago

answered 22 hours ago

Jo King

19.2k244102

share|improve this answer

share|improve this answer

edited 8 hours ago

edited 8 hours ago

edited 8 hours ago

answered 22 hours ago

Jo King

19.2k244102

answered 22 hours ago

Jo King

19.2k244102

answered 22 hours ago

Jo King

19.2k244102

19.2k244102

add a comment | 

add a comment | 

up vote
2
down vote

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.

share|improve this answer

edited 16 hours ago

answered 20 hours ago

Jonah

1,921816

add a comment | 

up vote
2
down vote

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.

share|improve this answer

edited 16 hours ago

answered 20 hours ago

Jonah

1,921816

add a comment | 

up vote
2
down vote

up vote
2
down vote

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.

share|improve this answer

edited 16 hours ago

answered 20 hours ago

Jonah

1,921816

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.

share|improve this answer

edited 16 hours ago

answered 20 hours ago

Jonah

1,921816

share|improve this answer

share|improve this answer

edited 16 hours ago

edited 16 hours ago

edited 16 hours ago

answered 20 hours ago

Jonah

1,921816

answered 20 hours ago

Jonah

1,921816

answered 20 hours ago

Jonah

1,921816

1,921816

add a comment | 

add a comment | 

up vote
1
down vote

Jelly, 6 bytes

Ṛị$ƬL’

Try it online!

1-indexed.

share|improve this answer

edited yesterday

answered yesterday

Erik the Outgolfer

30.7k429102

add a comment | 

up vote
1
down vote

Jelly, 6 bytes

Ṛị$ƬL’

Try it online!

1-indexed.

share|improve this answer

edited yesterday

answered yesterday

Erik the Outgolfer

30.7k429102

add a comment | 

up vote
1
down vote

up vote
1
down vote

Jelly, 6 bytes

Ṛị$ƬL’

Try it online!

1-indexed.

share|improve this answer

edited yesterday

answered yesterday

Erik the Outgolfer

30.7k429102

Jelly, 6 bytes

Ṛị$ƬL’

Try it online!

1-indexed.

share|improve this answer

edited yesterday

answered yesterday

Erik the Outgolfer

30.7k429102

share|improve this answer

share|improve this answer

edited yesterday

edited yesterday

edited yesterday

answered yesterday

Erik the Outgolfer

30.7k429102

answered yesterday

Erik the Outgolfer

30.7k429102

answered yesterday

Erik the Outgolfer

30.7k429102

30.7k429102

add a comment | 

add a comment | 

up vote
1
down vote

Dyalog APL, 29 28 27 bytes

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

Takes boxed arrays. Will trainify and explain later.

Try it here as a test suite.

share|improve this answer

edited 13 hours ago

answered 19 hours ago

lirtosiast

15.4k436104

add a comment | 

up vote
1
down vote

Dyalog APL, 29 28 27 bytes

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

Takes boxed arrays. Will trainify and explain later.

Try it here as a test suite.

share|improve this answer

edited 13 hours ago

answered 19 hours ago

lirtosiast

15.4k436104

add a comment | 

up vote
1
down vote

up vote
1
down vote

Dyalog APL, 29 28 27 bytes

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

Takes boxed arrays. Will trainify and explain later.

Try it here as a test suite.

share|improve this answer

edited 13 hours ago

answered 19 hours ago

lirtosiast

15.4k436104

Dyalog APL, 29 28 27 bytes

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

Takes boxed arrays. Will trainify and explain later.

Try it here as a test suite.

share|improve this answer

edited 13 hours ago

answered 19 hours ago

lirtosiast

15.4k436104

share|improve this answer

share|improve this answer

edited 13 hours ago

edited 13 hours ago

edited 13 hours ago

answered 19 hours ago

lirtosiast

15.4k436104

answered 19 hours ago

lirtosiast

15.4k436104

answered 19 hours ago

lirtosiast

15.4k436104

15.4k436104

add a comment | 

add a comment | 

up vote
0
down vote

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!

share|improve this answer

answered 22 hours ago

Οurous

5,77311031

add a comment | 

up vote
0
down vote

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!

share|improve this answer

answered 22 hours ago

Οurous

5,77311031

add a comment | 

up vote
0
down vote

up vote
0
down vote

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!

share|improve this answer

answered 22 hours ago

Οurous

5,77311031

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!

share|improve this answer

answered 22 hours ago

Οurous

5,77311031

share|improve this answer

share|improve this answer

answered 22 hours ago

Οurous

5,77311031

answered 22 hours ago

Οurous

5,77311031

answered 22 hours ago

Οurous

5,77311031

5,77311031

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f176196%2fnumber-of-transformations-until-repeat%23new-answer', 'question_page');
}
);

Post as a guest

Name

Email

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Name

Name

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

Email

Required, but never shown

This page is only for reference, If you need detailed information, please check here