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ę na0
. - 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 maxstep
zmiennej).
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?
źródło
Odpowiedzi:
Wynik:
354169787983(Usuń nowy wiersz).
Wypróbuj online!
Nie jestem pewien, dlaczego to działa ...
Wynik: 79
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:
źródło
maxstep
oceniającego, zwiększ wartość (indef evaluate(r,maxstep=20000):
), ponieważ niektóre podprogramy działają przez długi czas.79
zastępując->+>+> ...
z->,>+> ...
Wynik:
3743EDYCJA: 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
N
usuniętego znaku, oto wyniki:Istnieje w sumie 37 unikalnych wyników, które są (w kolejności numerycznej):
Jestem w
90% w100% 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 (. Zastanowiłem się nad tym trochę, co chciałbym przedstawić w skrócie:[]
) wydają się raczej bezużyteczneNiech
L
będzie długością kodu w bajtach (w wyzwaniu100
) in
będzie liczbą unikalnych wyników podprogramów.W przypadku
L=3
, są różne rozwiązania optymalnego z postaci+-.
, w którejn=2
(w tym przypadku, wyjścia są od 1 255 do+.
i-.
, odpowiednio). Stawia to najlepszy stosunek dlaL = 3
con/L = 66.67%
. Zauważ, że ten stosunek nie może być pobity przynajmniejL<10
.Dla
L=10
, rozwiązania są dość proste do Bruteforce. Oto wszystkie najlepsze rozwiązania nan = 6
:Który daje wynik punktowy na poziomie
n/L = 60%
.Ponieważ
L->infinity
jest jasne, że stosunek musi zbliżać się do 0, ponieważ istnieje tylko 255 możliwych wyników dla potencjalnie nieskończonegoL
.Współczynnik NIE zmniejsza się jednakowo. Nie jest możliwe zbudowanie rozwiązania
n=6, L=9
, więc najlepszym możliwym współczynnikiemL=9
jest5/9 = 55.56% < 60%
.Nasuwa się pytanie, jak szybko iw jakim zakresie stosunek maleje? Gdyż
L = 100
i10^9 checks/second
tak 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%
doL = 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ć.źródło