Numery w nawiasach to prosty sposób wyrażania dużych liczb całkowitych przy użyciu tylko lewego nawiasu, spacji i prawego nawiasu ( [ ]).
Numer nawiasu definiuje się jako ciąg jednej lub więcej par pasujących nawiasów [...]zwanych porcjami , każdy oddzielony od sąsiadów przez zero lub więcej spacji.
Liczba spacji między poszczególnymi porcjami określa hiperoperację między nimi. Brak spacji oznacza dodawanie, 1 spacja oznacza mnożenie, 2 spacje oznacza potęgowanie, 3 spacje oznacza tetrację i tak dalej. Hiperoperacje wyższego rzędu mają pierwszeństwo, więc tetracja występuje przed potęgowaniem, potęgowanie występuje przed pomnożeniem itp. Są one również asocjacyjne z prawej strony, więc a^b^cjest obliczane jako a^(b^c). (Ale a^b*cnadal jest (a^b)*c.)
Każda porcja może być pusta ( []) lub zawierać inny numer nawiasu. Puste porcje mają wartość 0. Niepuste porcje mają wartość zawartego numeru nawiasu plus 1.
Przykłady: ( ^^jest tetracja, ^^^jest pentation )
[[]]ma wartość 1, ponieważ jest[]zwiększana o 0 ( ) o 1[[[]]]ma wartość 2, ale tak samo,[[]][[]]ponieważ dwa ([[]]) są dodawane[[[]]] [[[[]]] [[[[]]]]][[[]]]ma wartość 20 = (2 * ((2 ^ 3) +1)) + 2[[[]]] [[[[]]]]ma wartość 65536 = 2 ^^^ 3 = 2 ^^ (2 ^^ 2) = 2 ^^ 4 == 2 ^ (2 ^ (2 ^ 2))[[[[]]]] [[[]]] [[]]ma wartość 7625597484987 = 3 ^^^ (2 ^^^ 1) = 3 ^^^ 2 = 3 ^^ 3 = 3 ^ (3 ^ 3)
W poprawnych numerach nawiasów:
- Nigdy nie będzie spacji wiodących ani końcowych.
- Zawsze będzie co najmniej jedna para pasujących nawiasów.
- Wszystkie lewe nawiasy będą mieć pasujący prawy nawias.
- Spacja nigdy nie pojawi się bezpośrednio po prawej
[ani po lewej stronie]. - Wartość jest zawsze liczbą całkowitą nieujemną.
Wyzwanie
Zauważ, że może być wiele formularzy dla numeru nawiasu, które dają tę samą wartość. [[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]i [[[]]] [[[[]]]]oba reprezentują 16, ale ta ostatnia jest znacznie krótsza.
Wyzwaniem jest napisanie algorytmu, który będzie próbował znaleźć najkrótszą reprezentację liczby w nawiasach dla danej wartości. Na przykład uważam, że najkrótszym sposobem przedstawienia 16 jest użycie 17 znaków jako [[[]]] [[[[]]]].
Punktacja (zaktualizowana)
Niech S będzie zbiorem liczb całkowitych od 1 do 256 (włącznie), a także dziesięciu następujących wartości:
8191 13071 524287 2147483647 1449565302 1746268229 126528612 778085967 1553783038 997599288
(Pierwsze 4 to liczby pierwsze Mersenne, pozostałe są losowe).
Zgłoszenie, które generuje najkrótszy zestaw numerów w nawiasach dla wszystkiego w S. wygra. Twój wynik to suma długości liczb w nawiasach dla wszystkich wartości w S (im mniejsza, tym lepiej).
Wraz z kodem prześlij listę numerów nawiasów dla wszystkich liter S , dokładna kolejność nie jest szczególnie ważna. na przykład:
1=[[]]
2=[[[]]]
3=[[[[]]]]
...
2147483647=[...]
...
(Wiem, że nie jest to optymalna metoda oceniania, ale nie jestem skonfigurowany do przeprowadzania losowych testów heurystycznych przy każdym przesyłaniu. Przepraszam :()
Zasady
- Być może nie hardcode żadnych numerów wspornika oprócz banalnych rozwiązań przyrostowych (
[], [[]], [[[]]], ...). Twój program musi faktycznie szukać optymalnie krótkich reprezentacji. (Chociaż wyniki mogą być nieoptymalne.) - Twój algorytm powinien działać dla wszystkich nieujemnych liczb całkowitych poniżej 2 147 483 648 (2 ^ 31). Nie możesz szczególnie skupiać się na wartościach w S .
- Dla każdego konkretnego wejścia twój algorytm powinien uruchomić się najwyżej 10 minut na przyzwoitym nowoczesnym komputerze (procesor ~ 2,5 Ghz, ~ 6GB RAM).
- W (pozornie) rzadkiej szansie na remis wygrywa najwyżej ocenione zgłoszenie.
- Jeśli skopiujesz inne rozwiązanie lub poprawisz je bez przypisania, zostaniesz zdyskwalifikowany.
źródło
Odpowiedzi:
Python 11455b
To rozwiązanie ma chciwe podejście do szukania sposobów na rozbicie liczb pierwszych, a nie podejście wyczerpujące. Potrzebuję 9875b dla 1-256 w porównaniu do 8181 dla prawdopodobnie optymalnego rozwiązania Martina w tej przestrzeni.
Większa tabela wyników mnożenia i potęgowania daje nieznaczną poprawę w większych przypadkach testowych. Poniższe rozwiązanie zajęło około 7 minut. Wydłużenie czasu pracy powyżej 30 minut ma minimalny wpływ na wydajność.
Ja, podobnie jak Martin, miałem problem z pierwszeństwem. Moje rozwiązanie polegające na ograniczeniu wyboru operacji może nie być optymalne.
Wynik:
źródło
Matematyka
Uwaga: Ten algorytm nigdy nie będzie w stanie zbliżyć się do większych liczb testowych. Potrzebowałbym zupełnie innego podejścia, więc zostawię to tak, jak inni sprawdzają swoje niższe liczby. Możesz uznać to przesłanie za nieprawidłowe.
Oto początek dla pierwszych 256 liczb (pozostałe zostały dodane po rozpoczęciu i prawdopodobnie muszę znaleźć dla nich osobne rozwiązanie)
Całkowita długość pierwszych 256 cyfr wynosi 7963 znaków. Nie wiem czy to jest optymalne.
Ignorując dodanie, wyniki dla 8191 i 13071 znaleziono w kilka sekund, a 524387 w kilka minut jako
w 164 znaków łącznie.
Oto kod:
Użyłem wyczerpującego wyszukiwania aż do potęgowania. Nie ma operacji tetracyjnych ani wyższych rzędów. Właśnie wypróbowałem operacje wyższego rzędu ręcznie i jest tylko kilka kombinacji, które faktycznie dają liczby poniżej 2 31 , więc po prostu zakodowałem te, które działają.
Edycja: Moje poprzednie rozwiązanie nie przejmowało się priorytetem, po prostu zrzuciło wszystko.
Teraz myślę, że mój nowy kod to naprawił,ale żaden z pierwszych 256 numerów się nie zmienił, ani 8191 (który był ważny wcześniej, sprawdziłem) ... i jest już za późno, aby powiedzieć teraz, czy mój kod rzeczywiście to naprawił . Jutro przyjrzę się jeszcze raz i dodam wyjaśnienie, ponieważ teraz przy sprawdzaniu pierwszeństwa jest nieco skomplikowane (mam nadzieję, że powinno to skrócić czas wyszukiwania).Edycja: OK, zgodnie z oczekiwaniami pojawiły się błędy. Myślę, że to naprawiłem teraz, zwiększając całkowitą długość dla 1 - 256 do 7963 . Nie jestem pewien, czy jest to już optymalne, ponieważ może być możliwe znalezienie krótszych rozwiązań z części nieoptymalnych, jeśli pozwalają one na operacje wyższego rzędu. Wyjaśnienie nastąpi, gdy uda mi się trochę wyczyścić kod.
źródło
Python 9219b
To mój drugi wpis. Zacząłem od zera i wypróbowałem nowy układ danych, w tym użycie pakietu blist do sortowania list i nagrań oraz kilka nowych podejść do znajdowania dużych rozwiązań. Myślę, że mam optymalną 1-256. Zwiększenie czasu działania z 30 do 4 m skróciło duże przypadki testowe o około 30 bajtów.
Wynik:
7944b dla 1-256
1275b dla dużych skrzynek
źródło