Un juego divertido para jugar si estás aburrido es el juego Diffy . Es un juego de un jugador que es bastante simple y puede consumir una gran parte de su tiempo.

El juego Diffy funciona de la siguiente manera: comienzas con una lista de enteros no negativos, en este ejemplo usaremos

3 4 5 8

Luego tomas la diferencia absoluta entre números adyacentes

 (8)  3   4   5   8
    5   1   1   3

Entonces repites. Repite hasta que se da cuenta de que ha entrado en un bucle. Y luego, generalmente, el juego comienza de nuevo desde el principio.

3 4 5 8
5 1 1 3
2 4 0 2
0 2 4 2
2 2 2 2
0 0 0 0
0 0 0 0

A menudo, el juego no tiene un objetivo, solo estás haciendo tiempo haciendo aritmética en tu cabeza. Sin embargo, cuando tengo el placer de jugar este juego, mi objetivo siempre es tratar de elegir un período e intentar construir un juego que se repita con ese período en particular.

No todos los juegos son periódicos, el ejemplo anterior no es periódico, por ejemplo, porque finalmente alcanza un juego con todos los ceros y, por lo tanto, nunca puede volver a su posición inicial. De hecho, parece que la gran mayoría de los juegos no son periódicos, por lo que los pocos juegos son una joya rara.

Dado un juego que se repite con un período en particular, es trivial hacer otro juego que se repita con el mismo período simplemente duplicando la secuencia. Por ejemplo el juego:

1 0 1

Se reproduce exactamente igual que el juego:

1 0 1 1 0 1

De hecho, podemos considerar que ambos son realmente el juego que se repite infinitamente:

... 1 0 1 ...

Los consideraremos un juego por el bien de este desafío.

De manera similar, multiplicar toda la secuencia por una constante también conservará trivialmente el período, por lo que una vez más vamos a contar dos juegos que difieren en un factor constante para ser el mismo juego.

Las cadenas infinitas ... 1 0 1 ...y ... 0 1 1 ...obviamente son la misma cadena desplazada por un carácter. No contaremos estos como juegos diferentes, pero cuando uno llegue al otro no se considerará el final del ciclo al determinar el período de un juego. Por ejemplo:

Los dos juegos

... 0 0 0 1 0 1 ...  = A
... 0 0 1 1 1 1 ...  = B
... 0 1 0 0 0 1 ...  = A << 4
... 1 1 0 0 1 1 ...  = B << 4
... 0 1 0 1 0 0 ...  = A << 2
... 1 1 1 1 0 0 ...  = B << 2

y

... 0 0 1 0 1 0 ...  = A << 1
... 0 1 1 1 1 0 ...  = B << 1
... 1 0 0 0 1 0 ...  = A << 5
... 1 0 0 1 1 1 ...  = B << 5
... 1 0 1 0 0 0 ...  = A << 3
... 1 1 1 0 0 1 ...  = B << 3

los dos son juegos con periodo 6. Ellos no comparten plazo con entre sí en todo momento de sus bucles (a diferencia ... 1 1 0 ..., y ... 1 0 1 ...que alcanzan entre sí) sino porque son versiones de sí cambiaron se consideran el mismo juego, cuando el conteo.

Reflejar (o invertir) una cadena infinita da esencialmente el mismo comportamiento, pero no necesariamente da el mismo período. Considere, por ejemplo,

... 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 ...

y su reflejo

... 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 ...

Si consideramos que la próxima generación se producirá en un punto intermedio entre los personajes:

... 0 0 0 1 0 0 1 1 0 1 0 1 1 1 1 ...
 ... 0 0 1 1 0 1 0 1 1 1 1 0 0 0 1 ...

... 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 ...
 ... 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 ...

entonces ambos habrían cambiado de posición por 3.5 elementos. Sin embargo, no consideramos que la próxima generación se produzca con ese desplazamiento de medio elemento, por lo que uno redondea a un cambio de 4 elementos dando un período de 15, y el otro redondea a un cambio de 3 elementos dando un período de 5.

Por esta razón, consideramos que una cadena asimétrica y su reflejo son distintos, aunque los ciclos son en cierto sentido isomórficos. Por supuesto, si forman parte del mismo ciclo, solo cuenta como un ciclo.

Con estas restricciones, un poco de matemática puede mostrar que, de hecho, hay un número finito de ciclos Diffy con un período finito determinado. Además, cada cadena infinita con un período finito es una repetición infinita de una cadena finita.

Tenga en cuenta que las cadenas pueden ser más grandes o más cortas que los períodos. Por ejemplo, hay una cadena de longitud 5 con el período 15 y una cadena de longitud 15 con el período 5. Todas las cadenas con el período 19 tienen una longitud de 9709.

Tarea

Dado un número ntal que n es mayor que 1 a través de métodos de entrada estándar, determine el número de ciclos Diffy distintos con un período de exactamente n.

(Parece que, en la literatura, a 0menudo no se considera un juego Diffy periódico. Dado que esta es un área gris, no te pediré que la resuelvas n = 1)

Este es el código de golf , por lo que el objetivo es minimizar el número de bytes en su código fuente.

Casos de prueba

2  ->   0
3  ->   1
4  ->   0
5  ->   1
6  ->   1
7  ->   3
8  ->   0
9  ->   4
10 ->   4
11 ->   3
12 ->   5
13 ->   5
14 ->  24
15 ->  77
16 ->   0
17 -> 259
18 -> 259
19 ->  27
20 -> 272
21 -> 811
22 -> 768
23 ->  91
24 -> 340
25 -> 656

Consejos

Todos los juegos de diferencias periódicas contendrán solo cero y una sola constante, esto significa que cada juego periódico será isomorfo a algunos juegos de diferencias que consisten solo en ceros y unos.

Python 2 , 181 bytes

n=input()
m=2**n
a=[m]*m
r=lambda i:[i*-~m>>k&m-1 for k in range(n)]
def s(i):
 if a[i]&m:a[i]=i;a[i]=s(min(r(i^i*2)))
 return a[i]
print sum(min(r(i)[1:])>i==s(i)for i in range(m))

Pruébalo en línea!

Cómo funciona

Las reglas que transforman cada fila de un juego de diferencias binarias en la siguiente fila son las mismas que las reglas que transforman cada columna en la siguiente columna. Por lo tanto, es suficiente encontrar todos los ciclos distintos dentro del gráfico de todas las columnas de longitud n canónica , donde una columna es "canónica" si es lexicográficamente más pequeña que todas sus rotaciones (esto excluye automáticamente las columnas con un período menor que n ).

Con columnas representadas como números binarios 0 ≤ i <2 ⁿ , la regla envía i a la rotación más pequeña de i XOR ( i ⋅2). (Si i es canónica, su alto bit es cero y no tiene que preocuparse acerca envolvente aquí.)

Entonces, recorremos todas las columnas posibles i , verificamos la canonicidad, luego aplicamos la regla repetidamente hasta que encontremos una columna que hayamos visitado antes, recordando la primera columna revisada. Exactamente una columna en cada ciclo será su propia primera columna revisada.