Imprimir a diferença na sequência de Thue-Morse

10

Observe que, quando digo "negar", quero dizer substituir todos os zeros (ou seja, uma negação bit a bit)

A sequência Thue-Morse é como 01101001

A maneira como você o gera é:

Comece com 0. Negue o que resta e anexe-o ao final.

Então pegue 0. Negue e adicione isso ao final -01

Então pegue isso e negue e adicione isso até o fim - 0110

E assim por diante.

Outra propriedade interessante disso é que a distância entre zeros cria uma string "irracional" e não repetitiva.

Então:

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

Você pode escrever um programa que, quando inserido n, produzirá os primeiros n dígitos da sequência a ser impressa?

Este é um código de golfe, e o menor número de bytes vence!


fonte
6
Não exigir uma base específica para a saída parece brecha. A sequência Thue-Morse em si é a saída desejada, em unário e com 0 como separador.
Dennis

Respostas:

2

Geléia, 9 bytes

;¬$‘¡TI’ḣ

Experimente online!

Como 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
fonte
4

Python 3 2, 104 92 88 84 bytes

Essa é uma solução bastante rudimentar, baseada na construção de uma sequência ternária de Thue-Morse do zero. Essa sequência é idêntica à que está sendo solicitada, embora outra pessoa precise escrever uma explicação mais completa do motivo. De qualquer forma, essa sequência é apenas uma modificação trivial dessa, A036580 .

Edit: Alterou o loop for para uma compreensão da lista, mudou de uma função para um programa e mudou tudo para Python 2. Agradecimentos a Dennis pela ajuda no golfe.

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

Julia, 56 50 bytes

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

Esta é uma função anônima que aceita um número inteiro e retorna uma matriz inteira. Para chamá-lo, atribua-o a uma variável.

Nós gerar a sequência Thue-Morse permutado bits, começando com um número inteiro m = 1, então anexamos 1-ma mcomo uma matriz n+1vezes, onde nestá a entrada. Isso gera mais termos do que precisamos. Em seguida, localizamos os que estão usando find(m), obtemos a diferença entre valores consecutivos usando diffe subtraímos 1 elemento. Tomar os primeiros ntermos da matriz resultante nos dá o que queremos.

Economizou 6 bytes e corrigiu um problema graças ao Dennis!

Alex A.
fonte
3

PowerShell, 102 bytes

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

Um pouco de uma maneira diferente de calcular. O PowerShell não tem uma maneira fácil de "obter todos os índices nessa matriz em que o valor nesse índice é igual a tal e tal ", portanto, precisamos ser um pouco criativos.

Aqui estamos usando A001969 , os "números com um número par de 1s em sua expansão binária", que completamente coincidentemente fornece os índices dos 0s na sequência Thue-Morse. ;-)

O filtercalcula esse número. Por exemplo, x 4daria 9. Simplesmente passamos 0para a entrada $args[0], subtraindo 1porque somos indexados a zero, e cada iteração do loop imprime a diferença entre o próximo número e o número atual. A saída é adicionada ao pipeline e a saída implicitamente com novas linhas.

Exemplo

PS C:\Tools\Scripts\golfing> .\print-the-difference-in-the-thue-morse.ps1 6
2
1
0
2
0
1
AdmBorkBork
fonte
A relação com A001969 é uma ótima descoberta!
18746 Luis Mendo
3

Haskell, 42 bytes

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

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

É uma implementação a036585_listde A036585 deslocou para baixo para 0, 1e 2. Golfe: concat (map f l)é f =<< le f 0=[0,1,2]; f 1=[0,2]; f 2=[1]é ([[0..2],[0,2],[1]]!!).

Nota: lé a sequência infinita. São necessários 10 bytes ou cerca de 25% para implementar o nrecurso take- first - element.

nimi
fonte
3

Mathematica, 79 68 70 bytes

(Differences[Join@@Position[Nest[#~Join~(1-#)&,{0},#+2],0]]-1)[[;;#]]&
CalculatorFeline
fonte
11
Falha em n<3.
murphy
3

MATL , 14 11 bytes

Q:qB!Xs2\dQ

Experimente online!

Conforme apontado por @TimmyD em sua resposta , a sequência desejada é dada pelas diferenças consecutivas de A001969 . Este último, por sua vez, pode ser obtido como a sequência de Thue-Morse mais 2 * n . Portanto, a sequência desejada é dada pelas (diferenças consecutivas da sequência de Thue-Morse) mais uma .

Por outro lado, a sequência de Thue-Morse pode ser obtida como o número de unidades na representação binária de n , começando em 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
fonte
Posso solicitar parênteses em (diferenças consecutivas da sequência de Thue-Morse) mais 1 ?
CalculatorFeline
@CatsAreFluffy Você está totalmente certo. Feito
Luis Mendo
2

05AB1E , 14 13 bytes

Código:

ÎFDSÈJJ}¥1+¹£

Explicação:

Î              # 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

Experimente online!

Adnan
fonte
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)]

O itermo th desta sequência é 1+t(i+1)-t(i), onde testá a função Thue-Morse. O código o implementa recursivamente, que é menor que

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

Mathematica, 65 bytes

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

Supera minha outra resposta, mas não supera a versão extra- picante do golfe. Agora normalmente coloco meu código entre aspas e o retiro porque o Mathematica adora adicionar espaços ao seu código (que não fazem nada), mas nunca mexe com as strings, mas isso não funciona para o código que possui aspas ...

Seja como for, eu só estou usando a mágica embutida para isso. Saída é uma string.

CalculatorFeline
fonte
Agora temos 4 respostas do Mathematica: Minha original, a não verbal (é 5 se apenas o símbolo contar), a extra-golfe e a minha mágica embutida.
CalculatorFeline
1

Mathematica, 58 bytes

Differences[Nest[Join[#,1-#]&,{0},#]~Position~0][[;;#]]-1&
A Simmons
fonte
11
Como sei que você não pegou minha solução e a jogou fora?
CalculatorFeline
@catsarefluffy Eu adaptei sua idéia para gerar a sequência (jogando-a cortando o operador infix), mas achei que o método usado para transformar isso na saída pretendida era muito diferente e mais adequado para uma nova resposta do que para uma edição sugerida.
A Simmons
@catsarefluffy Acabo de ver sua edição. a última vez que vi que estava em sua forma original quando fiz isso. Vou remover esta resposta, mas você vai ter que confiar em mim que era :) independente
Um Simmons
1;;#pode ser substituído por simplesmente ;;#.
precisa
Na verdade, obtive a transformação de saída da resposta de TimmyD. (Especificamente, o primeiro parágrafo me fez lembrar Position.)
CalculatorFeline
1

Perl, 45 + 2 = 47 bytes

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

Requer o sinalizador -pe -a:

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

Porto de @ Sherlock9 answer

Economizou 9 bytes graças a Ton

andlrc
fonte
A -aopção dá-lhe uma cópia gratuita da entrada, então$_=2;s/./(1,20,210)[$&]/ge until/.{@F}/;$_=$&
Ton Hospel
@TonHospel Isso é perfeito, não posso acreditar que eu não tinha pensado nisso :-) E eu posso salvar o -pcom -E: say$&no final, se assumirmos 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]))

Porto da resposta de @ Sherlock9.

editar: salvou 6 bytes graças a @WashingtonGuedes.

Neil
fonte
Iria !s[n]trabalhar no lugar de s.length<n? Ou talvez apenas s[n]com ?:invertido?
removido
1

CJam (19 bytes)

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

Demonstração online

Isso utiliza a abordagem de incrementar as sucessivas diferenças entre os elementos da sequência de Thue-Morse.


Minha abordagem mais curta usando regras de reescrita é 21 bytes:

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

(Aviso: lento). Isso codifica as regras de reescrita

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

Como

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

Ruby, 57 bytes

Uma porta da resposta Python do xnor. As mudanças se localizam principalmente na demonstração ternário em tno lugar do anddevido 0sendo truthy em Ruby, e usando (1..n).mape 1+t[i]-t[i-1]para salvar bytes vs. importar a compreensão da lista diretamente.

t=->n{n<1?n:n%2^t[n/2]}
->n{(1..n).map{|i|1+t[i]-t[i-1]}}
Sherlock9
fonte
0é verdade? Como isso funciona??
CalculatorFeline
@CatsAreFluffy Na minha experiência, mal #
Sherlock9
0

Mathematica ( quase não 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)[[;;#]]&

A sequência é gerada aplicando repetidamente uma regra de substituição. Outra regra a transforma na saída desejada. Se houver um número suficiente de pessoas interessadas, explicarei em detalhes.

versão não alfanumérica

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

como sugerido por CatsAreFluffy.

Murphy
fonte
Eu acho que é seguro assumir que as pessoas estão suficientemente interessadas em uma explicação para praticamente qualquer resposta. Falando apenas por mim, não voto positivo nos envios sem explicações (a menos que a abordagem seja óbvia).
Alex A.
E se você transformar todas as letras em sequências $e substituí 0- las por x-x(onde x é uma sequência não utilizada de $) (e usar (x-x)!para 1 (idem)), não teremos alfanuméricos.
CalculatorFeline
Bytesave: Use em {x__}vez de_[x__]
CalculatorFeline
Na verdade, tenho certeza de que o Mathematica é completo em Turing apenas em símbolos ou $[_]:=-/;(ambos por emulação de contador de máquina)
CalculatorFeline