Generowanie NOP Brainf ***

26

Czasami pisząc kod pieprzony mózg, czujesz potrzebę wydłużenia go, aby zachęcić do debugowania. Mógłbyś to zrobić po prostu wsadzając ><tam, ale co to za zabawa? Będziesz potrzebował czegoś dłuższego i mniej NOPey, aby zmylić każdego czytającego Twój kod.

Szybkie wprowadzenie do Brainfuck

Brainfuck jest ezoterycznym językiem programowania stworzonym w 1993 roku przez Urban Müllera i wyróżniającym się ekstremalnym minimalizmem. (Wikipedia)

Brainfuck to język oparty na ośmiu poleceń: +-><,.[]. Kod jest uruchamiany na czymś takim jak maszyna Turinga: nieskończona taśma, na której można zmieniać wartości. W tym wyzwaniu skupimy się na pierwszych czterech:

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

NOP Brainfuck

NOP typu „brainfuck” to sekwencja postaci typu „brainfuck”, które po wykonaniu z dowolnego stanu nie prowadzą do zmiany stanu. Składają się z czterech wyżej wymienionych postaci.

Wyzwanie

Wyzwanie polega na napisaniu programu lub funkcji, która po uruchomieniu generuje losowy NOP o określonej długości.

Wkład

Otrzymasz jako dane wejściowe nieujemną liczbę całkowitą n. (NOP są niemożliwe dla nieparzystych n.)

Wydajność

Wyślesz losowy NOP pieprzony mózg o długości n.

Zasady

  • Definicja NOP: kiedy wyjście programu jest wstawiane w dowolnym punkcie programu do pieprzenia mózgu, zachowanie tego programu nie może się w żaden sposób zmieniać. Innymi słowy, nie może zmieniać stanu tłumacza.
    • Zauważ, że na przykład +>-<jest niepoprawny, ponieważ zmienia wartości dwóch komórek bez zmiany ich z powrotem. Przed opublikowaniem sprawdź swoje rozwiązanie.
    • Zauważ też, że +>-<->+<jest to NOP, którego nie można zredukować do zera przez samo usunięcie >< <> +- -+. Dlatego nie można użyć algorytmu, który po prostu wstawia je do siebie.
  • Każdy prawidłowy NOP długości nmusi mieć niezerową szansę pojawienia się na wyjściu. Jednak rozkład nie musi być jednolity.
  • Interpretator, o którym mowa, ma podwójnie nieskończoną taśmę komórek o dowolnej precyzji. Oznacza to, że możesz iść w nieskończoność w obu kierunkach i zwiększać / zmniejszać każdą komórkę w nieskończoność.
  • Program musi zakończyć się w ciągu 1 minuty dla n= 100 na moim komputerze, więc nie będzie generować wszystkich możliwych NOP i wybierać jednego.
  • Jeśli podano nieprawidłowe dane wejściowe (niecałkowite, ujemne, nieparzyste itp.), Możesz zrobić wszystko, co chcesz, w tym awarię.

Punktacja

To jest , więc wygrywa najkrótsza odpowiedź w bajtach.

Przykłady

Oto wszystkie prawidłowe dane wyjściowe dla n= 4:

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

Oto kilka możliwych wyników dla n= 20:

+>>->+<->-<<<->>++<<
>+>-<+<->+-<>->+<-<+
+--+-++--++-+--+-++-
>>>>>>>>>+-<<<<<<<<<
PurkkaKoodari
źródło
18
oto NOP brainfuck że nie używa +-<>jakbyś poprosił:a
undergroundmonorail
1
Nie sądzę, żeby istniały nie proste NOP, więc prawdopodobnie możesz usunąć tę kwalifikację. .ma efekt uboczny, ,zastępuje wartość, której nie można odzyskać bez użycia []. Ale w []końcu ustawi wartość na zero. To również nadpisuje wartość (więc potrzebowalibyśmy innej, []aby ją odzyskać), chyba że możemy być pewni, że komórka, której dotyczy problem, na początku miała zero. Musielibyśmy jednak szukać takiej komórki z czymś podobnym [>]i niemożliwe jest niezawodne powrót do pozycji, z której przyszliśmy.
Martin Ender,
4
@Eumel „Omawiany interpreter pieprzenia mózgów ma podwójnie nieskończoną taśmę komórek o dowolnej precyzji”.
Martin Ender,
2
Pamiętaj, że „Brainfuck” nie jest już dozwolone w tytułach pytań na poziomie systemu. Wygląda na to, że udało ci się obejść to ograniczenie, używając znaków spoza ASCII. W przyszłości prosimy o przestrzeganie tego ograniczenia.
Alex A.,
2
@undergroundmonorail Cóż, Turing jest kompletny ... więc technicznie można napisać w nim PRNG, tak jak każdy inny język. (Chociaż wysiew może być trudny.)
PurkkaKoodari,

Odpowiedzi:

13

CJam, 62 59 bajtów

Dzięki nhahtdh za oszczędność 3 bajtów.

Ponieważ nie ma wymogu dla żadnego konkretnego rozkładu, o ile każdy brak pojawi się z skończonym prawdopodobieństwem, możemy to bardzo uprościć, po prostu generując ciąg zawierający zrównoważoną liczbę -+i <>, odpowiednio, testując, czy jest to NOP i sortując go, jeśli nie jest.

Oczywiście w przypadku dłuższych danych wejściowych prawie zawsze spowoduje to posortowane dane wyjściowe, ale można przetestować kod za pomocą niektórych danych wejściowych, 8aby przekonać się, że może on generować dowolny NOP o podanej długości.

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

Wypróbuj online.

Martin Ender
źródło
1
Tak ... arbitralny limit powinien wynosić n = 1000 poniżej 10 sekund. Komputery są dzisiaj sposobem na szybkie ^^ Ponieważ odpowiedź algorytmiczna rozwiązuje ją w ciągu sekundy nawet dla n = 1000
Falco
W przypadku jeszcze większego n myślę, że możliwe jest po prostu sortowanie danych wyjściowych, jeśli zbalansowany ciąg znaków nie jest NOP. Dystrybucja jest strasznie wypaczona, ale na to pozwala pytanie.
n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳ to fajny pomysł.
Martin Ender,
@ n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨d̷̰̀ĥ̷̳ Dzięki, to faktycznie oszczędza również trzy bajty tutaj.
Martin Ender,
16

CJam, 118 116 bajtów

To nieco wymknęło się spod kontroli ... zwłaszcza druga połowa wydaje się, że powinna być bardzo golfowa.

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

Sprawdź to tutaj.

To działa N = 100prawie natychmiast. Nie mam teraz czasu na napisanie pełnego podziału kodu, więc oto algorytm:

  • Wygenerować losowy ciąg zrównoważony <i >losowych (nawet) długości między 0i Nwłącznie.
  • Riffle pozycji głowicy taśmy w tej tablicy. Np . "<>><"Staje się [0 '< -1 '> 0 '> 1 '< 0].
  • Uzyskaj listę wszystkich pozycji osiągniętych w trakcie procesu.
  • Dla każdej takiej pozycji zainicjuj pusty ciąg. Określ także, ile par znaków pozostało, aby osiągnąć ciąg długości N.
  • Do każdej pozostałej pary dołącz +-ciąg do losowej pozycji.
  • Przetasuj wszystkie te struny.
  • Dla każdej pozycji określ, jak często ta pozycja występuje w ryflowanej tablicy, i podziel odpowiedni ciąg na tyle kawałków (o losowej długości).
  • W tablicy riffled zamień wystąpienia pozycji na przypadkowe fragmenty.

Gotowy. Jest to oparte na spostrzeżeniu, że:

  • Każdy NOP musi mieć taką samą ilość <i >aby przywrócić głowicę taśmy do pierwotnej pozycji.
  • Kod będzie NOP, o ile każda komórka taśmy będzie zwiększana tak często, jak zmniejszana.

Poprzez dystrybucję losowe ale zbilansowane ilości +s i -s pomiędzy wszystkich miejscach, gdzie szef taśma jest na danej komórce, mamy pewność, że możemy znaleźć każdą możliwą NOP.

Martin Ender
źródło
4

Mathematica, 350 bajtów

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)&

Zbyt długo? Tak. Czy w ogóle mnie to obchodzi? Nie, dopóki ktoś inny nie opublikuje prawidłowej odpowiedzi.

LegionMammal978
źródło
4
Czy mógłbyś dodać wyjaśnienie, aby ludzie mogli przekonać się, że jest to poprawne? :)
Martin Ender,
Jak dokładnie czyni tę pracę? Jeśli wywołam funkcję z numerem, zwraca tylko +.
Martin Ender,
@ MartinBüttner Naprawiono ... Obecnie, po prostu generuje losowe programy z równej liczby +- -i <- >parami, dopóki jeden dzieje się NOP. Połowę zajmuje prosty tłumacz BF.
LegionMammal978,
czy to faktycznie generuje ważny brak operacji o długości 100 w mniej niż minutę?
Martin Ender,
@ MartinBüttner Tak. Powiedziałbym, że zajmuje to średnio około 5 sekund. Na początku próbowałem całkowicie losowych programów, ale nigdy nie zakończyło się to na długość 100.
LegionMammal978
2

Python 3 , 177 bajtów

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='')

Wypróbuj online!

Użyłem kodu z odpowiedzi Bubblera do symulacji BF.

Tyilo
źródło
2

Python 3 , 163 bajty

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='')

Wypróbuj online!

Pełny program, który drukuje wyniki do STDOUT. Linia z kodem BF może być golfowa.

Przyjęła podejście Tyilo; jeśli wygenerowany kod BF nie jest NOP, odrzuć go całkowicie i wróć do '+-'powtarzania.

Bubbler
źródło
Limit czasu dla n = 100
l4m2
@ l4m2 Nie zauważyłem tego wymagania. Naprawiony.
Bubbler
1

JavaScript (Node.js) , 160 bajtów

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

Wypróbuj online!

l4m2
źródło
1

Wolfram Language (Mathematica) , 224 bajty

(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)&

Wypróbuj online!

Oto wersja bez gry w golfa (a raczej gry w golfa):

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]

Najpierw wybrać losową liczbę <„s i >” s do użytku, i wygenerować losowy listy z równą liczbą każda.

Aby wypełnić pozostałe znaki, wybieramy pozycję, w której chcesz dodać +, a następnie znajdujemy pozycję, w której wskaźnik wskazuje na to samo miejsce i -tam dodajemy .

Powtarzaj, aż lista będzie miała długość n, i uszereguj wynik.

Misza Ławrow
źródło