Is it stuck in a counting loop? [duplicate]

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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!

Answer 4

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!