Este desafío planteó un algoritmo para codificar un entero ncomo otro entero r. Lo que sigue es una explicación sucinta de ese algoritmo, utilizando n=60como ejemplo.

El algoritmo original

• Primero, codificamos el número como una cadena de corchetes.

  • Si n = 1, devuelve una cadena vacía.
  • De lo contrario, tomamos nla descomposición primaria ordenada de forma ascendente y reemplazamos cada elemento con su índice principal (1 índice) entre paréntesis.60 = 2*2*3*5 => [1][1][2][3]
  • Haga esto de forma recursiva hasta que todo lo que tengamos sean paréntesis. [1][1][2][3] => [][][[1]][[2]] => [][][[]][[[1]]] => [][][[]][[[]]]

• Una vez que tenemos nuestra cadena de corchetes, la convertimos en un entero con el siguiente proceso.

  • Convierta cada soporte de apertura en ay 1cada soporte de cierre en a 0.[][][[]][[[]]] => 10101100111000
  • Elimine todos los 0s finales y el final 1.10101100111000 => 1010110011
  • Convertir la cadena final de 0s y 1s de binario a un entero.1010110011 => 691

Decodificando esta codificación

Una propiedad interesante de este algoritmo es que es no sobreyectiva. No todos los enteros pueden ser el resultado de esta codificación.

• En primer lugar, la representación binaria del resultado rdebe estar balance-ableen que el número de 0s nunca debe exceder el número de 1s. Un breve caso de prueba de falsey es 4, que está 100en binario.
• En segundo lugar, los corchetes en la representación binaria deben estar sorted ascendingcuando los s finales 1y finales 0se agregan una vez más. Un breve caso de prueba de falsey es 12 <= 1100 <= 110010 <= (())().

Sin embargo, solo determinar si un número es decodificable de esta manera sería un pequeño desafío. En cambio, el desafío consiste en decodificar repetidamente una entrada dada hasta que se alcance un número que no se puede decodificar o un ciclo, y devolver la secuencia de números resultante .

El reto

• Dado un número 1 <= r <= 2**20 = 1048576, devuelve la secuencia de números que se r decodifica sucesivamente , comenzando por rsí mismo y terminando con un número o ciclo no decodificable.
• Si se proporciona un número que no se puede decodificar como entrada, como 4o 12, devolverá una lista que solo contiene la entrada.
• Una secuencia que termina en un ciclo debe indicarse de alguna manera, ya sea agregando o anteponiendo un marcador (elija un entero no positivo, cadena, lista, etc. como marcador, pero manténgalo consistente), o repitiendo el ciclo en de alguna manera (repitiendo el primer elemento, repitiendo todo el ciclo, repitiendo infinitamente, etc.).
• En el caso de que cualquiera de las secuencias sea infinita (por ejemplo, aumentando para siempre), considérelo comportamiento indefinido.
• Este es el código de golf. El menor número de bytes gana.

Un ejemplo trabajado de decodificación

   1 -> 1 -> 1100 -> [[]] -> [2] -> 3
-> 3 -> 11 -> 111000 -> [[[]]] -> [[2]] -> [3] -> 5
-> 5 -> 101 -> 101100 -> [][[]] -> 2*[2] -> 2*3 -> 6
-> 6 -> 110 -> 110100 -> [[][]] -> [2*2] -> [4] -> 7
-> 7 -> 111 -> 11110000 -> [[[[]]]] -> [[[2]]] -> [[3]] -> [5] -> 11
-> 11 -> 1011 -> 10111000 -> [][[[]]] -> 2*[[2]] -> 2*[3] -> 2*5 -> 10
-> 10 -> 1010 -> 101010 -> [][][] -> 2*2*2 -> 8
-> 8 -> 1000  ERROR: Unbalanced string

Casos de prueba

4 -> [4]
12 -> [12]
1 -> [1, 3, 5, 6, 7, 11, 10, 8]
2 -> [2, 4]
13 -> [13, 13]    # cycle is repeated once
23 -> [23, 22, 14, 17]
51 -> [51, 15, 31, 127, 5381]
691 -> [691, 60]
126 -> [126, 1787, 90907]
1019 -> [1019, 506683, 359087867, 560390368728]

Las sugerencias y comentarios para este desafío son bienvenidos. ¡Buena suerte y buen golf!

Python 3 , 379 358 339 337 327 310 304 bytes

Conjetura: ¿Es 13el único número que conducirá a un ciclo? (No hay excepciones menores de 10 ^6. )

Se corrigió un error y -7 bytes gracias a Sherlock9 .
-3 bytes gracias a Jonathan Frech .
-16 bytes gracias a los ovs .
-6 bytes gracias al Sr. Xcoder .

Si hay un ciclo, se repetirá todo el ciclo.

def p(a,x=0,n=1):
 while a:x+=1;a-=n%x;n*=x*x
 return x
def g(a):
 c=i=0
 for v in a:
  c+=int(v)*2-1
  if c<0:return 0,0
  if c<1:break
  i+=1
 if a:x=p(g(a[1:i])[0]);b,c=g(a[i+1:]);return(x>c>0)*(0,0)or(x*b,x)
 return 1,0
def f(a):
 x=a,
 while(x.count(a)<3)*a:a,t=g(bin(a-~a)[2:]);x+=a,
 return x[:-1]

Pruébalo en línea!

Explicación:

def p(a,x=0,n=1):     # return the a-th prime
 while a:             # magical way to enumerate primes
  x+=1
  a-=n%x
  n*=x*x
 return x

def g(a):             # decode a 0/1 string
 c=i=0
 for v in a:
  c+=int(v)*2-1       # +1 if 1, -1 if 0
  if c<0: return(0,0) # c<0: unbalanced parentheses
  if c<1: break       # first outermost parentheses
  i+=1
 if a:
   x=p(g(a[1:i])[0])  # recursive solve those inside the parentheses ...
   b,c=g(a[i+1:])     # and the remaining
   if x>c and c:      # if not ascending
    return (0,0)
   return (x*b,x)     # return (result, value of first closed parentheses)
 return (1,0)         # empty string

def f(a):
 x=a,
 while a and x.count(a)<3: # detect non-decodable or cycle
  a,t=g(bin(a-~a)[2:])     # a-~a is a*2+1
  x+=a,
 return x[:-1]

Pyth, 62 bytes

L?b**FKme.fP_Zyd)bSIK1fTseB.u.xyvs@L,"],"\[++JjN2 1m0h-/J1/J00

Banco de pruebas

Indica un ciclo repitiendo el número final.

L?b**FKme.fP_Zyd)bSIK1    Define y to decode from list format. 0 if invalid.

fTseB.u.xyvs@L,"],"\[++JjN2 1m0h-/J1/J00
     .u                                     Repeat the following until it cycles
                                            Collecting the values in a list.
                     ++JjN2 1m0h-/J1/J0     Convert the number to expanded binary
            @L,"],"\[                       Map 0 to "],", 1 to "["
           s                                Flatten to a string.
          v                                 Evaluate as a Python object.
       .x                              0    If evaluation fails, return 0.
         y                                  Otherwise decode.
  seB                                       Duplicate the final number
fT                                          Remove all 0s.