Wyzwanie polega na przekształceniu labiryntów 2D w labirynty 1D.
Przegląd
+-+-+-+-+-+-+ +-+-+-+-+-+-+ graph {
| | | | |A| | B| A B A -- D
+ + + + +-+-+ + + + + +-+-+ \ | C -- D
| | | | | | | | \ | D -- E
+-+-+ +-+-+ + +-+-+ +-+-+ + \ | E -- F
| | |C D E F| C---D-E---F E -- G
+-+-+-+ +-+ + +-+-+-+ +-+ + | | B -- F
| | | | G | | .---G | F -- J
+ +-+-+-+ + + + +-+-+-+ + + .' / | G -- H
| | | | |H|I |J| H I-' J G -- I
+-+-+-+-+-+-+ +-+-+-+-+-+-+ (ascii) } // (graphviz dot)
Figure 1 Figure 2 Figure 3
Na potrzeby tego wyzwania tradycyjny labirynt 2D jest prostokątnym labiryntem utworzonym z punktów kratowych, w których znajdują się wszystkie następujące elementy:
- Jest zamknięty (zewnętrzna krawędź jest połączona ścianami).
- Wszystkie punkty sieci są połączone ze ścianami
- Jest połączony (dla każdych dwóch spacji X i Y jest ścieżka między nimi)
- Jest acykliczny (nie ma ścieżek z żadnego spacji X z powrotem do X bez cofania)
Ryc. 1 pokazuje tradycyjny labirynt 2D. Te labirynty mają trzy obszary zainteresowań:
- Ślepe zaułki - miejsca, z których jest tylko jedna dostępna ścieżka
- Korytarze - miejsca, z których są dwie dostępne ścieżki
- Punkty decyzyjne - miejsca, z których dostępne są trzy lub cztery dostępne ścieżki
Dla każdego takiego labiryntu można utworzyć wykres, w którym ślepe zaułki i punkty decyzyjne są węzłami, a krawędź między każdym dwoma węzłami połączonymi ścieżką wzdłuż korytarza. Ryc. 2 pokazuje ten sam labirynt z oznaczonymi takimi węzłami, a ryc. 3 wykres labiryntu (w notacji kropkowej ASCII i Graphviz).
Labirynty 1D
Labirynty 1D zawierają punkty osnowy, które występują w parach i są identyfikowane za pomocą litery (w obu przypadkach). Rycina 4 pokazuje przykładowy labirynt 1D. W przeciwnym razie jest to identyczne z labiryntem 2D o wysokości 1, jak pokazano na ryc. 5. Zwróć uwagę w szczególności na ryc. 5 pozycje punktów kratowych oznaczone przez +, które zmieniają się od lewej do prawej; w labiryncie 1D każda inna postać zaczynająca się od lewej ściany jest również punktem kratowym.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| D| D E|G E F| F | G | | D| D E|G E F| F | G |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4 Figure 5
Zasady poruszania się po tym labiryncie są następujące. Każdy ruch może być reprezentowany jako do przodu ( >) lub do tyłu ( <). Tutaj do przodu i do tyłu domyślnie mają takie samo znaczenie, jak nasza intuicyjna świadomość przestrzenna; do przodu przechodzi do pozycji bezpośrednio w prawo, a do tyłu natychmiast w lewo.
Punkty wypaczenia reprezentują lokalizacje, które asymetrycznie zamieniają połączenia z sąsiadami. Jeśli zbliżasz się do sąsiada do punktu wypaczenia, pozycja dwóch punktów wypaczenia jest zamieniana; jeśli przechodzisz z punktu osnowy do sąsiada, nie są one zamieniane. Na przykład na rysunku 6 przejście od 1 do tyłu prowadzi do 2 (ponieważ 1 jest sąsiadem G, a my przechodzimy od sąsiada, punkty 2 i @ są zamieniane). Przejście od 2 (punkt wypaczenia G) prowadzi do 3 (tutaj zaczynamy od punktu wypaczenia, więc nie ma zamiany). Podobnie przejście wstecz od 3 prowadzi do @.
54 2367 89^ @1
| D| D E|G E F| F | G |
Y X
Figure 6
Rysunek 6 pokazuje również przykładową nawigację od X do Y, wykorzystującą sekwencję ruchów <<>><>>>>>. Te ruchy prowadzą do punktów oznaczonych 123456789^odpowiednio w tej kolejności. Skorzystaj z fragmentu kodu w następnej sekcji.
Konwersja 2D na 1D
Biorąc pod uwagę labirynt 1D, można utworzyć wykres, na którym każdy węzeł jest albo ślepą uliczką, albo parą punktu wypaczenia, a krawędzie istnieją między dowolnymi dwoma węzłami połączonymi korytarzem. Ten wykres pozwala nam porównać labirynty 1D i 2D.
Na przykład labirynt 1D na rycinie 4 jest tym samym labiryntem na rycinie 1. Aby zobaczyć dlaczego, ryc. 7 dodaje etykiety do ślepych zaułków. Używając tych etykiet do zbudowania wykresu, wykres z Rysunku 7 jest po prostu znowu Rysunkiem 3. Rycina 8 pokazuje schemat budowy tego wykresu.
| D| D E|G E F| F | G |
A C B J H I
Figure 7
| D| D E|G E F| F | G |
+ + + + + + + + + + + + + + + <- lattice points
|A |C | |B J|H I| <- dead ends
|A D|C D E|G E F|B F J|H G I| <- all nodes (dead ends+warp points); i.e.:
"where each end is either a dead end
or a warp point pair"; note that each
pair of warp points is the same node.
|A-D|C-D-E|G-E-F|B-F-J|H-G-I| <- corridors; note each is a connection, since
1 2 3 4 5 6 7 8 9 "edges exist between any two nodes
connected along a corridor"
graph { graph {
A -- D // 1 <----> A -- D
C -- D // 2 <----> C -- D
D -- E // 3 <----> D -- E
G -- E // 4 <----> E -- G
E -- F // 5 <----> E -- F
B -- F // 6 <----> B -- F
F -- J // 7 <----> F -- J
H -- G // 8 <----> G -- H
G -- I // 9 <----> G -- I
} ^ }
Built from | From Figure 3
1D maze `-> isomorphic mappings
Figure 8
(Należy zauważyć, że etykiety i układ każdego wykresu zostały sztucznie wybrane, aby wyrównać w celach ilustracyjnych; ogólnie mówiąc, jest to problem izomorfizmu wykresu ).
Poniższy fragment kodu pomaga zwizualizować mechanikę labiryntu 1D i połączenia między labiryntem 1D, wykresem równoważności i labiryntem 2D.
Podczas poruszania się po labiryncie 1D w tym fragmencie podświetlane są dwa ostatnie dotknięte węzły. Te same węzły są podświetlane w ten sam sposób na wykresie równoważności i labiryncie 2D.
Zasadniczo dla każdego tradycyjnego labiryntu 2D można utworzyć równoważny labirynt 1D tego typu. Nieco bardziej skomplikowanym przykładem jest rysunek 9:
+-+-+-+-+-+-+ +-+-+-+-+-+-+ graph {
| | | | | |A| | |B| A B A -- D
+ + + + + + + + + + + + + + \ / C -- D
| | | | | | | | | | \ / D -- E
+-+-+ + +-+-+ +-+-+ + +-+-+ \ / B -- E
| | |C D E | C---D-E E -- F
+-+-+-+ +-+ + +-+-+-+ +-+ + |\ E -- I
| | | | F | | .---F \ F -- G
+ +-+-+-+ + + + +-+-+-+ + + .' / \ G -- H
| | | | |G|H |I| G H-' I H -- I
+-+-+-+-+-+-+ +-+-+-+-+-+-+ (ascii) } // (graphviz dot)
Figure 9 Figure 10 Figure 11
| D| D E |F E | F | | D| D E |F E | F |
A C I B G H
Figure 12 Figure 13
Ten labirynt ma węzeł z czterema ścieżkami (E na ryc. 10). Rysunek 11 pokazuje wykres. Rycina 12 jest równoważnym labiryntem 1D; a ryc. 13 pokazuje ten sam labirynt z etykietami dla ślepych zaułków, aby porównać z ryc. 11.
Wyzwanie
Biorąc pod uwagę labirynt 2D jako dane wejściowe, napisz funkcję lub program, który przekształca labirynt 2D w labirynt 1D z punktami wypaczenia. Punkty wypaczenia mogą w każdym przypadku używać dowolnej z 52 liter.
Gwarancje wejściowe (jeśli któryś z nich nie jest spełniony, nie musisz sobie z tym radzić):
- Labirynt wejściowy jest połączony (tzn. Zawsze możesz przejść z dowolnego miejsca do innego).
- Labirynt wejściowy jest zamknięty.
- Labirynt wejściowy jest prostokątny.
- Wykorzystywane są wszystkie punkty sieci
+. - Wykorzystywane są wszystkie ściany między punktami kratowymi w tym samym rzędzie
| - Wykorzystywane są wszystkie ściany między punktami kratowymi w tej samej kolumnie
-. - Wszystkie przestrzenie są częścią ścieżki (i wszystkie wewnątrz labiryntu).
- Ścieżki to wszystkie przestrzenie (zawsze będzie to tradycyjny, nie wypaczający się)
- Ścieżki mają dokładnie jedną przestrzeń.
- Labirynt budowany jest przez łączenie punktów na kratce.
- Na wykresie labiryntu nie ma więcej niż 52 ogółem węzłów (tj. Ślepe zaułki plus punkty decyzyjne).
Format wyjściowy:
- Twój wynik powinien być pojedynczą linią przedstawiającą labirynt 1D.
- Twój wynik nie powinien mieć wiodących / końcowych białych znaków; z wyjątkiem tego, że końcowy znak nowej linii jest w porządku.
- Pierwsza postać, a następnie każda inna postać są punktami sieci.
- Wszystkie ściany powinny znajdować się na punktach kratowych; i wszystkie punkty wypaczenia między nimi.
- Wykres labiryntu 1D powinien odpowiadać wykresowi labiryntu 2D.
- Twoje labirynty 1D muszą być zwarte; wszystkie punkty niesieciowe muszą być ślepymi zaułkami (tj. przylegającymi do ścian) lub punktami wypaczenia.
- Te tylko litery twojej wyjścia powinien być punkty osnowy. Każdy punkt wypaczenia występuje na linii dokładnie dwa razy.
Przykład:
| D| D E|G E F| F | G | <- (1,2) The single line output
+ + + + + + + + + + + + + + + <- lattice point spacing... (3)
(4,6) lattice points are all walls or spaces
(5) See Figure 8
(7) D, E, F, G appear twice; no other labels
To jest golf golfowy. Zwycięzcą jest poprawne przesłanie bez luki z najmniejszą liczbą bajtów.
Testowanie
Nie ma przypadków testowych dla tego wyzwania, ponieważ istnieje duża liczba poprawnych wyników dla każdego nietrywialnego labiryntu.
Zbudowałem jednak moduł sprawdzający w C ++ (ten moduł przedstawia oba rozwiązania za pomocą kanonizacji grafów ).
Ponadto podajemy kilka przykładów ilustrujących prawidłowe formatowanie:
Przykład 1
+-+-+-+-+-+-+
| | | |
+ + + + +-+-+
| | | |
+-+-+ +-+-+ +
| |
+-+-+-+ +-+ +
| | |
+ +-+-+-+ + +
| | | |
+-+-+-+-+-+-+
->
| D| D E|G E F| F | G |
Przykład 2
+-+-+-+-+-+-+
| | | | |
+ + + + + + +
| | | | |
+-+-+ + +-+-+
| |
+-+-+-+ +-+ +
| | |
+ +-+-+-+ + +
| | | |
+-+-+-+-+-+-+
->
| D| D E |F E | F |