Opis
Wyimaginowany język programowania (IPL) używa polskiej odwrotnej notacji. Ma następujące polecenia:
- i - wprowadź liczbę i pchnij ją na stos
- o - nieniszcząca moc wyjściowa na szczycie stosu (liczba pozostaje na stosie)
- d - odrzuć wierzch stosu
- liczba całkowita - pchnij ten numer na stos
- + - * - wyłóż dwie liczby ze stosu, wykonaj odpowiednią operację i odepchnij wynik. W IPL nie ma podziału.
IPL działa tylko z liczbami całkowitymi i służy do prostych obliczeń. Program IPL jest zapisany w jednym wierszu i oddzielony spacjami. Pusty ciąg jest prawidłowym programem IPL.
Program IPL:
i i + o
Wpisuje dwie liczby, dodaje je razem i wyświetla wynik.
Liczby wejściowe i liczby całkowite, które można wypychać na stos, znajdują się w zakresie [-999, 999], jednak dane wyjściowe mogą być dowolne. Jeśli twój język nie obsługuje dużych liczb, jest to w porządku.
Format wejścia / wyjścia
Możesz wybrać dowolny format wejściowy / wyjściowy, o ile zrozumiałe i odczytywane / zapisywane są: ciąg, lista, tokeny itp.
Zadanie
Otrzymujesz program IPL, musisz go zoptymalizować (zmniejszyć długość):
i 12 + 3 + o d 2 3 + d
Po optymalizacji stanie się
i 15 + o
Nie musisz zachowywać stanu stosu, ale ilość wejść i wyjść oraz ich kolejność powinny odpowiadać oryginalnemu i zoptymalizowanemu programowi.
Więc program IPL:
-40 i * 2 * o i + 3 1 + o i 2 *
Po optymalizacji stanie się
i -80 * o i 4 o i
lub
-80 i * o i 4 o i
(pamiętaj, że musisz zapisać wszystkie dane wejściowe, nawet jeśli są one nieistotne).
Nie powinno być żadnego twardego kodowania dla przypadków testowych, kod powinien działać na dowolnym dowolnym programie IPL i generować możliwie najkrótszy program IPL, który spełnia wymagania.
Punktacja
Domyślna punktacja golfa.
AKTUALIZACJA: zmieniono punktację na czystą ocenę golfa, zgodnie z sugestią @Sanchises.
Przypadki testowe:
Wkład:
(empty string)
Możliwe wyjście:
(empty string)
Wkład:
i 4 * 2 + 3 * 6 - o
Możliwe wyjście:
i 12 * o
Wkład:
1 1 + o
Możliwe wyjście:
2 o
Wkład:
i 2 + 3 + o d 2 3 + d
Możliwe wyjście:
i 5 + o
Wkład:
-40 i * 2 * o i + 3 1 + o i 2 *
Możliwe wyjście:
-80 i * o i 4 o i
Wkład:
i i 1 + i 1 + i 1 + i 1 + d d d d o
Możliwe wyjście:
i i i i i d d d d o
Wkład:
i i i 0 * * * o
Możliwe wyjście:
i i i 0 o
Wkład:
i i i 1 * * * o
Możliwe wyjście:
i i i * * o
Wkład:
i 222 + i 222 - + o
Możliwe wyjście:
i i + o
Wkład:
i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o
Możliwe wyjście:
i i i i i o 1 o
Wkład:
i 1 + 2 * 1 + o
Możliwe wyjście:
i 2 * 3 + o
Wkład:
1 1 + o i 2 + 3 + o d 2 3 + d 4 i * 2 * o i + 3 1 + o i 2 * i i 1 + i 1 + i 1 + i 1 + d d d d o i i i 0 * * * o i i i 1 * * * o i 2 + i 2 - + o i 2 + 3 * 2 + 3 * 2 + 3 * i * d i 2 + 3 * i + d i o 2 + 2 - 0 * 1 o
Możliwe wyjście:
2 o i 5 + o 8 i * o i 4 o i i i i i i d d d d o i i i 0 o i i i * * * o i i + o i i i i i o 1 o
źródło
i i d o
doi o i
(wejście jest w porządku, a wyjście jest w porządku) albo nie należy go uprościć? (zestaw wejść i wyjść powinien być w porządku)Odpowiedzi:
Wolfram Language (Mathematica) ,
733728690564516506513548 bajtówWypróbuj online!
Jest to czteroetapowy tour-de-force, który (1) zamienia „-” na „-1 * +”, abyśmy nie musieli radzić sobie z odejmowaniem, (2) nieco upraszcza listę poleceń ( 3) tworzy listę wszystkich permutacji z tej listy poleceń i wybiera te, które dają ten sam wynik podczas analizowania (wykonywania), oraz (4) upraszcza nieco te listy poleceń i wybiera najkrótsze, po konwersji niektórych operacji z powrotem na odejmowanie.
Ten kod jest strasznie nieefektywny, ponieważ przechodzi przez listę wszystkich permutacji kodu wejściowego. W przypadku długich kodów wejściowych nie polecam uruchamiania tego kodu; ale kiedy go czytam, w tym wyzwaniu nie ma żadnych ograniczeń czasu wykonywania ani pamięci.
Ten kod wykonuje krok optymalizacji po przekonwertowaniu wszystkich operacji „-” na operacje „+” z odwróconymi znakami i dopiero na końcu ponownie wprowadza operator „-” podczas konwersji kodu z powrotem na ciągi znaków. Oznacza to na przykład, że „i -1 i * + o” jest poprawnie zoptymalizowane do „ii - o”.
Ponieważ wymagania dotyczące formatu we / wy są dość luźne, kod ten przyjmuje i zwraca kod jako listy, gdzie symbole „+”, „-”, „*” są reprezentowane odpowiednio przez p, m, t, tokeny. Konwersja zi na łańcuchy odbywa się w funkcji otoki podanej w TIO:
Wersja bez gry w golfa, w tym opakowanie formatu łańcucha i minimalizowanie końcowej długości łańcucha kodu zamiast liczby tokenów, a także kilka dodatkowych drobiazgów transformacji:
Dzięki @redundancy za wyłapanie błędu: Analizator wymaga
Expand
zastosowania wyjścia, aby obsłużyć równoważność dystrybucyjną. 506 → 513aktualizacja
Teraz również optymalizuje się
1 o 1 + o
do1 o 2 o
. Był to zaskakująco trudny przypadek, który spowodował spowolnienie kodu. 513 → 548źródło
i i 1 + i 1 + i 1 + i 1 + d d d d o
.i 2 * i 2 * + o
powinny generować zoptymalizowane dane wyjściowei i + 2 * o
, ale ten kod zwraca (niezoptymalizowane) dane wejściowe.