Twoim zadaniem jest odgrywanie ról obu postaci w tej scenie od początku. Cobb daje Ariadnie wyzwanie:
Masz dwie minuty na zaprojektowanie labiryntu, którego rozwiązanie zajmuje jedną minutę.
Niektóre wolności zostaną uwzględnione w tym opisie. Co najważniejsze, to wyzwanie nie jest oparte na czasie, a wyniki oparte są na skuteczności twoich labiryntów i rozwiązujących labirynt.
Przepraszam za wiele zmian tego wyzwania, gdy przechodzimy do łatwego i sprawiedliwego formatu.
Część I: Format labiryntu
Wszystkie labirynty są kwadratowe. Komórka w labiryncie jest reprezentowana jako krotka o zerowym indeksie row column
.
Ściany są reprezentowane przez dwa ciągi binarne: jeden dla ścian poziomych (które blokują ruch między rzędami) i ścian pionowych (odwrotnie). W NxN
labiryncie są Nx(N-1)
możliwe ściany każdego typu. Weźmy przykład 3x3, w którym komórki są oznaczone:
A B | C
---
D | E F
---
G H | I
wszystkie możliwe pionowe ściany są: AB BC DE EF GH HI
. Przełożone na sznurek ściany pokazane są 011001
dla ścian pionowych i 010010
dla ścian poziomych. Również przez „ciąg binarny” rozumiem „znaki” 0 i „1”.
Pełny format labiryntu to ciąg znaków, który zawiera w następującej kolejności:
- szerokość
- rozpocznij krotkę komórki
- krotka końcowa komórki
- poziome ściany
- pionowe ściany
Na przykład ten labirynt:
0 1 2 3 4
_________
0 | | E| _|
1 | _|_|_ |
2 |_ _ _ | |
3 | _ _ | |
4 |____S|___|
start:(4,2)
end:(0,2)
jest sformatowany do tego:
5
4 2
0 2
00001011101110001100
10100110000100010010
Część II: Architekt
Program Architekt tworzy labirynt. Musi grać zgodnie z zasadami i zapewniać prawidłowy labirynt (taki, w którym istnieje rozwiązanie, a końca nie ma na początku).
Dane wejściowe: dwie dodatnie liczby całkowite:
size [random seed]
Gdzie size
będzie [15, 50]
. Zachęcamy do skorzystania z losowego materiału siewnego, aby można było odtworzyć mecze, chociaż nie jest to wymagane.
Dane wyjściowe: Labirynt prawidłowy rozmiar x rozmiar (kwadrat) przy użyciu formatu opisanego w części I. „ważny” oznacza, że istnieje rozwiązanie, a komórka początkowa nie jest równa komórce końcowej.
Ocena architekta w danym labiryncie wynosi
# steps taken to solve
–––––––––––––––––––––––––––––
max(dist(start,end),(# walls))
Architekci są więc nagradzani za skomplikowane labirynty, ale karani za każdą zbudowaną ścianę (jest to substytut ograniczenia czasowego Ariadny). Thedist()
Funkcja ta zapewnia, że labirynt bez ścian nie dostaje nieskończoną wynik. Zewnętrzne granice labiryntu nie wpływają na liczbę ścian.
Część III: Solver
Solver próbuje rozwiązać labirynty generowane przez architektów innych osób. Jest coś w rodzaju mgły wojny: uwzględniane są tylko ściany przylegające do odwiedzanych komórek (wszystkie inne są zastępowane przez „?”)
wejście: ten sam format labiryntu, ale z „?” gdzie ściany są nieznane, dodatkowy wiersz dla bieżącej lokalizacji i oddzielona przecinkami lista prawidłowych wyborów z tej lokalizacji. (Jest to duża edycja, która ma na celu uproszczenie pisania funkcji parsowania labiryntu)
przykład (taki sam jak powyższy labirynt 5x5 po zrobieniu jednego kroku w lewo)
5
4 2
0 2
???????????????011??
????????????????001?
4 1
4 0,4 2
Co odpowiada coś takiego, gdzie ?
jest mgła:
0 1 2 3 4
_________
0 |????E????|
1 |?????????|
2 |?????????|
3 | ?_?_????|
4 |__C_S|_?_|
wyjście: jeden z krotek z listy prawidłowych wyborów
Wynik każdego Solvera jest odwrotnością wyniku architekta.
Część IV: Król wzgórza
Architekci i solwery otrzymują osobne wyniki, więc potencjalnie może być dwóch zwycięzców.
Każda para architektów i solverów będzie miała wiele szans na przechytrzenie się. Wyniki będą uśredniane dla wszystkich testów i przeciwników. Wbrew konwencjom golfa kod wygrywa najwyższy średni wynik!
Zamierzam, aby to trwało, ale nie mogę zagwarantować ciągłego testowania na zawsze! Powiedzmy na razie, że zwycięzca zostanie ogłoszony za tydzień.
Część V: Składanie
- Utrzymuję władzę weta wobec wszystkich zgłoszeń - spryt jest zachęcany, ale nie wtedy, gdy psuje konkurencję lub mój komputer! (Jeśli nie potrafię powiedzieć, co robi twój kod, prawdopodobnie go zawetuję)
- Wymyśl nazwę swojej pary Architekt / Solver. Opublikuj swój kod wraz z instrukcjami, jak go uruchomić.
Już wkrótce: zaktualizowany zestaw testowy Python dla nowego formatu. Nastąpiły duże zmiany, aby umożliwić przesłanie dowolnego języka.
źródło
Odpowiedzi:
BuildFun i SolveFun
Cóż, zajęło to sporo czasu i nie jestem do końca pewien, czy solver oszukuje, czy nie. Choć ma dostęp do całego labiryntu przez cały czas, patrzy tylko na komórkę, w której się znajduje, otaczające go ściany i, jeśli nie ma między nimi ściany, komórki przylegające do niej. Jeśli jest to niezgodne z zasadami, daj mi znać, a postaram się to zmienić.
W każdym razie oto kod:
Zdaję sobie sprawę, że jest to absurdalnie długi i nie jest szczególnie łatwy do odczytania, ale jestem leniwy, więc tak właśnie jest.
BuildFun
Architekt BuildFun jest dość prostym programem do generowania labiryntu, który zawsze tworzy „idealny” labirynt (jeden bez pętli i gdzie dwa punkty zawsze będą miały dokładnie jedną ścieżkę między nimi). Opiera swoją logikę na danych wejściowych nasion, co oznacza, że generowane labirynty są pseudolosowe z czymś, co często wydaje się powtarzającymi się wzorami, a przy tym samym ziarnie i rozmiarze powstanie ten sam labirynt.
Po wygenerowaniu labiryntu program podejmie próbę maksymalizacji wyniku labiryntu, szukając punktu początkowego i końcowego, które prowadzą do najdłuższej ścieżki między nimi. Aby to zrobić, biegnie przez każdy punkt początkowy, rozkłada znaczniki, aby znaleźć punkt końcowy najdalej od niego, i wybiera kombinację z najdłuższą ścieżką.
Następnie rysuje labirynt, liczy ściany i wysyła informacje o labiryncie. Jest to punkt początkowy, punkt końcowy, odległość między nimi, liczba ścian i wynik. Formatuje również te informacje w stylu opisanym powyżej dla rozmiaru, początku i końca, ścian poziomych i ścian pionowych i zapisuje je w pliku tekstowym o nazwie Maze.txt do późniejszego wykorzystania.
SolveFun
Solver, SolveFun, używa pliku tekstowego Maze.txt jako danych wejściowych i działa w bardzo podobny sposób jak architekt. Przy każdym ruchu wybierze kierunek, w którym chce podążać, w oparciu o swoje względne położenie do końca, a następnie spojrzy na otaczające go ściany. Jeśli nie ma tam ściany, sprawdzi, czy znajdowała się w sąsiedniej komórce, a jeśli nie, zostanie dodana jako możliwa opcja. Następnie przesunie się w kierunku najbliższym preferowanemu, pod warunkiem że ma opcje. Jeśli nie ma opcji, będzie się cofać, dopóki nie będzie. Trwa to aż do końca.
Podczas ruchu rejestruje ścieżkę, którą obiera w ścieżce zmiennej, która jest używana na końcu do wyprowadzenia całkowitej liczby kroków. Rejestruje także liczbę powtórzeń wykorzystanych do obliczenia zmarnowanych kroków na końcu. Kiedy osiągnie koniec, wypuści labirynt z najkrótszą ścieżką od początku do końca oznaczoną
*
s.Jak biegać
Ze względu na metodę wypisywania labiryntu (która obejmuje podkreślenie niektórych znaków), należy go uruchomić z wiersza poleceń w formie
python -c 'import filename;filename.BuildFun(Size, Seed)'
i
python -c 'import filename;filename.SolveFun()'
gdzie Size jest liczbą całkowitą od 15 do 50 (włącznie), a Seed jest liczbą całkowitą od 4 do Size (włącznie).
źródło