2D Maze Minus 1D

27

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.

Pokaż fragment kodu

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:

  1. Twój wynik powinien być pojedynczą linią przedstawiającą labirynt 1D.
  2. 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.
  3. Pierwsza postać, a następnie każda inna postać są punktami sieci.
  4. Wszystkie ściany powinny znajdować się na punktach kratowych; i wszystkie punkty wypaczenia między nimi.
  5. Wykres labiryntu 1D powinien odpowiadać wykresowi labiryntu 2D.
  6. Twoje labirynty 1D muszą być zwarte; wszystkie punkty niesieciowe muszą być ślepymi zaułkami (tj. przylegającymi do ścian) lub punktami wypaczenia.
  7. 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  |

Więcej przykładów można znaleźć tutaj .

code-golf graph-theory maze H Walters
źródło
1
Nie sądzę, aby wyjaśnienie labiryntów 1D było bardzo jasne ... Może dodanie pomniejszego / prostszego przykładu pomogłoby.
mbomb007
To fajnie. Tak, to pomaga.
mbomb007
Mimo że Twój interaktywny skrypt pomógł, wciąż jest to trudny problem. Więc po prostu to pomijam. Moje rozumienie tego jest nadal w najlepszym razie niepewne.
mbomb007
Opis labiryntu 1D jest szkicowy. Musiałem przeczytać rysunek 7, aby zrozumieć, że znaki pionowego paska w labiryncie 1D to ściany, których nie można pominąć.
edc65
1
przykład 1 z labiryntem 1d ułożonym w labiryncie 2d, gdzie każda para liter jest drabiną: gist.github.com/sparr/36d6355cc4c785a27b12157666169082
Sparr

Odpowiedzi:

3

Python 2 z igraph , 492 369 bajtów

import igraph,string
def f(s):
 C=s.find('\n')/2;N=' ';g=igraph.Graph(0,[(i,i+j)for i in range(len(s)/(4*C+4)*C)for j in(1,C)if s[(i/C*2+1)*(2*C+2)+i%C*2+2*j+j/C*3]==N]);V=g.vs;g.d=g.degree;O='';V(_d=1)[N]=N;V(_d_gt=2)[N]=list(string.ascii_letters)
 while g.es:
    v=V(_d=1)[0];O+='|'+v[N]
    while g.d(v):w=v.neighbors()[0];g-=(v,w);v=w;O+=N+v[N]if v[N]else''
 print O+'|'

(Każda piąta i szósta linia zaczyna się tabulatorem, a nie czterema spacjami, jak pokazuje StackExchange.)

  • Zaoszczędzono sześć bajtów, przestawiając trochę arytmetyki
  • Zapisano siedem bajtów przy użyciu plasterka zamiast zip
  • Zapisano trzy bajty, używając g+=tuple(v.neighbors())zamiastg.add_edge(*v.neighbors())
  • Zapisano siedem bajtów za pomocą g-=g.es[g.incident(v)]zamiastg.delete_edges(g.incident(v))
  • Zaoszczędzono jedenaście bajtów aliasingu g.d=g.degree
  • Zaoszczędzono 52 bajty (!), Eliminując pętlę, która zwarła wszystkie korytarze, zastępując wierzchołki stopnia 2 krawędzią między sąsiadami. Zamiast tego pętla wyjściowa po prostu ignoruje te wierzchołki.
  • Zapisano 13 bajtów, zauważając, że podczas przypisywania nazw, igraph nie dba o to, czy podana iterowalność jest za długa
  • Zaoszczędzono cztery bajty, nie mając zmiennej Rliczby wierszy, przenosząc jej obliczenia do jedynego punktu użycia
  • Zapisano dwa bajty, zmieniając wcięcie drugiego poziomu na tabulatory zamiast spacji
  • Zaoszczędzono sześć bajtów, przestawiając 2*(i%C)na i%C*2, 2*(i/C)do i/C*2i (C-1)*jnaj*C-j
  • Zapisano cztery bajty nazewnictwa N='n'
  • Zapisano jeden bajt określający, czy znak używa spacji <'-'zamiast ==' ', przy założeniu, że pojawiają się tylko prawidłowe znaki.
  • Potem zdałem sobie sprawę, że mogę nazwać atrybut wierzchołka ' 'zamiast 'n'i ponownie użyć Ndwóch literalnych spacji w źródle, i ==Nzamiast <'-'oszczędzić pięć dodatkowych bajtów

Następuje nieco nie golfowa wersja. Podstawową ideą jest, aby najpierw utworzyć wykres na wszystkich wierzchołkach labiryntu (plamy z nieparzystym rzędem i kolumną, gdy indeksowane są zerem.) Istnieje krawędź od jednego wierzchołka do następnego w tym samym rzędzie, jeśli następujący znak jest spacją i nie |. Od wierzchołka do tego tuż pod nim znajduje się krawędź, jeśli odpowiedni znak w następnym rzędzie to spacja, a nie spacja -.

Po zbudowaniu tego wykresu wybieramy dowolny liść i podążamy wzdłuż sąsiednich wierzchołków, zapisując ich nazwy, jeśli nie są korytarzem, i usuwamy używane krawędzie, aż utkniemy. Następnie bierzemy kolejny liść i kontynuujemy, aż znikną wszystkie krawędzie.

import string
import igraph
def f(s):
  C = s.find('\n')/2 # number of maze vertices in each row
  R = len(s)/(4*C+4) # number of rows
  def strpos(r, c):
    """Index of the vertex at row r, col c in the newline-delimited string s"""
    return (2*r+1)*(2*C+2) + 2*c + 1
  def vertpos(i):
    """Index of the i-th vertex in s"""
    return strpos(i/C, i%C)
  g = igraph.Graph(edges=[(i, i+(C if j else 1))
                          for i in range(R*C)
                          for j in (0, 1)
                          if s[vertpos(i)+(2*C+2 if j else 1)] == ' '])
  V = g.vs # the graph's vertex sequence
  O = ''
  V(_degree=1)['n'] = ' ' # All leaves are named space
  W = V(_degree_gt=2) # All warp points...
  W['n'] = list(string.ascii_letters[:len(W)]) # ...are named successive letters
  while g.es: # while any edges remain...
    v = V(_degree=1)[0] # find a leaf
    O += '|'+v['n'] # start a new 'block'
    while v.degree():
      w = v.neighbors()[0] # pick a neighbor
      g -= (v, w) # delete that edge
      v = w
      if v['n']: # If it's a dead end or warp point...
        O += ' '+v['n'] # ...write out the new neighbor
  print O+'|'

Możesz zobaczyć wyniki dla pięciu przykładowych labiryntów . (Niestety igraphnie jest dostępny w Try It Online; wyniki te zostały wyeksportowane z SageMathCloud .)

Nick Matteo
źródło
4

Haskell - 481 405 387 bajtów

import Data.List
s&t=elemIndices s t
l=last
c!(x:y:z)=l$(y:c)!(x:z):do{[x:p,q]<-mapM([id,reverse]<*>)[[x],[y]];x&[l q];[[]!((q++p):c++z)]}
c![x]=x:[]!c
c!z=z
main=interact(\m->let{g=' '&m;
u=(\\[k|k<-g,length(v>>=(k&))==2])<$>[]!v;
v=[[x,y]|x<-g,y<-g,elem(y-x-1)[0,head$'\n'&m]];
}in '|':(u>>=(++"|").init.(>>=(:" ").toEnum.((+)<*>(+65).(*32).(`div`26)).l.(-1:).(&(nub$u>>=init.tail)))))

Spowoduje to utworzenie listy spacji, które znajdują się w labiryncie, ponumerowanych według indeksu w ciągu i używa jej do znalezienia wszystkich par sąsiadujących spacji. Następnie łączy pary w dłuższe sekwencje punktów na podstawie dopasowania pierwszych / ostatnich elementów i usuwa korytarze, dzięki czemu każda sekwencja to jedno pomieszczenie w labiryncie 1D. Sekwencje są następnie tłumaczone na ciąg znaków, zamieniając punkty we wnętrzu co najmniej jednego pokoju (punkty wypaczenia) na odpowiednie litery, a resztę na spacje.

Labirynt 2D jest odczytywany ze STDIN, a labirynt 1D jest drukowany do STDOUT.

Edycja: Zmniejszona o 62 bajty, przestawiając kilka rzeczy i nieco modyfikując algorytm, oraz kolejne 14, zastępując zgodnie chrz toEnumsugestią Laikoni.

Edycja 2: Zaoszczędź 13 bajtów więcej, upraszczając logikę (!), 3 używając cukru dopasowującego wzór listy, a 2 używając >>=konkatowania u.

faubi
źródło
Myślę, że nie potrzebujesz nowych linii i spacji przed osłonami wzorów, np. Też o(x:p)q|x==last q=[q++p]|1>0=[]powinien działać.
Laikoni
toEnumPowinien również działać zamiast chr, a następnie import Data.Charmoże zostać upuszczony.
Laikoni
Wreszcie, gdy wyzwanie wymaga programu lub funkcji, możesz je zastąpić main=interact(\m->...)just f m=.... To powinno wystarczyć, aby pobić odpowiedź pytona, jeśli to coś dla ciebie znaczy.
Laikoni