To pytanie jest pierwszym z kilku wyzwań związanych z urodzinami Brain-flak zaprojektowanych z okazji pierwszych urodzin Brain-Flak! Więcej informacji na temat urodzin Brain-Flaka można znaleźć tutaj

Zeszłego lata mieliśmy Brain-flak Integer Metagolf , a wygenerowane odpowiedzi były bardzo przydatne dla społeczności Brain-Flak. Najważniejszą rzeczą, która sprawia, że ​​Integer Metagolf jest tak skuteczny, jest technika o nazwie hardcoding Multiplication.

W Brain-Flak zwielokrotnienie czasu wykonania jest niezwykle kosztowne. Najkrótszy znany fragment mnożenia to:

({}<>)({<({}[()])><>({})<>}{}<><{}>)

Odkryte przez Megatom

Istnieje jednak bardzo prosty sposób na pomnożenie czasu kompilacji. Na przykład następujący kod zostanie pomnożony przez 5:

 (({})({})({})({}){})

Wypróbuj online!

Działa to, ponieważ kolejne wyrażenia są dodawane razem. Każdy z nich ({})nic nie robi na stosie ( {}wyskakuje i (..)odsuwa go z powrotem) i ocenia wszystko, co znajduje się na stosie. Wszystkie te wyrażenia razem sumują się nawet pięciokrotnie, niezależnie od tego, co było na górze stosu.

Dla dowolnego nnastępującego wyrażenia ciąg utworzy fragment, który zwielokrotni górę stosu przez n:

"("+"({})"*(n-1)+"{})"

Działa to poprzez tworzenie nwyrażeń, które wszystkie oceniają na górę stosu. Pierwszy n-1nie zmienia niczego, a ostatni usuwa wierzch stosu przed pchnięciem.

W przypadku liczb zespolonych można połączyć wiele mniejszych wyrażeń, aby zaoszczędzić bajty. Na przykład możesz pomnożyć przez 25, mnożąc dwukrotnie przez 5:

(({})({})({})({}){})(({})({})({})({}){})

Jest to dość proste i dla niektórych liczb działa całkiem dobrze, ale istnieją lepsze sposoby na to. Na przykład jedna metoda, którą wymyśliłem, wykorzystuje binarną reprezentację liczby. ( Oto implementacja Pythona ) Ta nowa metoda jest o wiele bardziej skuteczna niż proste wyrażenie łańcuchowe pokazane wcześniej, ale to nie koniec, istnieje wiele interesujących sposobów mnożenia kodu i prawdopodobnie tona, której nikt jeszcze nie odkrył.

Myślę więc, że nadszedł czas, aby zobaczyć, jak dobrze możemy uzyskać.

Krótki przegląd Brain-Flak

Oto opis wszystkiego, co musisz wiedzieć o Brain-Flak do tego wyzwania.

Brain-Flak ma „nilady” i „monady”. Nilady to nawiasy, w których nie ma nic. Każdy nilad robi coś i zwraca wartość. W przypadku tego wyzwania dwie nilady, którymi się zajmujemy, to {}i <>. {}wyskakuje u góry aktywnego stosu i zwraca jego wartość. <>przełącza aktywny stos i aktywny stos, tak że aktywny stos staje się nieaktywny, a nieaktywny stos staje się aktywny, zwraca zero.

Monady są nawiasami, w których są rzeczy. Biorą jeden argument, sumę wszystkiego w sobie, czasami wykonują akcję, a następnie zwracają wartość. Te trzy, którymi się zajmujemy, to (...): <...>i [...]. Najważniejsza monada tego wyzwania (...)przyjmuje wartość wnętrza i wypycha ją na aktywny stos. Następnie zwraca argument. <...>i [...]oba są „obojętnymi” monadami, tzn. nie wykonują żadnej akcji, a raczej modyfikują przekazywaną wartość. <...>zawsze zwraca zero niezależnie od przekazanego argumentu. Tymczasem [...]zawsze zwraca czasy argumentów -1.

Przykładowe programy z wyjaśnieniem

Jeśli nigdy nie programowałeś w Brain-Flak, dobrym pomysłem może być zapoznanie się z przykładowymi programami przy użyciu opisanych operacji

({}{})

Dodaje to dwie najlepsze liczby ze stosu. Każdy {}zrzuca wartość ze stosu i (...)odsuwa swoją sumę z powrotem.

({}[{}])

Podobnie odejmuje to drugi element na stosie od pierwszego. Tak jak poprzednio, każda {}wyskakuje wartość, ale [..]około druga powoduje jej dodanie. Ponownie (...)przesuwa sumę.

({}<{}>)

To usuwa drugą wartość ze stosu, pozostawiając najwyższą wartość nietkniętą. Działa tak jak dwa ostatnie, z tą różnicą, że druga wartość jest wyciszona przez, <...>więc push wypycha tylko pierwszą wartość z powrotem.

(({}))

To tworzy drugą kopię wartości na górze stosu. Robi to, {}podnosząc górną część stosu, aby uzyskać jego wartość, a (..)następnie najpierw wypycha go z powrotem, oceniając do wartości. Drugi (...)pobiera wartość zwróconą przez pierwszą i wypycha ją również na stos. tworzenie drugiej kopii.

Zadanie

Biorąc pod uwagę liczbę całkowitą, nutwórz fragment kodu Brain-Flak, który czyści stos, który zwielokrotnia górę bieżącego stosu przez n.

Możesz używać następujących operacji Brain-Flak

(...) -> Push Monad, Pushes the result of its contents
<...> -> Zero Monad, Returns zero
[...] -> Negative Monad, Returns the opposite of its contents result
{}    -> Pop nilad, Pops the TOS and returns its value
<>    -> Switch nilad, Switches the active and inactive stack

Inne operacje są zakazane na potrzeby wyzwania.

Punktacja

Twój wynik będzie sumą długości wszystkich programów od n=2do n=10000. Pamiętaj o dołączeniu linku do danych wyjściowych programu w celu weryfikacji.

Ruby, 669856

$answers = Hash.new{|hash,n|
  valid = []
  2.upto(n**0.5){|i|
    valid.push("("+hash[n/i]+")"+"({})"*(i-2)+"{}") if n%i == 0
  }
  valid.push("({})"+hash[n-1])
  (hash[n] = valid.min_by{|s| s.length})
}
$answers[1] = "{}"

def full_answer n
  "("+$answers[n]+")"
end

To jest szybka odpowiedź wyjściowa. Znaleziono tutaj pierwsze 1000 min-programów . (Próbowałem opublikować wszystkie, ale to przeciążało maksymalny rozmiar pastebinu). Mogę dodać wyjaśnienie kodu później.

Przykłady:

360:    ((((((({})(({}){}){})({}){})({}){}){}){}){})
4608:   (((((((((((({})({}){})({}){}){}){}){}){}){}){}){}){}){})
9991:   (({})((({})(((((((({})((({})({}){}){}){}){}){}){}){}){}){}){})({}){}){})