# First odd then even indices

Your task is to find out how often you need to "shuffle" a given list with the following operation until you get back the original list.

(1 2 3 4 5 6 7 8 9)
split it into the elements at odd and even indices
(1 3 5 7 9) (2 4 6 8)
concatenate these two list
(1 3 5 7 9 2 4 6 8)

Input: A list

Output: The number of iterations it takes until you get back the original list

## Examples

(1 2 3) -> (1 3 2) -> (1 2 3)               => 2
(1 2 3 4 3 2 1) -> (1 3 3 1 2 4 2) -> ...   => 3
(1 2 3 4 5 6 7 8 9 10) -> ...               => 6
(1 2 3 4 5 6 7 8 9 10 11) -> ...            => 10
"abab" -> "aabb" -> "abab"                  => 2
"Hello, World!" -> "Hlo ol!el,Wrd" -> ...   => 12
(1 0 1 1 0 0 0 1 1 1) -> ...                => 6
(1 0 0 1 1 1 0 0 0 0 1) -> ...              => 10
(1 1 1 1 1 1 1) -> (1 1 1 1 1 1 1)          => 1

## Rules

• You can use lists of any type (that supports at least two distinct values)
• You can assume the the list has at least two elements
• The odd/even indices are determined using 1-based indexing
• You have to apply the operation at least once
• If your language has a built-in for finding fixed points consider adding a non-builtin solution as well
• This is the shortest solution (per language) wins
• Can we assume that the list has more than one element? Commented Aug 21, 2023 at 8:39
• Related Commented Aug 21, 2023 at 22:22

# K (ngn/k), 12 bytes

#{x@<2!!#x}\

Try it online!

{ ... }\ Iterate until reaching the first value again (or a fixed point). Collect intermediate values.
2!!#x 2 mod range of length x. Sequence of alternating 0s and 1s the same length as x.
x@< Grade up, then index into x. Sorts x by that sequence.

# Length. Counts the number of intermediate results.

• "Iterate until reaching the first value again (or a fixed point)" -- Looks like the K builtin is much nicer than J's here. In J, only consecutive repeats count as a fixed point. In K, it sounds like at minimum "repeat consecutive" and "repeat first" trigger a break. What about "repeat some other intermediate value, but not consecitively"? Ie, stop when you see any previous value a 2nd time? (this makes the most sense to me) Commented Aug 20, 2023 at 18:33
• @Jonah intermediate values are not checked, which can be a pain when cycles don't include the initial value. I think the justification is that quadratic complexity could be unwanted/unexpected
– ovs
Commented Aug 20, 2023 at 19:02
• Right. Ideally, it would be configurable (via an adverb perhaps in J-land), and you could even configure the check to use something like a hash table. Commented Aug 20, 2023 at 19:10

# Thunno 2L, 4 bytes

µ¥zS
µ¥zḞ
µ¥^ḥ

Don't worry, the stack languages with single-byte uninterleave operators are going to be even shorter :P

lol

#### Explanation

# Implicit input

µ¥    # Collect while unique:

z   #  Uninterleave into two pieces
#   [1,2,3,4,5,6]  ->  [[1,3,5],[2,4,6]]
S  #  Then flatten the nested list
#   [[1,3,5],[2,4,6]]  ->  [1,3,5,2,4,6]
Ḟ  #  Alternative flatten built-in
#   [[1,3,5],[2,4,6]]  ->  [1,3,5,2,4,6]

^   #  Or, uninterleave and push separately
#   [1,2,3,4,5,6]  ->  [1,3,5] [2,4,6]
ḥ  #  Then concatenate the two lists
#   [1,3,5] [2,4,6]  ->  [1,3,5,2,4,6]

# Finally, the L flag takes the length
# Implicit output

# J, 26 24 bytes

i.~_:0}(\:2|#\)^:(3<@^#)

Try it online!

Accepts numeric lists

The maximum number of iterations until we return to the input is bounded by Landau's function $$\g(n)\$$, and it can be shown that:

$${\displaystyle g(n)\leq e^{n/e}}$$

For golf reasons, I simply round that to:

$${\displaystyle g(n)\leq 3^{n}}$$

and iterate that many times. Note I could trade bytes for efficiency here and iterate until I see the input again, but this approach was shorter.

• (\:2|#\) Apply the needed permutation -- equivalent to sorting down by 1 0 1 0...
• ^:(3<@^#) Do that $$\3^n\$$ times, saving results
• _:0} Convert the first item on the list, which is the input itself, to infinity, so that match will be skipped.
• i.~ Index of the input within that list.

# Jelly, 6 bytes

ŒœẎ$ƬL Try it online! Don't worry, the stack languages with single-byte uninterleave operators are going to be even shorter :P Ƭ Repeat while unique, collecting all results: Œœ Split into odd and even-indexed elements, Ẏ$      and concatenate.
L    How many results are there?

# 05AB1E, 8 bytes

vDÅ≠})Ùg

Try it online or verify all test cases (the test suite uses the faster alternative ι˜ instead of Å≠).

Explanation:

Although 05AB1E has an unshuffle builtin Å≠ (even though ι˜ does the same and is faster..), it unfortunately lacks a "Repeat until unique" builtin..

v     # Loop the (implicit) input-length amount of times:
D    #  Duplicate the current list
#  (which will be the implicit input-list in the first iteration)
Å≠  #  Unshuffle it
})    # After the loop: wrap all lists on the stack into a list
Ù   # Uniquify this list of lists
g  # Pop and push its length
# (which is output implicitly as result)

ι   #  Uninterleave it into a pair of lists
˜  #  Flatten it to a single list

=let(d,torow(A:A,3),_,lambda(_,a,n,sort(let(b,torow(wrapcols(a,2),3),if(and(b=d),n,_(_,b,1+n))))),_(_,d,1))

Put the input in cells A1:A and the formula in B1.

The formula is self-contained. Uses singularize(wrap()) like the Excel answer but does not depend on named functions or named ranges.

• Welcome to Code Golf, and nice answer! Commented Aug 22, 2023 at 15:34

# Python, 65 bytes

lambda s,j=1:j*((t:=s[:len(s)-1|1])==(t*2**j)[::2**j])or f(s,j+1)

Attempt This Online!

## How?

This is based on the observation that in zero-based indexing the reshuffle can be written as n -> 2n mod N where N is the largest odd number not greater than the length of the input. (If the length is even the last point is a fixed point, so it can be ignored.)

# Nekomata + -n, 6 bytes

ᶦ{ĭ,ᵖ≠

Attempt This Online!

Nekomata has a single-byte uninterleave operator, but still can't beat Jelly, because it doesn't have a "repeat while unique" operator.

ᶦ{ĭ,ᵖ≠
ᶦ{          Repeat until failure:
ĭ             Uniterleave
,            Join
ᵖ≠          Check if the result is unequal to the input

-n counts the number of iterations.

# Excel, 93 bytes

Define:

a as =$A$1# (7 bytes)

z as =LAMBDA(p,q,LET(x,TOCOL(WRAPROWS(p,2),2,1),y,q+1,IF(SUM(N(x<>a))=0,y,z(x,y)))) (79 bytes)

Within the worksheet: =z(a,0) (7 bytes)

$A$1# is a spilled, vertical range comprising the list entries.

# R, 70 bytes

f=\(x,l=0,y=c(x[!0:1],x[!1:0]),-=list)if(-y%in%l,0,1+f(y,c(l,-y)))

Attempt This Online!

# Ruby, 55 bytes

->l{k=*l;1.step.find{w=-2;l==k=k.map{k[w+=2]||k[w=1]}}}

Try it online!

• -1 byte by upgrading to 2.6 for endless range. Also, since you're reassigning instead of modifying k you can skip the splat and just do a shallow assignment at the start. Attempt This Online Commented Aug 21, 2023 at 20:54

# Vyxall, 31 bitsv2, 3.875 bytes

yJ)↲

Try it Online!

the stack languages with single-byte uninterleave operators are going to be even shorter

# R, 5452 51 bytes

Edit: -3 bytes thanks to @Dominic van Essen.

\(x,y=x){while(sd((y[]=matrix(y,2,,T))-x))T=T+1;+T}

Attempt This Online!

• Nice! What on earth was I thinking collecting all the intermediate values...? Doh! Well done. Commented Aug 21, 2023 at 10:19
• 52 bytes... Commented Aug 21, 2023 at 10:42
• 51 bytes...(y-x can never be all-the-same unless it's all-zero, I think...) Commented Aug 21, 2023 at 21:14
• @DominicvanEssen Nice observation! Commented Aug 22, 2023 at 4:43

# Charcoal, 27 bytes

⊞υθＷ‹№υθ²⊞υ⭆²Φ§υ±¹﹪⁺κν²Ｉ⊖Ｌυ

Try it online! Link is to verbose version of code. Only works on strings. Explanation:

⊞υθ

Push the string to the predefined empty list.

Ｗ‹№υθ²

Repeat until a second copy of the string is found.

⊞υ⭆²Φ§υ±¹﹪⁺κν²

Shuffle the most recent string and push it to the list.

Ｉ⊖Ｌυ

Output the number of shuffles taken.

28 bytes to work on strings or lists:

⊞υθＷ‹№υθ²⊞υΣＥ²Φ§υ±¹﹪⁺κν²Ｉ⊖Ｌυ

Attempt This Online! Link is to verbose version of code.

# sclin, 45 bytes

=$a$a"2/ tpose flat"itr1dp"$a !="tk* len1+ Try it here! Takes a list. For testing purposes: [1 2 3 4 5 6 7 8 9 10 11] ; =$a $a"2/ tpose flat"itr1dp"$a !="tk* len1+

NOTE: for string-based inputs, use e.g. ["a" "b" "a" "b"].

## Explanation

Prettified code:

=$a$a.
( 2/ tpose flat ) itr 1dp ( $a != ) tk* len 1+ • =$a $a Input list a • (...) itr generate infinite list from successive modifications of a... • 2/ tpose flat chunk into pairs, transpose, flatten • 1dp drop first item to prevent tk* from exiting early • ($a != ) tk* take while not equal to a
• len 1+ length + 1

# JavaScript (ES6), 64 bytes

Expects a list of positive integers.

a=>(g=a=>(g[a]^=i=-2)&&1+g(a.map(_=>a[!a[i+=2]|i%a.length])))(a)

Try it online!

### How?

We can apply the shuffle by doing:

a.map((_, i) => a[!a[i * 2] | i * 2 % a.length])

This code first collects all values at even (0-based) indices. When a[i * 2] is not defined anymore, it starts collecting values at odd indices.

For golfing reasons, we rather start with $$\i=-2\$$ and do:

a.map(_ => a[!a[i += 2] | i % a.length])

We stop as soon as the same array has been encountered twice and return the number of iterations.

# Arturo, 49 bytes

$->a[1x:a while[i:0arrange'x=>[i%2'i+1]x<>a][1+]] Try it!$->a[                         ; a function taking an input a
1                         ; push 1 -- this is our output (count)
x:a                       ; assign a to x
while[                    ; while...
i:0                   ; assign 0 to i
arrange'x=>[i%2'i+1]  ; sort x by its indices' parities
x<>a                  ; x doesn't equal a...
]                         ; end while predicate
[1+]                      ; ...then increment the output
]                             ; end function