Gerando *** NOPs da Brainf

26

Às vezes, ao escrever o código do cérebro, você sente necessidade de prolongá-lo mais do que o necessário para incentivar a depuração. Você poderia fazer isso apenas colocando um ><lá, mas que graça é essa? Você precisará de algo mais e menos NOPey para confundir qualquer pessoa que esteja lendo seu código.

Introdução rápida ao Brainfuck

Brainfuck é uma linguagem de programação esotérica criada em 1993 por Urban Müller, e notável por seu extremo minimalismo. (Wikipedia)

Brainfuck é uma linguagem baseada em oito comandos: +-><,.[]. O código é executado em algo como uma máquina de Turing: uma fita infinita na qual os valores podem ser alterados. Neste desafio, focaremos nos quatro primeiros:

+    increment the value at the pointer
-    decrement the value at the pointer
>    move the pointer right
<    move the pointer left

Brainfuck NOPs

Um NOP com ação cerebral é uma sequência de caracteres com ação cerebral que, quando executados a partir de qualquer estado, não levam a nenhuma alteração no estado. Eles consistem nos quatro caracteres mencionados acima.

O desafio

O desafio é escrever um programa ou função que, quando executado, gere um NOP aleatório com o tamanho de um determinado comprimento.

Entrada

Você receberá como entrada um inteiro par não-negativo n. (NOPs são impossíveis para ímpares n).

Saída

Você produzirá um NOP aleatório do tamanho do cérebro n.

Regras

  • A definição de NOP: quando a saída do programa é inserida em qualquer ponto do programa, o comportamento do programa não deve mudar de forma alguma. Em outras palavras, ele não deve alterar o estado do intérprete.
    • Observe que, por exemplo +>-< está incorreto, pois altera os valores das duas células sem alterá-los novamente. Teste sua solução antes de postar.
    • Observe também que +>-<->+<é um NOP que não pode ser reduzido a nada apenas com a remoção >< <> +- -+. Portanto, você não pode usar um algoritmo que apenas os insere.
  • Todo NOP válido do comprimento ndeve ter uma chance diferente de zero de aparecer na saída. A distribuição não precisa ser uniforme, no entanto.
  • O intérprete do cérebro em questão tem uma fita duplamente infinita de células de precisão arbitrárias. Ou seja, você pode ir infinitamente para as duas direções e aumentar / diminuir cada célula indefinidamente.
  • O programa deve terminar dentro de 1 minuto para n= 100 na minha máquina, para não gerar todos os NOPs possíveis e escolher um.
  • Se você receber uma entrada inválida (não inteiro, negativo, ímpar, etc.), poderá fazer o que quiser, incluindo falha.

Pontuação

Isso é , então a resposta mais curta em bytes vence.

Exemplos

Aqui estão todas as saídas válidas para n= 4:

++--    +-+-    +--+    --++    -+-+    -++-
>><<    ><><    ><<>    <<>>    <><>    <>><
><+-    ><-+    <>+-    <>-+
>+-<    >-+<    <+->    <-+>
+><-    -><+    +<>-    -<>+
+-><    -+><    +-<>    -+<>

Aqui estão algumas saídas possíveis para n= 20:

+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<
PurkkaKoodari
fonte
18
aqui está um NOP do cérebro que não usa +-<>como você pediu:a
undergroundmonorail
1
Não acho que existem NOPs não simples, então você provavelmente pode remover essa qualificação. .tem um efeito colateral, ,substitui um valor que não pode ser recuperado sem o uso de []. Mas []acabará definindo um valor para zero. Isso também substitui um valor (portanto, precisaríamos de outro []para recuperá-lo), a menos que possamos ter certeza de que a célula afetada era zero no início. No entanto, teríamos que procurar uma célula com algo parecido [>]e é impossível retornar com segurança à posição de onde viemos.
27568 Martin Ender #
4
@Eumel "O intérprete de cérebro em questão tem uma fita duplamente infinita de células de precisão arbitrárias".
Martin Ender
2
Observe que "Brainfuck" não é mais permitido nos títulos das perguntas no nível do sistema. Parece que você conseguiu contornar a restrição usando caracteres não ASCII. No futuro, cumpra esta restrição.
Alex A.
2
@undergroundmonorail Bem, é Turing completo ... para que tecnicamente alguém possa escrever um PRNG nele como em qualquer outro idioma. (Embora a semeadura pode ser difícil.)
PurkkaKoodari

Respostas:

13

CJam, 62 59 bytes

Obrigado a nhahtdh por salvar 3 bytes.

Como não há requisito para uma distribuição específica, desde que cada operação não apareça com probabilidade finita, podemos simplificar muito isso simplesmente gerando uma string contendo um número equilibrado de -+ e <>, respectivamente, testando se é um NOP e classificando-o se não é.

Obviamente, para entradas mais longas, isso quase sempre resultará em uma saída classificada, mas você pode testar o código com alguma entrada 8para ver se ele pode, em princípio, produzir qualquer NOP do comprimento especificado.

ri_0a*\2/{;"-+<>":L2/mR}%smr:SL["Xa.Xm"3/2e*L]z:sers~0-S$S?

Experimente online.

Martin Ender
fonte
1
Sim ... o limite arbitrário deveria ter sido n = 1000 em 10 segundos. Computadores são apenas maneira de rápido hoje ^^ Porque os resolve resposta algorítmicos lo em menos de um segundo, mesmo para n = 1000
Falco
Para n ainda maior, acho possível classificar a saída apenas se a sequência balanceada não for NOP. A distribuição é terrivelmente distorcida, mas é permitida pela pergunta.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d que é uma idéia legal.
Martin Ender
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Obrigado, isso também salva três bytes aqui.
Martin Ender
16

CJam, 118 116 bytes

Isso ficou um pouco fora de controle ... especialmente a segunda metade parece que deve ser muito jogável.

ri2/_)mr:R-"<>"R*mr_'=fm0\{1$+}%+__&e`]:\{mr1aa..+}*\@](\z:~\{~\("+-"*mr1$3$e=[{_,)mr_2$<@@>}*+]@@f{`1$`={(}@?\}W<}/

Teste aqui.

Isso lida com N = 100 praticamente instantaneamente. Eu não tenho tempo para escrever a repartição completa do código agora, então aqui está o algoritmo:

  • Gere uma sequência aleatória equilibrada de <e >com comprimento aleatório (par) entre 0eN inclusive.
  • Coloque as posições da cabeça da fita nessa matriz. Por exemplo, "<>><"torna-se[0 '< -1 '> 0 '> 1 '< 0] .
  • Obtenha uma lista de todas as posições alcançadas no processo.
  • Para cada uma dessas posições, inicialize uma string vazia. Determine também quantos pares de caracteres restam para atingir uma sequência de comprimentoN .
  • Para cada par restante anexado +- à sequência de uma posição aleatória.
  • Embaralhe todas essas cordas.
  • Para cada posição, determine com que frequência essa posição ocorre na matriz riffled e divida a sequência correspondente em vários pedaços (comprimento aleatório).
  • Na matriz riffled, substitua as ocorrências da posição pelos seus pedaços aleatórios.

Feito. Isso se baseia na observação de que:

  • Qualquer NOP deve ter uma quantidade igual <e> retornar a cabeça da fita à posição original.
  • O código será um NOP desde que cada célula de fita seja incrementada com a frequência decrescente.

Ao distribuir quantidades aleatórias, mas equilibradas, de +s e -s entre todos os locais onde a cabeça da fita está em uma determinada célula, garantimos que encontramos todos os NOP possíveis.

Martin Ender
fonte
4

Mathematica, 350 bytes

Quiet@(For[a="+",If[{##4}=={},#3!=0||Union@#!={0},Switch[#4,"+",#0[ReplacePart[#,#2->#[[#2]]+1],#2,#3,##5],"-",#0[ReplacePart[#,#2->#[[#2]]-1],#2,#3,##5],">",#0[#~Append~0,#2+1,#3+1,##5],"<",If[#2<2,#0[#~Prepend~0,1,#3-1,##5],#0[#,#2-1,#3-1,##5]]]]&@@{{0},1,0}~Join~Characters@a,a=""<>RandomSample@Flatten@RandomChoice[{{"+","-"},{">","<"}},#/2]];a)&

Tempo demais? Sim. Eu me importo? Não até outra pessoa postar uma resposta válida.

LegionMammal978
fonte
4
Você se importaria de adicionar uma explicação, para que as pessoas possam se convencer de que isso é válido? :)
Martin Ender
Como exatamente faz este trabalho? Se eu chamar a função com um número, ela retornará apenas +.
Martin Ender
@ MartinBüttner fixo ... Atualmente, ele só gera programas aleatórios com um número igual de +- -e <- >pares até que um passa a ser um NOP. Metade disso é tomada por um simples intérprete de AM.
LegionMammal978
isso realmente gera um no-op válido de 100 em menos de um minuto?
Martin Ender
@ MartinBüttner Sim. Em média, eu diria que leva cerca de 5 segundos. Na primeira, eu tentei programas completamente aleatórios, mas nunca terminado por tempo 100.
LegionMammal978
2

Python 3 , 177 bytes

from random import*
n=int(input())
r=[0]*n*3
p=0
a=[43,45]
s=choices(a+[60,62],k=n)
for c in s:p+=~c%2*(c-61);r[p]+=c%2*(44-c)
if any(r+[p]):s=a*(n//2)
print(*map(chr,s),sep='')

Experimente online!

Eu usei o código da resposta de Bubbler para a simulação BF.

Tyilo
fonte
2

Python 3 , 163 bytes

from random import*
n=int(input())
p=0;d=[0]*n;a=choices(b'+-<>',k=n)
for c in a:d[p]+=c%2*(44-c);p+=~c%2*(c-61)
if p|any(d):a=n//2*b'+-'
print(*map(chr,a),sep='')

Experimente online!

Programa completo que imprime resultados para STDOUT. A linha que executa o código BF pode ser jogável.

Adotou a abordagem de Tyilo; se o código BF gerado não for um NOP, descarte-o completamente e volte a '+-'repetir.

Bubbler
fonte
Tempo limite para n = 100
l4m2 24/10
@ l4m2 Não percebeu esse requisito. Fixo.
quer
1

JavaScript (Node.js) , 160 bytes

n=>[...s=c(i=n,t=c(n/2,r=[],f=_=>'+-'),f=_=>'+-<>'[Math.random()*4|0])].map(_=>_<'<'?(r[i]=_+1-~r[i]-1):(i+=_<'>'||-1))|r.some(eval)|i-n?t:s;c=n=>n?c(n-1)+f():r

Experimente online!

l4m2
fonte
1

Wolfram Language (Mathematica) , 224 bytes

(s=RandomSample[##&@@@Table["<"">",(r=RandomInteger)[#/2]]];While[(g=Length@s)<#,s=Insert[s=Insert[s,"+",i=r@g+1],"-",RandomChoice@@Select[GatherBy[0~Range~++g,Count[#,"<"]-Count[#,">"]&@Take[s,#]&],!FreeQ[#,i]&]+1]];""<>s)&

Experimente online!

Aqui está a versão sem golfe (ou melhor, pré-golfe):

Function[{n},
 k = RandomInteger[n/2];
 s = RandomSample[## & @@@ Table["<" ">", k]];
 While[Length[s] < n,
   s = Insert[s, "+", i = RandomInteger[Length[s]] + 1];
   p = GatherBy[Range[0, Length[s]], 
     Count[#, "<"] - Count[#, ">"]& @ Take[s, #]&];
   j = RandomChoice @@ Select[p, ! FreeQ[#, i] &]];
   s = Insert[s, "-", j + 1];
   ];
 ""<>s]

Primeiro escolhemos um número aleatório de <'s e> ' para usar e geramos uma lista aleatória com um número igual de cada.

Para preencher o restante dos caracteres, escolhemos uma posição na qual adicionar a +, em seguida encontramos uma posição em que o ponteiro aponta para o mesmo local e adicionamos uma- lá.

Repita até que a lista tenha comprimento ne especifique o resultado.

Misha Lavrov
fonte