Zere uma célula arbitrariamente grande em Brainf ***

28

Sua tarefa é escrever um pedaço de código que zere a célula atual na variante Brainfuck que, cada célula pode conter um número inteiro assinado de magnitude arbitrariamente grande, em vez dos 0 a 255 normais.

Você pode assumir que existem l células à esquerda er células à direita da célula atual que são inicialmente zero. Seu programa pode acessar apenas essas células l + r +1. Depois que seu código termina, ele deve deixar as células extras l + r zero e o ponteiro para a célula atual na posição original.

Você não pode usar nenhuma entrada / saída.

O código com menor l + r vence. Se houver um empate, o código mais curto vence. É recomendável também indicar a complexidade do tempo do seu programa para referência, onde n é o valor absoluto do número inteiro original na célula atual.

Ferramentas úteis

Você pode testar um programa Brainfuck nessa variação usando este intérprete no TIO por mbomb007 .

Você também pode usar o intérprete nesta resposta por boothby (outras respostas do Python provavelmente também funcionam, mas eu não testei).

jimmy23013
fonte
Eu o marquei como code-golf porque acho que alcançaremos o l + r ideal rapidamente.
Jimmy23013
2
Parece que, com o seu comentário, você quis dizer um número inteiro de magnitude arbitrária, o que pode ser positivo ou negativo. Essa é uma diferença no dialeto em inglês para algumas pessoas; portanto, pode ser útil esclarecer que pode ser muito positivo ou muito negativo.
Isaacg
4
@ jimmy23013 Você tem um intérprete de BF com células assinadas que podemos usar para isso?
Mbomb007 /
@ mbomb007 codegolf.stackexchange.com/a/3085/25180 mas provavelmente muito golfy ...
jimmy23013
1
@Mego Why? No desafio "real", você também deve obter o l + r ideal, o que provavelmente tornará mais difícil reduzir o tamanho do código.
Jimmy23013

Respostas:

17

l + r = 0 + 2 = 2, 55 53 51 bytes

[>+[-<+>>+<]<[>]>[+[-<+<->>]<[->+<]]>[-<+>]<<]>[-]<

l + r = 1 + 2 = 3, 46 44 bytes

[[>+[-<+<+>>]<[<+[->->+<<]]>]>[>]<[-]<<[-]>]

Meu próprio algoritmo. O ponteiro deve começar no número que precisa ser zerado. A complexidade do tempo é O (n ^ 2).

Como funciona:

  • Começamos com o número n.
  • Nós incrementamos um, então o número se torna n+1.
  • Nós diminuímos dois, então o número se torna n+1-2 = n-1
  • Como incrementamos três, o número se torna n-1+3 = n+2.
  • Nós diminuímos quatro, então o número se torna n+2-4 = n-2.

Repetimos o processo, aumentando o decréscimo a cada passo, até chegarmos a zero.

JungHwan Min
fonte
2
Exatamente o algoritmo em que pensei depois de passar do estágio "isso não é possível": P
ETHproductions
9

l + r = 0 + 2 = 2; 58 bytes

>+<[>[<->>+<-]>+<<[>]>[<<+>+>-]<[->+<]>[<]>+[-<+>]<<]>[-]<

A complexidade é O (n ^ 2).

O seguinte é o meu gerador de programa de teste, para que você possa ver que eu realmente tentei testá-lo caso não funcionasse ...

p='''
>+<
[
>
[<->>+<-]
>+<
<[>]>
[<<+>+>-]
<
[->+<]
>[<]>
+ [-<+>]
<<
]
> [-] <
'''

p = ''.join(p.split())

cpp = '''
#include <bits/stdc++.h>
using namespace std;
void test(int q) {
long long t[3] = {q, 0, 0};
int i = 0;
ZZZ
printf("q=%d %lld %lld %lld\\n", q, t[0], t[1], t[2]);
}
int main() {
while(true) {
    int q; cin >> q; test(q);
}
}
'''

d = {
'>': '++i; assert(i<3);',
'<': '--i; assert(i>=0);',
'+': '++t[i];',
'-': '--t[i];',
'[': 'while(t[i]){',
']': '}',
}

print cpp.replace('ZZZ', ''.join(d[c] for c in p))
feersum
fonte
Você pode testá-lo usando o intérprete que acabei de criar. Ver comentário
mbomb007 2/17/17
Parece que funciona para mim.
Mbomb007
2
Este deve ser o ideal l + r. Prova rápida de que 1 é impossível: em cada ponto em que a célula sobressalente atinge zero, você só pode armazenar uma quantidade finita de dados além do valor da célula original (na posição da cabeça da fita e no ponteiro de instruções), o que significa que você está limitado em quão longe pode ajustar a célula principal a partir desse ponto em pelo menos uma direção.
@ ais523 Pode haver outros equivalentes. Seria interessante se alguém cria l + r = 1 + 1.
Mbomb007