Podprogramy Brainf *** z unikalnymi wyjściami

19

Powinieneś napisać program o długości 100 bajtów (BF).

Jedna postać usunie z niej w każdy możliwy sposób powstałe 100 nowych programów (o długości 99 bajtów). Np dla programu ++.>.The 5 podprogramy są +.>., +.>., ++>., ++..i ++.>.

Twój wynik będzie liczbą unikalnych wyników wygenerowanych przez 100 programów. Wyższy wynik jest lepszy.

Detale

  • Twoje programy zostaną zakończone po wypisaniu pierwszego znaku.
  • Niepoprawne lub nie kończące się programy i programy generujące puste wyjścia nie są wliczane do wyniku.
  • Komórki BF są 8-bitowe zwijające. (255 + 1 = 0, 0-1 = 255)
  • Twój program nie ma danych wejściowych. Jeśli użyjesz ,w kodzie, ustawia on bieżącą komórkę na 0.
  • Po lewej stronie pozycji początkowej nie ma komórek. Np. <.Jest niepoprawny, ale .<ważny, ponieważ wykonanie jest zakończone o godzinie .. Taśma jest niezwiązana w innym kierunku.
  • Programy z niesymetrycznymi nawiasami ( [i ]) są nieprawidłowe.
  • Twój oryginalny program może mieć mniej niż 100 bajtów, ponieważ łatwo jest go rozszerzyć do 100 bajtów bez zmiany wyniku.
  • Twój oryginalny program nie musi być prawidłowym kodem BF.

Możesz użyć tego programu python3 (link ideone), aby określić wynik swojej odpowiedzi. (W przypadku długo działających programów może być konieczne zmodyfikowanie maxstepzmiennej).

Przykład

(Dla uproszczenia program ten jest krótszy niż 100 bajtów.)

Solution: ++,+[-]+><.-,-.

Score: 3

Explanation:

Subprogram     => Output

+,+[-]+><.-,-. => 1
+,+[-]+><.-,-. => 1
+++[-]+><.-,-. => 1
++,[-]+><.-,-. => 1
++,+-]+><.-,-. => None
++,+[]+><.-,-. => None
++,+[-+><.-,-. => None
++,+[-]><.-,-. => 0
++,+[-]+<.-,-. => None
++,+[-]+>.-,-. => 0
++,+[-]+><-,-. => 255
++,+[-]+><.,-. => 1
++,+[-]+><.--. => 1
++,+[-]+><.-,. => 1
++,+[-]+><.-,- => 1

Unique outputs are [0, 1, 255]    
Score is 3 for ++,+[-]+><.-,-. (length = 15)

W przypadku remisu zwycięzcą zostaje ten z krótszym kodem. (Twój program może być krótszy niż 100 bajtów, jak podano w sekcji Szczegóły.) Jeśli kody są równej długości, zwycięzcą jest wcześniejszy plakat.

Bonusowa łamigłówka: czy bez pogrubionego ograniczenia można znaleźć program z wynikiem 100?

randomra
źródło
Rozwiązałem układankę bonusową; odpowiedź jest (ocenzurowana).
AJMansfield
@AJMansfield Czy mógłbyś edytować swój komentarz, aby inni mogli pomyśleć o układance? Np. Zmień swoje rozwiązanie na link pastebin.com, który zawiera odpowiedź.
randomra
3
Hmm Napisałem optymalizator genetyczny dla tego pytania, aby spróbować znaleźć mikro-ulepszenia istniejących odpowiedzi, ale jak dotąd nie jest to zbyt skuteczne. Utknęli odpowiednio na 79 i 43. Ach cóż - warto było spróbować!
wchargin

Odpowiedzi:

12

Wynik: 35 41 69 78 79 83

(Usuń nowy wiersz).

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

Wypróbuj online!

Nie jestem pewien, dlaczego to działa ...

Wynik: 79

X->>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>+>
+>+>+>+>+>+>+>+>+>+>+>+[>[-<+>>+<]+>[-<+>]<<<+]>>.

Wypróbuj online!

Został on miał podsumować 2 * mem [i] * I i dodać liczbę komórek (+ const), gdzie adresy są liczone od prawej do lewej strony. Mnożnik 2 i liczba komórek mogą powodować, że usuwanie + i> ma różną parzystość.

Rzeczywiście tak działało w wersji 69-punktowej. Ale najnowsza wersja to zepsuła i przez przypadek dostała coś innego. Oblicza sumę (mem [i] * i + i + 1), a usunięcie + i> robi prawie to samo, z wyjątkiem sumy (i), która ma różnicę liczby komórek, która jest również liczbą różnych danych wyjściowych do usuwania + i>.

Aby otrzymać bonus:

+. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +. +.

jimmy23013
źródło
Uwaga: jeśli przetestujesz to za pomocą dostarczonego programumaxstep oceniającego, zwiększ wartość (in def evaluate(r,maxstep=20000):), ponieważ niektóre podprogramy działają przez długi czas.
randomra 30.03.15
1
Wynik może być rzeczywiście wzrosła do 79zastępując ->+>+> ...z->,>+> ...
BrainSteel
@BrainSteel Właśnie zmieniłem to na no-op.
jimmy23013
9

Wynik: 37 43

+>-,->,+-><->-[>---+-+<[--->>+><,+>>>++<><<<+<[>--]]><><+-+>+<<+<><+++<[[<[---->-<-]>++>],>,]<,]<+-.

EDYCJA: Teraz mój program pozwala na nawiasy kwadratowe. Nie wygrywam z tym żadnych nagród, ale to właśnie dostaję za to, że niektóre ważone RNG wykonują dla mnie pracowitą pracę.

Zostało to wygenerowane przez program napisany w C.

Dla każdego Nusuniętego znaku, oto wyniki:

N = 0 => 158
N = 1 => 158
N = 2 => 158
N = 3 => 187
N = 4 => 129
N = 5 => 100
N = 6 => 158
N = 7 => 13
N = 8 => 1
N = 9 => 211
N = 10 => 129
N = 11 => 1
N = 12 => 57
N = 13 => 255
N = 14 => Mismatched Braces
N = 15 => 59
N = 16 => 11
N = 17 => 11
N = 18 => 11
N = 19 => 117
N = 20 => 11
N = 21 => 117
N = 22 => 166
N = 23 => Mismatched Braces
N = 24 => 206
N = 25 => 206
N = 26 => 206
N = 27 => 147
N = 28 => 147
N = 29 => 158
N = 30 => 148
N = 31 => 188
N = 32 => 51
N = 33 => 17
N = 34 => 84
N = 35 => 84
N = 36 => 84
N = 37 => 158
N = 38 => 158
N = 39 => 94
N = 40 => 46
N = 41 => 94
N = 42 => 94
N = 43 => 94
N = 44 => 17
N = 45 => 196
N = 46 => Mismatched Braces
N = 47 => 149
N = 48 => No Termination
N = 49 => No Termination
N = 50 => Mismatched Braces
N = 51 => Mismatched Braces
N = 52 => 45
N = 53 => 77
N = 54 => 45
N = 55 => 77
N = 56 => 50
N = 57 => 209
N = 58 => 50
N = 59 => 251
N = 60 => 249
N = 61 => 99
N = 62 => 99
N = 63 => 117
N = 64 => 89
N = 65 => 207
N = 66 => 89
N = 67 => 115
N = 68 => 115
N = 69 => 115
N = 70 => 95
N = 71 => Mismatched Braces
N = 72 => Mismatched Braces
N = 73 => 104
N = 74 => Mismatched Braces
N = 75 => No Termination
N = 76 => No Termination
N = 77 => No Termination
N = 78 => No Termination
N = 79 => Left Overflow
N = 80 => 3
N = 81 => 2
N = 82 => No Termination
N = 83 => Mismatched Braces
N = 84 => No Termination
N = 85 => 133
N = 86 => 133
N = 87 => 0
N = 88 => Mismatched Braces
N = 89 => 158
N = 90 => 0
N = 91 => 4
N = 92 => Mismatched Braces
N = 93 => 0
N = 94 => 158
N = 95 => Mismatched Braces
N = 96 => 0
N = 97 => 157
N = 98 => 159
N = 99 => None

Istnieje w sumie 37 unikalnych wyników, które są (w kolejności numerycznej):

0, 1, 2, 3, 4, 11, 13, 17, 45, 46, 50, 51, 57, 59, 77, 84, 89, 94, 95, 99,
100, 104, 115, 117, 129, 133, 147, 148, 149, 157, 158, 159, 166, 187, 188, 
196, 206, 207, 209, 211, 249, 251, 255

Jestem w 90% w 100% pewien, że to rozwiązanie nie jest optymalne , ale udowadniam, że może to być niezwykle trudne . Jest kilka rzeczy, które są jasne. Brak .symboli do momentu, gdy ostatni znak wydaje się właściwą drogą , a nawiasy kwadratowe ( []) wydają się raczej bezużyteczne . Zastanowiłem się nad tym trochę, co chciałbym przedstawić w skrócie:

Niech Lbędzie długością kodu w bajtach (w wyzwaniu 100) i nbędzie liczbą unikalnych wyników podprogramów.

W przypadku L=3, są różne rozwiązania optymalnego z postaci +-., w której n=2(w tym przypadku, wyjścia są od 1 255 do +.i -., odpowiednio). Stawia to najlepszy stosunek dla L = 3co n/L = 66.67%. Zauważ, że ten stosunek nie może być pobity przynajmniej L<10.

Dla L=10, rozwiązania są dość proste do Bruteforce. Oto wszystkie najlepsze rozwiązania na n = 6:

++>-->+<+. => 6
++>-->+<+. => 6
+++>->+<+. => 6
--->->+<+. => 6
++>---><+. => 6
+++>--><+. => 6
-->++>-<-. => 6
+++>+>-<-. => 6
--->+>-<-. => 6
-->+++><-. => 6
--->++><-. => 6

Który daje wynik punktowy na poziomie n/L = 60%.

Ponieważ L->infinityjest jasne, że stosunek musi zbliżać się do 0, ponieważ istnieje tylko 255 możliwych wyników dla potencjalnie nieskończonego L.

Współczynnik NIE zmniejsza się jednakowo. Nie jest możliwe zbudowanie rozwiązania n=6, L=9, więc najlepszym możliwym współczynnikiem L=9jest 5/9 = 55.56% < 60%.

Nasuwa się pytanie, jak szybko iw jakim zakresie stosunek maleje? Gdyż L = 100i 10^9 checks/secondtak zajęłoby kilka rzędów wielkości więcej niż czas życia wszechświata, aby brutalnie znaleźć optymalne rozwiązanie. Czy jest na to elegancki sposób? Bardzo wątpię, że jest w dół 37%do L = 100.

Współczynnik faktycznie wzrasta, aż do L=100. Zobacz inne odpowiedzi, aby potwierdzić.

Chciałbym usłyszeć wasze oceny powyższego. W końcu mogłem się okropnie mylić.

BrainSteel
źródło