Wprowadzenie
„Muhuhuhahahah!” Szalony naukowiec się śmieje. „Jesteś uwięziony w mojej małej grze!”
Przed tobą jest śmiertelna jama węży, a za tobą przepaść bez dna. Nie ma wyjścia, utknąłeś!
„Dwa kroki przed tobą to dół węża, a dwa kroki za tobą to przepaść. Ale! Zanim się ruszysz, MUSISZ zapisać sekwencję kroków, do przodu i do tyłu, i daj mi je. Ale! Ponieważ ja czuję się dzisiaj trochę zły , mogę zmusić cię do podjęcia, zamiast każdego kroku, każdego n
kroku, gdzie n
długość jest mniejsza niż długość sekwencji!
Wybierz mądrze teraz. ”
Jaka jest maksymalna liczba kroków, które możesz wykonać przed swoją nieuchronną śmiercią?
Zadanie
Powyższe intro jest zwrotem przypuszczenia Erdősa , które niedawno okazało się prawdą (jeśli chcesz dowiedzieć się więcej na ten temat, przejdź do tego filmu , autorstwa Jamesa Grime'a - „ukradłem” mu pytanie o zwrot akcji).
Odpowiedź na wprowadzenie to 11
kroki, ale nie będę zagłębiał się w dowody. Odpowiedź, jeśli odległość między tobą a dwoma „niebezpieczeństwami” to 3
kroki, to 1160
kroki, chociaż nie jest to jeszcze odpowiednio potwierdzone.
Twoim zadaniem jest stworzenie programu, który generuje najdłuższą sekwencję kroków, którą możesz wykonać dla większego x
, gdzie x
jest liczba kroków między tobą a dwoma „niebezpieczeństwami”. Twój program musi pobrać dane wejściowe x
i wygenerować prawidłową sekwencję x
.
Na potrzeby tego wyzwania +
stanowi krok naprzód i -
krok wstecz.
Zatem dane wyjściowe dla danych wejściowych 2
to:
+--+-++--++
Który działa, bez względu na to, co n
wybierze szalony naukowiec. Dla naszego prowokacji x = 5
.
UWAGA: To wyzwanie nie jest duplikatem tego lub tego wyzwania , ponieważ moje wyzwanie koncentruje się na wynikach, w przeciwieństwie do samego kodu - innymi słowy, nie jest to wyzwanie związane z golfem. Poza tym wyzwania te są oparte na tych x = 3
, które mają już ustaloną górną granicę.
Zasady:
- Cały program powinien pasować do Twojej odpowiedzi. Jeśli jednak nie pasuje, podaj dodatkowe repozytorium Github lub coś podobnego.
- Możesz zaktualizować zarówno swoją odpowiedź, jak i swój program, jeśli możesz uzyskać lepszy wynik poprzez optymalizację kodu - ale robiąc to, musisz zaktualizować wszystko z poniższej listy.
- W swojej odpowiedzi musisz mieć:
- Twój program w całości lub link do repozytorium GH hostującego Twój kod
- Liczba wygenerowanych kroków - będzie to Twój końcowy wynik .
- Musisz także podać wersję online sekwencji w Pastebin lub coś podobnego. Dzięki temu możemy sprawdzić twoją odpowiedź.
- Czas ostatniej aktualizacji twojego wyniku, więc nie muszę sprawdzać twojej historii
- NIE wolno wcześniej kodować sekwencji.
- Twój program musi działać dla wszystkich
x
(gdziex
jest liczba kroków między tobą a otchłanią i otchłanią), ale musisz tylko podać wynikx = 5
.
Odpowiedź z największym wynikiem wygrywa!
źródło
n
krok, gdzien
dowolna liczba jest mniejsza niż rozmiar sekwencji.x=5
wymagałoby poważnego przełomu, który byłby wart opublikowania. Uważa, że dla maksymalnie 1160x=3
został sprawdzony i opublikowany w 2014 roku i żadne dalsze wartości są znane. .Odpowiedzi:
Rdza, wynik = 4997216, czas = 2017-07-12 00:18 UTC
Poprawia to najlepszy wynik, jaki udało mi się znaleźć w literaturze, która wynosiła 1148805 (Ronan Le Bras, Carla P. Gomes, Bart Selman, On the Erdős Discrepancy Problem , 2014), współczynnik 4,3.
Sekwencja wyjściowa o długości 4997216
Kod źródłowy na GitHub
Bieganie
Program przyjmuje maksymalną rozbieżność jako argument (jest to x -1 w języku wyzwania, aby dostosować się do bardziej powszechnej konwencji matematycznej). Tworzy przyrostowe dane wyjściowe w lekko skompresowanym formacie, który wygląda tak dla x = 3:
gdzie
add
oznacza dołączenie sekwencji znaków na końcu bieżącej sekwencji,delete
oznacza usunięcie pewnej liczby znaków z końca bieżącej sekwencji ilength
zapewnia długość bieżącej sekwencji. W tym schemacie unika się wytwarzania wielu gigabajtów wyników pośrednich w miarę odkrywania coraz dłuższych sekwencji. Najlepszy wynik można wyodrębnić za pomocą następującego programu w języku Python:Jak to działa
Jest tu około tysiąca wierszy kodu, więc będzie to tylko bardzo ogólny przegląd.
Ograniczamy wyszukiwanie do sekwencji całkowicie multiplikatywnych (te z f ( a · b ) = f ( a ) · f ( b )), ponieważ oznacza to, że potrzebujemy jedynie skupić się na ograniczeniu sum częściowych dla n = 1, a częściowych sumy dla n ≥ 2 automatycznie spełnią tę samą granicę.
Dla każdego podłańcucha f ( i + 1),…, f ( j ) częściowo przypisanej sekwencji znaków (więc każdy element to „+”, „-” lub nieznany), zdefiniuj niebezpieczeństwo + ( i , j ), aby było dwa razy liczba „+” minus długość j - i (dla wygody pozwalamy, aby i było tak małe jak - x + 2 i przyjmujemy, że f (- x + 3) = ⋯ = f (0) = „+” dla ten cel). Zdefiniuj niebezpieczeństwo - ( i , j ) podobnie. Następnie granica sum częściowych dla n= 1 jest równoważne warunkowi, że ilekroć i ≡ j ≡ x (mod 2), niebezpieczeństwo + ( i , j ) ≤ x - 2 i niebezpieczeństwo - ( i , j ) ≤ x - 2.
Budujemy przyrostową strukturę danych, która obsługuje stałe zapytania czasowe dla podciągów o największym niebezpieczeństwie, z logarytmicznymi aktualizacjami czasu. Działa poprzez powiązanie czterech wartości:
z każdym łańcuchem o długości 2, co drugim łańcuchem o długości 4, co czwartym łańcuchem o długości 8 i tak dalej. Wartości związane z dłuższym łańcuchem można obliczyć w stałym czasie z wartości powiązanych z jego dwiema połówkami.
Ta struktura, uzupełniona pewnymi informacjami pomocniczymi, pozwala nam bardzo szybko wykonywać propagację ograniczeń i wykrywanie konfliktów na częściowych sekwencjach. Używamy go do wyszukiwania podobnego do CDCL , z propagacją jednostek, poziomami decyzji i niechronologicznym cofaniem (na razie bez uczenia klauzul), w celu uzyskania pełnych sekwencji o coraz większej długości.
Na każdym etapie wyszukiwania zgadujemy najwcześniejszy nieprzypisany znak. Heurystyka zastosowana do tego przypuszczenia jest bardzo ważna dla uniknięcia wielu cofnięć; używamy f (3 · k ) = - f ( k ), f (3 · k + 1) = '+', f (3 · k + 2) = '-'.
Wyniki
Rozbieżności wyszukiwania 0, 1 i 2 natychmiast znajdują optymalne, całkowicie multiplikatywne sekwencje o długości 0, 9 i 246.
Wyszukiwanie rozbieżności 3 blokuje się w ciągu kilku sekund w 41319, co jest dość dalekie od znanej optymalnej całkowicie multiplikatywnej sekwencji o długości 127645 znalezionej przez Le Bras i in., 2014 (i bardzo nieznacznie dłuższego niemultiplikatywnego rozszerzenia długości 130000 znalezionego wkrótce potem ), ale znacznie lepiej niż najlepiej znana sekwencja przed sekwencją o długości 17000 .
Wyszukiwanie rozbieżności 4 poprawia najdłuższą sekwencję mniej więcej nieprzerwanie przez około pięć minut, aż utknie na 4997216. Najlepsza wcześniej znana sekwencja o długości 1148805 = 9 · 127645 została rozwinięta z sekwencji rozbieżności 3 poprzez zastąpienie każdego znaku s znakiem + - - + - ++ - s . O ile wiem, tak długie sekwencje są zbyt trudne, aby ogólny solver SAT mógł je bezpośrednio poprawić (ale może ty, drogi czytelniku, możesz udowodnić, że się mylę!).
Spodziewam się, że będę musiał dodać do mojego programu klauzulę dotyczącą uczenia się, aby pokonać te bariery.
Sekwencja jako mapa bitowa 2187 × 2285
(Kliknij, aby wyświetlić w pełnej rozdzielczości.)
źródło
Haskell , wynik = 9020, czas = 2017-06-09 00:52 UTC
Wypróbuj online!
To wyniki (9 n - 1 - 1) ⋅11 / 8 dla wszystkich n . Oto kilka pierwszych wyników:
źródło