Labirynt na siatce N przez N kwadratowych komórek jest definiowany przez określenie, czy każda krawędź jest ścianą, czy nie. Wszystkie zewnętrzne krawędzie są ścianami. Jedna komórka jest zdefiniowana jako początek , a jedna komórka jest zdefiniowana jako wyjście , a wyjście jest osiągalne od początku. Początek i koniec nigdy nie są tą samą komórką.
Pamiętaj, że ani początek, ani wyjście nie musi znajdować się na zewnętrznej granicy labiryntu, więc jest to prawidłowy labirynt:
Ciąg „N”, „E”, „S” i „W” oznacza próbę przejścia odpowiednio na północ, wschód, południe i zachód. Ruch blokowany przez ścianę jest pomijany bez ruchu. Łańcuch wychodzi z labiryntu, jeśli zastosowanie go od początku powoduje, że wyjście jest osiągane (niezależnie od tego, czy ciąg kontynuuje po osiągnięciu wyjścia).
Zainspirowany to pytanie puzzling.SE dla których XNOR przewidzianego do udowodnienia sposób rozwiązać z bardzo długim ciągiem, napisać kod, który może znaleźć jeden ciąg, który wychodzi każdy 3 przez 3 labirynt.
Z wyłączeniem nieprawidłowych labiryntów (rozpoczęcie i wyjście z tej samej komórki lub wyjście niedostępne od początku) istnieje 138 172 prawidłowych labiryntów i ciąg musi wyjść z każdego z nich.
Ważność
Ciąg musi spełniać następujące warunki:
- Składa się tylko z liter „N”, „E”, „S” i „W”.
- Wychodzi z dowolnego labiryntu, do którego jest stosowany, jeśli zaczyna się na początku.
Ponieważ zestaw wszystkich możliwych labiryntów obejmuje każdy możliwy labirynt z każdym możliwym ważnym punktem początkowym, oznacza to automatycznie, że łańcuch opuści każdy labirynt z dowolnego prawidłowego punktu początkowego. Oznacza to, że z dowolnego punktu początkowego, z którego można dotrzeć do wyjścia.
Zwycięski
Zwycięzca to odpowiedź, która zawiera najkrótszy prawidłowy ciąg i zawiera kod użyty do jego wytworzenia. Jeśli więcej niż jedna z odpowiedzi podaje ciąg o tej najkrótszej długości, wygrywa ten, który opublikuje ten ciąg.
Przykład
Oto przykładowy ciąg o długości 500 znaków, który da ci coś do pokonania:
SEENSSNESSWNNSNNNNWWNWENENNWEENSESSNENSESWENWWWWWENWNWWSESNSWENNWNWENWSSSNNNNNNESWNEWWWWWNNNSWESSEEWNENWENEENNEEESEENSSEENNWWWNWSWNSSENNNWESSESNWESWEENNWSNWWEEWWESNWEEEWWSSSESEEWWNSSEEEEESSENWWNNSWNENSESSNEESENEWSSNWNSEWEEEWEESWSNNNEWNNWNWSSWEESSSSNESESNENNWEESNWEWSWNSNWNNWENSNSWEWSWWNNWNSENESSNENEWNSSWNNEWSESWENEEENSWWSNNNNSSNENEWSNEEWNWENEEWEESEWEEWSSESSSWNWNNSWNWENWNENWNSWESNWSNSSENENNNWSSENSSSWWNENWWWEWSEWSNSSWNNSEWEWENSWENWSENEENSWEWSEWWSESSWWWNWSSEWSNWSNNWESNSNENNSNEWSNNESNNENWNWNNNEWWEWEE
Dziękujemy orlp za przekazanie tego.
Tabela liderów
Równe wyniki są wymienione w kolejności zamieszczania tego wyniku. Nie musi to być kolejność, w jakiej odpowiedzi zostały opublikowane, ponieważ wynik dla danej odpowiedzi może być z czasem aktualizowany.
Sędzia
Oto walidator Python 3, który pobiera ciąg NESW jako argument wiersza poleceń lub przez STDIN.
W przypadku niepoprawnego ciągu da to wizualny przykład labiryntu, dla którego zawodzi.
źródło
Odpowiedzi:
C ++,
979593918683828179 znakówMoja strategia jest dość prosta - algorytm ewolucji, który może rosnąć, zmniejszać się, zamieniać elementy i mutować prawidłowe sekwencje. Moja logika ewolucji jest teraz prawie taka sama jak @ Sp3000, ponieważ była to poprawa w stosunku do mojej.
Jednak moja implementacja logiki labiryntu jest dość sprytna. To pozwala mi sprawdzić, czy ciągi są poprawne przy prędkości blisteringu. Spróbuj to rozgryźć, patrząc na komentarz
do_move
iMaze
konstruktora.źródło
do_move
jest teraz niesamowicie szybki.Python 3 + PyPy,
8280 znakówWahałem się, czy opublikować tę odpowiedź, ponieważ w zasadzie podjąłem podejście orlp i rzuciłem na to swój własny obrót. Ten ciąg został znaleziony, zaczynając od pseudolosowego rozwiązania o długości 500 - spora liczba nasion została wypróbowana, zanim udało mi się pobić aktualny rekord.
Jedyną nową dużą optymalizacją jest to, że patrzę tylko na jedną trzecią labiryntów. Dwie kategorie labiryntów są wyłączone z wyszukiwania:
<= 7
dostępne są kwadratyChodzi o to, że każdy ciąg rozwiązujący pozostałe labirynty powinien również rozwiązać powyższe automatycznie. Jestem przekonany, że jest to prawdą w przypadku drugiego typu, ale zdecydowanie nie jest prawdą w przypadku pierwszego, więc dane wyjściowe będą zawierały fałszywe alarmy, które należy sprawdzić osobno. Tym fałszywym pozytywom zwykle brakuje tylko około 20 labiryntów, więc pomyślałem, że to dobry kompromis między szybkością i dokładnością, a także dałoby strunie nieco więcej przestrzeni do mutacji.
Początkowo przeglądałem długą listę heurystyk wyszukiwania, ale przerażająco żadne z nich nie wymyśliło niczego lepszego niż około 140.
źródło
0
nan
ścieżce i załóżmy, że ciągS
dostaje od0
celun
. NastępnieS
przenosi cię z dowolnej komórki pośredniejc
don
. Załóżmy inaczej. Niecha(i)
będzie pozycja poi
krokach zaczynających się od0
ib(i)
zaczynających się odc
. Następniea(0) = 0 < b(0)
, każdy krok zmienia sięa
ib
najwyżej o 1, ia(|S|) = n > b(|S|)
. Weź najmniejszyt
taki, żea(t) >= b(t)
. Najwyraźnieja(t) != b(t)
byłyby zsynchronizowane, więc muszą zamieniać miejsca krok po krokut
, poruszając się w tym samym kierunku.C ++ i biblioteka z lingelingiem
Stosując podejście oparte na SAT , mogłem całkowicie rozwiązać podobny problem dla labiryntów 4x4 z zablokowanymi komórkami zamiast cienkich ścian i ze stałymi pozycjami początkowymi i wyjściowymi w przeciwległych rogach. Miałem więc nadzieję, że uda mi się wykorzystać te same pomysły do rozwiązania tego problemu. Jednakże, chociaż dla drugiego problemu użyłem tylko 2423 labiryntów (w międzyczasie zaobserwowano, że 2083 wystarczy) i ma rozwiązanie o długości 29, kodowanie SAT wykorzystało miliony zmiennych, a jego rozwiązanie zajęło kilka dni.
Postanowiłem więc zmienić podejście na dwa ważne sposoby:
Zrobiłem także pewne optymalizacje, aby użyć mniej zmiennych i klauzul jednostkowych.
Program oparty jest na @ orlp's. Ważną zmianą był wybór labiryntów:
is_solution
sprawdza, czy wszystkie osiągalne pozycje są osiągnięte.W ten sposób otrzymuję 10772 labiryntów z pozycjami początkowymi.
Oto program:
Pierwszy
configure.sh
i Solver, a następnie skompilować program ze coś takiego , gdzie jest ścieżka gdzie resp. są, więc oba mogą być na przykład . Lub po prostu umieść je w tym samym katalogu i nie używaj opcji i .make
lingeling
g++ -std=c++11 -O3 -I ... -o m3sat m3sat.cc -L ... -llgl
...
lglib.h
liblgl.a
../lingeling-<version>
-I
-L
Program trwa jedną obowiązkową wiersza poleceń argumentu ciąg składający się z
N
,E
,S
,W
(dla stałych kierunków) lub*
. Możesz więc wyszukać ogólne rozwiązanie o rozmiarze 78, podając ciąg 78*
s (w cudzysłowach), lub wyszukaj rozwiązanie, zaczynającNEWS
odNEWS
poprzedzających go tylu,*
ile chcesz , aby wykonać dodatkowe kroki. Jako pierwszy test weź swoje ulubione rozwiązanie i zamień niektóre litery na*
. Szybko znajduje to rozwiązanie dla zaskakująco wysokiej wartości „niektórych”.Program powie, który labirynt dodaje, opisany przez strukturę ściany i pozycję początkową, a także poda liczbę dostępnych pozycji i ścian. Labirynty są sortowane według tych kryteriów i dodawany jest pierwszy nierozwiązany. Dlatego większość dodanych labiryntów ma
(9/4)
, ale czasami pojawiają się również inne.Wziąłem znane rozwiązanie o długości 79 i dla każdej grupy sąsiadujących 26 liter próbowałem zastąpić je dowolnymi 25 literami. Próbowałem także usunąć 13 liter od początku i od końca i zastąpić je dowolnymi 13 na początku i dowolnymi 12 na końcu i odwrotnie. Niestety wszystko wyszło niezadowalająco. Czy możemy zatem uznać to za wskaźnik, że długość 79 jest optymalna? Nie, podobnie próbowałem ulepszyć rozwiązanie o długości 80 do długości 79, ale to też nie powiodło się.
Wreszcie próbowałem połączyć początek jednego rozwiązania z końcem drugiego, a także z jednym rozwiązaniem przekształconym przez jedną z symetrii. Teraz brakuje mi ciekawych pomysłów, więc postanowiłem pokazać ci, co mam, mimo że nie doprowadziło to do nowych rozwiązań.
źródło