Imprime la diferencia en la secuencia Thue-Morse

10

Tenga en cuenta que cuando digo "negar", me refiero a reemplazar todos los ceros (es decir, una negación bit a bit)

La secuencia Thue-Morse es como 01101001

La forma en que lo genera es:

Comienza tomando 0. Niega lo que queda y añádelo hasta el final.

Entonces, toma 0. Negarlo y agregarlo al final -01

Luego, tómalo, niegalo y agrégalo al final. 0110

Y así.

Otra propiedad interesante de esto es que la distancia entre ceros crea una cadena "irracional" y no repetitiva.

Entonces:

0110100110010110
|__|_||__||_|__|
 2  1 0 2 01 2          <------------Print this!

¿Puede escribir un programa que, cuando ingrese n, produzca los primeros n dígitos de la cadena para imprimir?

Este es el código de golf, por lo que gana el menor número de bytes.


fuente
66
No requerir una base específica para la salida parece laguna. La secuencia Thue-Morse en sí es la salida deseada, en unario y con 0 como separador.
Dennis

Respuestas:

2

Jalea, 9 bytes

;¬$‘¡TI’ḣ

Pruébalo en línea!

Cómo funciona

;¬$‘¡TI’ḣ  Main link. Argument: n

  $        Create a monadic chain that does the following to argument A (list).
 ¬         Negate all items of A.
;          Concatenate A with the result.
   ‘¡      Execute that chain n + 1 times, with initial argument n.
     T     Get all indices of truthy elements (n or 1).
      I    Compute the differences of successive, truthy indices.
       ’   Subtract 1 from each difference.
        ḣ  Keep the first n results.
Dennis
fuente
4

Python 3 2, 104 92 88 84 bytes

Esta es una solución bastante rudimentaria basada en la construcción de una secuencia Thue-Morse ternaria desde cero. Esta secuencia es idéntica a la que se pregunta, aunque alguien más tendrá que escribir una explicación más completa de por qué es así. En cualquier caso, esta secuencia es solo una modificación trivial de esta, A036580 .

Editar: Cambió el bucle for a una lista de comprensión, cambió de una función a un programa y cambió todo a Python 2. Gracias a Dennis por la ayuda en el golf.

n=input()
s="2"
while len(s)<n:s="".join(`[1,20,210][int(i)]`for i in s)
print s[:n]
Sherlock9
fuente
3

Julia, 56 50 bytes

n->(m=1;[m=[m;1-m]for _=0:n];diff(find(m))[1:n]-1)

Esta es una función anónima que acepta un entero y devuelve una matriz de enteros. Para llamarlo, asígnelo a una variable.

Generamos la secuencia Thue-Morse bit-intercambiado partiendo de un número entero m = 1y, a continuación añadimos 1-ma mcomo una matriz n+1veces, donde nes la entrada. Esto genera más términos de los que necesitamos. Luego localizamos los que usan find(m), obtenemos la diferencia entre los valores consecutivos usando diff, y restamos 1 elemento. Tomar los primeros ntérminos de la matriz resultante nos da lo que queremos.

¡Ahorré 6 bytes y solucioné un problema gracias a Dennis!

Alex A.
fuente
3

PowerShell, 102 bytes

filter x($a){2*$a+([convert]::toString($a,2)-replace0).Length%2}
0..($args[0]-1)|%{(x($_+1))-(x $_)-1}

Una forma un poco diferente de computación. PowerShell no tiene una manera fácil de "obtener todos los índices en esta matriz donde el valor en ese índice es igual a tal y tal ", por lo que debemos ser un poco creativos.

Aquí estamos usando A001969 , los "números con un número par de 1s en su expansión binaria", que casualmente da los índices de los 0 en la secuencia Thue-Morse. ;-)

El filtercalcula ese número. Por ejemplo, x 4daría 9. Luego simplemente hacemos un bucle desde 0nuestra entrada $args[0], restando 1porque estamos indexados a cero, y cada iteración del bucle imprime la diferencia entre el siguiente número y el número actual. La salida se agrega a la canalización e implícitamente se genera con nuevas líneas.

Ejemplo

PS C:\Tools\Scripts\golfing> .\print-the-difference-in-the-thue-morse.ps1 6
2
1
0
2
0
1
AdmBorkBork
fuente
¡La relación con A001969 es un gran hallazgo!
Luis Mendo
3

Haskell, 42 bytes

l=2:(([[0..2],[0,2],[1]]!!)=<<l)
(`take`l)

Ejemplo de uso: (`take`l) 7-> [2,1,0,2,0,1,2].

Es una implementación de a036585_listde A036585 desplaza hacia abajo a 0, 1y 2. Golf: concat (map f l)es f =<< ly f 0=[0,1,2]; f 1=[0,2]; f 2=[1]es ([[0..2],[0,2],[1]]!!).

Nota: les la secuencia infinita. Se necesitan 10 bytes o aproximadamente el 25% para implementar la función de primeros nelementos.

nimi
fuente
3

Mathematica, 79 68 70 bytes

(Differences[Join@@Position[Nest[#~Join~(1-#)&,{0},#+2],0]]-1)[[;;#]]&
CalculadoraFeline
fuente
1
Falla por n<3.
murphy
3

MATL , 14 11 bytes

Q:qB!Xs2\dQ

Pruébalo en línea!

Como señaló @TimmyD en su respuesta , la secuencia deseada está dada por las diferencias consecutivas de A001969 . Este último a su vez se puede obtener como la secuencia Thue-Morse más 2 * n . Por lo tanto, la secuencia deseada viene dada por (diferencias consecutivas de la secuencia Thue-Morse) más uno .

Por otro lado, la secuencia Thue-Morse se puede obtener como el número de unos en la representación binaria de n , comenzando desde n = 0.

Q:q    % take input n implicitly and generate row vector [0,1,...,n]
B!     % 2D array where columns are the binary representations of those numbers
Xs     % sum of each column. Gives a row vector of n+1 elements
2\     % parity of each sum
d      % consecutive differences. Gives a row vector of n elements
Q      % increase by 1. Display implicitly
Luis Mendo
fuente
¿Puedo solicitar paréntesis en (diferencias consecutivas de la secuencia Thue-Morse) más 1 ?
CalculatorFeline
@CatsAreFluffy Tienes toda la razón. Hecho
Luis Mendo
2

05AB1E , 14 13 bytes

Código:

ÎFDSÈJJ}¥1+¹£

Explicación:

Î              # Push 0 and input
 F     }       # Do the following n times
  DS           # Duplicate and split
    È          # Check if even
     JJ        # Join the list then join the stack
        ¥1+    # Compute the differences and add 1
           ¹£  # Return the [0:input] element

Pruébalo en línea!

Adnan
fuente
2

Python, 69 bytes

t=lambda n:n and n%2^t(n/2)
lambda n:[1+t(i+1)-t(i)for i in range(n)]

El itérmino th de esta secuencia es 1+t(i+1)-t(i), donde testá la función Thue-Morse. El código lo implementa de forma recursiva, que es más corto que

t=lambda n:bin(n).count('1')%2
xnor
fuente
1

Mathematica, 65 bytes

SubstitutionSystem[{"0"->"012","1"->"02","2"->"1"},"0",#][[;;#]]&

Supera mi otra respuesta, pero no supera el extra- versión de golf picante . Ahora normalmente pongo mi código entre comillas, luego lo saco porque a Mathematica le encanta agregar espacios a su código (que no hace nada) pero nunca se mete con cadenas, pero eso no funciona para el código que sí tiene comillas ...

Lo que sea, solo estoy usando la magia incorporada para esto. La salida es una cadena.

CalculadoraFeline
fuente
Ahora tenemos 4 respuestas de Mathematica: la original, la no verbal (son 5 si el símbolo solo cuenta), la extra-golf y mi magia incorporada.
CalculatorFeline
1

Mathematica, 58 bytes

Differences[Nest[Join[#,1-#]&,{0},#]~Position~0][[;;#]]-1&
Un simmons
fuente
1
¿Cómo sé que no tomaste mi solución y la jugaste?
CalculatorFeline
@catsarefluffy Adapte su idea para generar la secuencia (jugando golf cortando el operador infijo), pero sentí que el método utilizado aquí para transformar eso en la salida deseada era muy diferente y más adecuado para una nueva respuesta que una edición sugerida.
Un Simmons
@catsarefluffy Acabo de ver tu edición. La última vez que lo vi fue en su forma original cuando hice esto. Eliminaré esta respuesta, pero tendrás que confiar en mí que fue independiente :)
Un Simmons
1;;#puede ser reemplazado por simplemente ;;#.
LegionMammal978
En realidad, obtuve la transformación de salida de la respuesta de TimmyD. (Específicamente, el primer párrafo me hizo recordar Position.)
CalculatorFeline
1

Perl, 45 + 2 = 47 bytes

$_=2;s/./(1,20,210)[$&]/ge until/.{@F}/;say$&

Requiere la bandera -py -a:

$ perl -pa morse-seq.pl <<< 22                                                                            
2102012101202102012021

Puerto de @ Sherlock9 respuesta

Guardado 9 bytes gracias a Ton

andlrc
fuente
La -aopción le da una copia gratuita de la entrada, entonces$_=2;s/./(1,20,210)[$&]/ge until/.{@F}/;$_=$&
Ton Hospel
@TonHospel Eso es perfecto, no puedo creer que no haya pensado en eso :-) Y puedo guardarlo -pcon -E: say$&al final si suponemos que Perl> v5.18
andlrc
1

JavaScript (ES6), 73 67 bytes

f=(n,s="2")=>s[n]?s.slice(0,n):f(n,s.replace(/./g,c=>[1,20,210][c]))

La respuesta del puerto de @ Sherlock9.

editar: guardado 6 bytes gracias a @WashingtonGuedes.

Neil
fuente
¿ !s[n]Funcionaría en lugar de s.length<n? O tal vez solo s[n]con ?:invertido?
eliminado
1

CJam (19 bytes)

1ri){2b:^}%2ew::-f-

Demostración en línea

Esto utiliza el enfoque de incrementar las sucesivas diferencias entre los elementos de la secuencia Thue-Morse.


Mi enfoque más corto usando reglas de reescritura es de 21 bytes:

ri_2a{{_*5*)3b~}%}@*<

(Advertencia: lento). Esto codifica las reglas de reescritura

0  ->  1
1  ->  20
2  ->  210

como

x -> (5*x*x + 1) in base 3
Peter Taylor
fuente
0

Ruby, 57 bytes

Un puerto de la respuesta Python de xnor. Los cambios se encuentran en su mayoría en la declaración ternaria ten lugar de la anddebida a 0estar Truthy en Ruby, y el uso (1..n).mapy 1+t[i]-t[i-1]ahorrar bytes frente a la importación de la lista por comprensión directa.

t=->n{n<1?n:n%2^t[n/2]}
->n{(1..n).map{|i|1+t[i]-t[i-1]}}
Sherlock9
fuente
0es verdad? ¿¿Cómo funciona??
CalculatorFeline
@CatsAreFluffy En mi experiencia, mal
Sherlock9
0

Mathematica ( casi no verbal), 107 110 bytes

({0}//.{n__/;+n<2#}:>{n,{n}/.x_:>(1-x)/._[x__]:>x}//.{a___,0,s:1...,0,b___}:>{a,+s/.(0->o),0,b}/.o->0)[[;;#]]&

La secuencia se genera aplicando repetidamente una regla de reemplazo. Otra regla lo transforma a la salida deseada. Si hay suficientes personas interesadas, lo explicaré en detalle.

versión no alfanumérica

({$'-$'}//.{$__/;+$/#
<($'-$')!+($'-$')!}:>
{$,{$}/.$$_:>(($'-$')
!-$$)/.{$$__}:>$$}//.
{$___,$'-$',$$:($'-$'
)!...,$'-$',$$$___}:>
{$,+$$/.($'-$'->$$$$)
,$'-$',$$$}/.$$$$->$'
-$')[[;;#]]

como lo sugiere CatsAreFluffy.

murphy
fuente
Creo que es seguro asumir que las personas están suficientemente interesadas en una explicación para casi cualquier respuesta. Hablando solo para mí, no votaré las presentaciones sin explicaciones (a menos que el enfoque sea obvio).
Alex A.
Y si convierte todas las letras en secuencias de $y reemplaza 0con x-x(donde x es una secuencia no utilizada de $) (y usa (x-x)!para 1 (ídem)), seremos libres de caracteres alfanuméricos.
CalculatorFeline
Bytesave: Usar en {x__}lugar de_[x__]
CalculatorFeline
De hecho, estoy bastante seguro de que Mathematica completa Turing solo en símbolos o $[_]:=-/;(ambos por emulación de máquina de contador)
CalculatorFeline