Zeruj dowolnie dużą komórkę w Brainf ***

28

Twoim zadaniem jest napisanie kodu zerującego bieżącą komórkę w wariancie Brainfuck, który, każda komórka, może zawierać podpisaną liczbę całkowitą o dowolnie dużej wielkości, zamiast normalnej wartości od 0 do 255.

Można założyć, istnieje l komórki do lewej i r komórek na prawo od bieżącej komórki, które są początkowo zero. Program możesz przejść tylko te l + r +1 komórek. Po swoimi końcami kod powinien on opuścić l + r dodatkowe komórki zero i wskaźnik do bieżącej komórki w pierwotnej pozycji.

Nie możesz używać żadnego wejścia / wyjścia.

Kod z najmniejszym l + r wygrywa. W przypadku remisu wygrywa najkrótszy kod. Zaleca się również podanie złożoności czasowej programu w celach informacyjnych, gdzie n jest wartością bezwzględną oryginalnej liczby całkowitej w bieżącej komórce.

Użyteczne narzędzia

Możesz przetestować program Brainfuck w tej odmianie, używając tego interpretera na TIO przez mbomb007 .

Możesz również użyć interpretera w tej odpowiedzi przez boothby (inne odpowiedzi w Pythonie prawdopodobnie również działają, ale nie testowałem).

jimmy23013
źródło
Oznacziłem to kodem golfowym, ponieważ myślę, że szybko osiągniemy optymalną l + r.
jimmy23013
2
Wygląda na to, że z twojego komentarza masz na myśli liczbę całkowitą o dowolnej wielkości, która może być dodatnia lub ujemna. Jest to różnica w dialekcie angielskim dla niektórych osób, więc może być pomocne wyjaśnienie, że może być bardzo pozytywne lub bardzo negatywne.
isaacg
4
@ jimmy23013 Czy masz interpreter BF z podpisanymi komórkami, których możemy użyć do tego?
mbomb007
@ mbomb007 codegolf.stackexchange.com/a/3085/25180, ale prawdopodobnie zbyt golfy ...
jimmy23013
1
@Mego Dlaczego? W wyzwaniu „prawdziwym” musisz także uzyskać optymalną wartość l + r, co prawdopodobnie utrudni zmniejszenie rozmiaru kodu.
jimmy23013

Odpowiedzi:

17

l + r = 0 + 2 = 2, 55 53 51 bajtów

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

l + r = 1 + 2 = 3, 46 44 bajtów

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

Mój własny algorytm. Wskaźnik powinien zaczynać się od liczby, którą należy wyzerować. Złożoność czasowa wynosi O (n ^ 2).

Jak to działa:

  • Zaczynamy od numeru n.
  • Zwiększamy jeden, więc liczba staje się n+1.
  • Zmniejszamy dwa, więc liczba staje się n+1-2 = n-1
  • Zwiększamy trzy, więc liczba staje się n-1+3 = n+2.
  • Zmniejszamy cztery, więc liczba staje się n+2-4 = n-2.

Powtarzamy ten proces, zwiększając przyrost / spadek z każdym krokiem, aż otrzymamy zero.

JungHwan Min
źródło
2
Dokładnie algorytm, o którym myślałem po przejściu etapu „to nawet nie jest możliwe”: P
ETHprodukcje
9

l + r = 0 + 2 = 2; 58 bajtów

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

Złożoność wynosi O (n ^ 2).

Oto mój generator programu testującego, więc możesz zobaczyć, że próbowałem go przetestować na wypadek, gdyby nie działał ...

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
źródło
Możesz to przetestować za pomocą właśnie utworzonego przeze mnie interpretera. Patrz komentarz
mbomb007
Wygląda na to, że mi to działa.
mbomb007
2
To musi być optymalne l + r. Szybki dowód, że 1 jest niemożliwe: w każdym punkcie, w którym zapasowa komórka osiąga zero, można przechowywać tylko skończoną ilość danych oprócz wartości oryginalnej komórki (w pozycji głowicy taśmy i wskaźnika instrukcji), co oznacza, że jesteś ograniczony w tym, jak daleko możesz dopasować główną komórkę od tego punktu w co najmniej jednym kierunku.
@ ais523 Mogą istnieć inne równoważne. Byłoby interesujące, gdyby ktoś stworzył l + r = 1 + 1.
mbomb007