# Is it stuck in a counting loop? [duplicate]

Given a list of non-negative integers the function $$\f\$$ replaces every integer with the number of identical integers preceding it (not necessarily contiguously). So

f [1,1,2,2,1,3,3] = [1,2,1,2,3,1,2]


We will say that a list, $$\X\$$, is in a loop if there is some positive integer $$\n\$$ such that $$\f^n X = X\$$. That is you can apply the function to $$\X\$$ some number of times to arrive at $$\X\$$.

Your task is to take a list as input and determine if that list is in a loop. You should output one of two consistent values, one if it is in a loop and the other if it is not.

This is code-golf. The goal is to minimize the size of your source code as measured in bytes.

A note: There are other ways to formulate this condition.

## Test cases

[2,2] -> False
[1,1] -> True
[1,2] -> True
[1,1,2,2,3,3] -> True
[1,2,3,1,4,2,5,3] -> True
[1,2,1,3,1,2] -> True
[1,2,1,3,1,3,4,6] -> False
[1,2,2,3] -> False

• @Arnauld I think it is not the length of the run of identical integers, but the total number in the list. So the third element should be [1, 1, 2, 2, 3, 3]. Perhaps an example with the numbers not being grouped would help. Commented Dec 14, 2023 at 15:27
• It looks like the true ones all have a cycle length of 2, and the false ones converge to something with a cycle length of 2 also, just not including the original input. i don't see how to prove it though -- is it always true? Commented Dec 14, 2023 at 16:59
• @Jonah It is always true. I found it difficult to prove, but there's a stronger claim that's easier to prove, and may also be helpful to golfing. Commented Dec 14, 2023 at 17:05
• @WheatWizard aren't we kind of transposing Young diagrams in the loop? Commented Dec 14, 2023 at 19:13
• It looks like the condition is that the input has to be a stackable sequence (1-indexed)? Definitely the result of f is stackable, so if the initial list is not, we're never looping back to it. And if it's stackable, the loop length is 2, except for the input [1] or [] it's 1.
– xnor
Commented Dec 14, 2023 at 19:51

# J, 14 bytes

-:(1#.]=]\)^:2


Try it online!

This uses the fact I conjectured in the comments, which WheatWizard confirmed is true:

It looks like the true ones all have a cycle length of 2, and the false ones converge to something with a cycle length of 2 also, just not including the original input.

So, we simply apply the transformation twice, and check if the result matches the input.

# Jelly, 7 bytes

ċṪ‘ƊƤ⁺⁼


Try it online!

A monadic link taking a list of integers and returning 1 if a loop and 0 if not. Uses @Jonah’s observation that we only need to apply the transformation twice and check whether we get back to where we started.

## Previous solution, 9 bytes

ċṪ‘ƊƤ⁺ÐL⁼


Try it online!

A monadic link taking a list of integers and returning 1 if a loop and 0 if not.

## Explanation

ċṪ‘ƊƤ     | For each prefix, count the number of times the popped tail appears and then increment by 1
⁺ÐL  | Repeat this again until a value is seen for the second time, returning the last value that has not been seen before
⁼ | Check whether equal to the original argument


# Python3, 115 bytes

def f(a):
q=[a]
while(l:=[sum(k==j for k in q[-1][:i+1])for i,j in enumerate(q[-1])])not in q:q+=[l]
return l==a


Try it online!

# JavaScript (ES6), 59 bytes

Naive implementation. Returns a Boolean value.

a=>(g=a=>g[a]?a+""==b:g(g[a]=a.map(p=v=>p[v]=-~p[v])))(b=a)


Try it online!

### Commented

a => (                // a[] = input array
g =                 // g is a recursive function taking ...
a =>                // ... the current state a[] of the array
g[a] ?              // if we've encountered a[] before:
a + "" == b       //   stop and return true if this is the original array
:                   // else:
g(                //   do a recursive call:
g[a] =          //     mark a[] as encountered
a.map(p =       //     p is on object used to count 'preceding' values
v =>            //     for each value v in a[]:
p[v] = -~p[v] //       increment p[v]
)               //     end of map()
)                 //   end of recursive call
)(b = a)              // initial call to g with a[] saved in b[]


# JavaScript (ES6), 45 bytes

Optimized version using Jonah's conjecture.

a=>a+""==(g=a=>a.map(p=v=>p[v]=-~p[v]))(g(a))


Try it online!

# JavaScript (ES6), 41 bytes

Further optimized, knowing that we're actually looking for a stackable sequence as pointed out by xnor. This is basically a 1-indexed version of my answer to the other challenge.

a=>a.every(k=>a[a[-k]=-~a[-k--],-k]--|!k)


Try it online!