Este desafio consiste em converter labirintos 2D em labirintos 1D.
visão global
+-+-+-+-+-+-+ +-+-+-+-+-+-+ 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
Para os propósitos deste desafio, um labirinto 2D tradicional é um labirinto retangular formado a partir de pontos de treliça, onde tudo o que se segue é válido:
- Está fechado (a borda externa é conectada por paredes).
- Todos os pontos de rede estão conectados às paredes
- Está conectado (para cada dois espaços X e Y existe um caminho entre eles)
- É acíclico (não há caminhos de nenhum espaço X de volta para X sem retroceder)
A Figura 1 mostra um labirinto 2D tradicional. Esses labirintos têm três áreas de interesse:
- Becos sem saída - locais a partir dos quais existe apenas um caminho disponível
- Corredores - locais a partir dos quais existem dois caminhos disponíveis
- Pontos de decisão - locais a partir dos quais existem três ou quatro caminhos disponíveis
Para cada labirinto, pode-se criar um gráfico onde os becos sem saída e os pontos de decisão são nós, e há uma aresta entre cada dois nós conectados por um caminho ao longo de um corredor. A Figura 2 mostra o mesmo labirinto com esses nós rotulados e a Figura 3 o gráfico do labirinto (na notação de ponto ASCII e Graphviz).
Labirintos 1D
Os labirintos 1D incorporam pontos de distorção, que vêm em pares, e são identificados usando uma letra (em ambos os casos). A Figura 4 mostra um exemplo de labirinto 1D. Caso contrário, é idêntico a um labirinto 2D com uma altura de 1, como mostrado na Figura 5. Observe em particular na Figura 5 as posições dos pontos de treliça marcados por +, que alternam da esquerda para a direita; no labirinto 1D, todos os outros caracteres que começam com a parede mais à esquerda também são um ponto de treliça.
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| D| D E|G E F| F | G | | D| D E|G E F| F | G |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4 Figure 5
As regras para navegar neste labirinto são as seguintes. Cada movimento pode ser representado como avançar ( >) ou voltar ( <). Avançar e retroceder aqui, por padrão, tem o mesmo significado que nossa percepção espacial intuitiva; frente vai para a posição imediatamente à direita e para trás imediatamente à esquerda.
Os pontos de distorção representam locais que trocam assimetricamente a conexão com os vizinhos. Se você está vindo de um vizinho para um ponto de distorção, a posição dos dois pontos de distorção é trocada; se você estiver vindo de um ponto de distorção para um vizinho, eles não serão trocados. Por exemplo, na Figura 6, retroceder de 1 leva você a 2 (como 1 é o vizinho de G e estamos saindo do vizinho, os pontos 2 e @ são trocados). Avançar de 2 (ponto de distorção G) leva você a 3 (aqui, estamos começando a partir de um ponto de distorção, portanto não há troca). Da mesma forma, retroceder de 3 leva você a @.
54 2367 89^ @1
| D| D E|G E F| F | G |
Y X
Figure 6
A Figura 6 também mostra um exemplo de navegação de X para Y, usando a sequência de movimentos <<>><>>>>>. Esses movimentos levam você aos pontos marcados 123456789^respectivamente, nessa ordem. Sinta-se livre para explorar você mesmo usando o snippet de código na próxima seção.
Convertendo 2D para 1D
Dado um labirinto 1D, é possível criar um gráfico em que cada nó é um beco sem saída ou um par de pontos de distorção, e existem arestas entre quaisquer dois nós conectados ao longo de um corredor. Este gráfico nos permite comparar labirintos 1D e 2D.
Por exemplo, o labirinto 1D na Figura 4 é o mesmo labirinto na Figura 1. Para ver por que, a Figura 7 adiciona etiquetas aos becos sem saída. Usando esses rótulos para criar um gráfico, o gráfico da Figura 7 é simplesmente a Figura 3 novamente. A Figura 8 mostra uma quebra de estrutura deste gráfico.
| 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
(Observe que os rótulos e o layout de cada gráfico foram escolhidos artificialmente para alinhar para fins ilustrativos; geralmente, esse é um problema de isomorfismo do gráfico ).
O trecho a seguir é fornecido para ajudar a visualizar a mecânica do labirinto 1D e a conexão entre o labirinto 1D, o gráfico de equivalência e o labirinto 2D.
À medida que você navega no labirinto 1D neste trecho, os dois últimos nós que você toca são realçados. Os mesmos nós são destacados da mesma maneira no gráfico de equivalência e no labirinto 2D.
Em geral, para qualquer labirinto 2D tradicional, um labirinto 1D equivalente deste tipo pode ser criado. Um exemplo um pouco mais complexo é a Figura 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
Este labirinto possui um nó com quatro caminhos (E na Figura 10). A Figura 11 mostra seu gráfico. A Figura 12 é um labirinto 1D equivalente; e a Figura 13 mostra o mesmo labirinto com rótulos para becos sem saída para comparar com a Figura 11.
Desafio
Dado um Labirinto 2D como entrada, escreva uma função ou programa que transforma o labirinto 2D em um labirinto 1D com pontos de distorção. Os pontos de distorção podem usar qualquer uma das 52 letras em cada caso.
Garantias de entrada (se alguma delas não for atendida na entrada, você não precisará lidar com isso):
- O labirinto de entrada está conectado (ou seja, você sempre pode ir de qualquer ponto para outro).
- O labirinto de entrada está fechado.
- O labirinto de entrada é retangular.
- Todos os pontos de rede são usados
+. - Todas as paredes entre os pontos de treliça na mesma linha usam
| - Todas as paredes entre os pontos da rede na mesma coluna são usadas
-. - Todos os espaços fazem parte de um caminho (e todos dentro do labirinto).
- Caminhos são todos os espaços (isso sempre será tradicional, sem distorções)
- Os caminhos têm exatamente um espaço amplo.
- O labirinto é construído conectando pontos em uma treliça.
- Não há mais de 52 nós no total (ou seja, becos sem saída mais pontos de decisão) no gráfico do labirinto.
Formato de saída:
- Sua saída deve ser uma única linha mostrando um labirinto 1D.
- Sua saída não deve ter espaços em branco à esquerda / à direita; exceto que uma nova linha à direita está correta.
- O primeiro caractere e todos os outros caracteres depois são pontos de treliça.
- Todas as paredes devem estar em pontos de treliça; e todos os pontos de distorção entre eles.
- O gráfico do seu labirinto 1D deve ser equivalente ao gráfico do labirinto 2D.
- Seus labirintos 1D devem ser compactos; todos os pontos que não são de treliça devem ter becos sem saída (isto é, adjacentes às paredes) ou pontos de distorção.
- As únicas letras em sua saída devem ser pontos de distorção. Cada ponto de distorção ocorre na linha exatamente duas vezes.
Exemplo:
| 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
Isso é código-golfe. O vencedor é o envio correto, sem brechas, com o mínimo de bytes.
Teste
Não há casos de teste para esse desafio, pois há um grande número de saídas corretas para qualquer labirinto não trivial.
No entanto, construí um verificador em C ++ (esse verificador representa graficamente as duas soluções por meio de uma canonização de gráfico ).
Além disso, aqui estão alguns exemplos para ajudar a ilustrar a formatação correta:
Exemplo 1
+-+-+-+-+-+-+
| | | |
+ + + + +-+-+
| | | |
+-+-+ +-+-+ +
| |
+-+-+-+ +-+ +
| | |
+ +-+-+-+ + +
| | | |
+-+-+-+-+-+-+
->
| D| D E|G E F| F | G |
Exemplo 2
+-+-+-+-+-+-+
| | | | |
+ + + + + + +
| | | | |
+-+-+ + +-+-+
| |
+-+-+-+ +-+ +
| | |
+ +-+-+-+ + +
| | | |
+-+-+-+-+-+-+
->
| D| D E |F E | F |
fonte
Respostas:
Python 2 com igraph ,
492369 bytes(A quinta e a sexta linhas, cada uma começa com uma guia, não quatro espaços, como mostra o StackExchange.)
g+=tuple(v.neighbors())vez deg.add_edge(*v.neighbors())g-=g.es[g.incident(v)]vez deg.delete_edges(g.incident(v))g.d=g.degreeRpara o número de linhas, movendo seu cálculo para o único ponto de uso2*(i%C)parai%C*2,2*(i/C)parai/C*2e(C-1)*jparaj*C-jN='n'<'-'e não==' ', supondo que apenas caracteres válidos apareçam.' 'vez de'n'e reutilizarNpara os dois espaços literais na fonte e, em==Nvez de<'-', salvar mais cinco bytesA seguir, uma versão não-destruída. A idéia básica é primeiro fazer um gráfico em todos os vértices do labirinto (os pontos com linha e coluna ímpares quando indexados a zero.) Há uma aresta de um vértice para o próximo na mesma linha se o caractere a seguir for um espaço e não
|. Existe uma aresta do vértice para a logo abaixo, se o caractere correspondente na linha a seguir for um espaço, e não-.Depois de construir este gráfico, escolhemos qualquer folha e seguimos vértices sucessivamente adjacentes, escrevendo seus nomes se eles não forem um corredor e excluindo bordas usadas, até ficarmos presos. Então pegamos outra folha e continuamos até que todas as bordas se foram.
Você pode ver os resultados para os cinco exemplos de labirintos . (Infelizmente,
igraphnão está disponível no Try It Online; esses resultados foram exportados do SageMathCloud .)fonte
Haskell -
481405387 bytesIsso cria uma lista de espaços que estão no labirinto, numerados por índice na cadeia de caracteres e o usa para encontrar todos os pares de espaços adjacentes. Em seguida, costura os pares em seqüências mais longas de pontos com base no primeiro / último elementos correspondentes e remove os corredores, de modo que cada sequência seja uma sala no labirinto 1D. As seqüências são traduzidas em uma seqüência de caracteres substituindo pontos no interior de pelo menos uma sala (os pontos de distorção) em letras correspondentes e o restante em espaços.
O labirinto 2D é lido em STDIN e o labirinto 1D é impresso em STDOUT.
Edit: Reduzido por 62 bytes, reorganizando um monte de coisas e modificando um pouco o algoritmo, e outros 14, substituindo
chr-otoEnumpor sugerido por Laikoni.Editar 2: salvou mais 13 bytes simplificando a lógica
(!), 3 usando o padrão de lista correspondente a sugar e 2 usando>>=para concatenaru.fonte
o(x:p)q|x==last q=[q++p]|1>0=[]deve funcionar também.toEnumdeve funcionar em vez dechr, entãoimport Data.Charpode ser descartado.main=interact(\m->...)por apenasf m=.... Isso deve ser suficiente para vencer a resposta do python, se isso significa alguma coisa para você.