2D Лабиринт Минус 1D

27

Эта задача о преобразовании 2D лабиринтов в 1D лабиринты.

обзор

+-+-+-+-+-+-+   +-+-+-+-+-+-+                    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

Для целей этой задачи традиционный 2D-лабиринт представляет собой прямоугольный лабиринт, образованный из точек решетки, где выполняется все следующее:

  • Он закрыт (внешний обод соединен стенами).
  • Все точки решетки связаны со стенами
  • Это связано (для каждых двух пространств X и Y есть путь между ними)
  • Это ациклично (нет пути из любого пространства X обратно в X без возврата)

На рисунке 1 показан традиционный 2D лабиринт. У этих лабиринтов есть три области интереса:

  • Тупики - места, из которых есть только один доступный путь
  • Коридоры - места, из которых есть два доступных пути
  • Точки принятия решения - места, из которых есть три или четыре доступных пути

Для каждого такого лабиринта можно создать график, в котором тупики и точки принятия решений являются узлами, а между каждыми двумя узлами есть граница, соединенная путем вдоль коридора. На рисунке 2 показан тот же лабиринт с помеченными такими узлами, а на рисунке 3 - график лабиринта (в точечной записи ASCII и Graphviz).

1D лабиринты

1D лабиринты содержат точки перекоса, которые идут парами и идентифицируются с помощью буквы (в любом случае). На рисунке 4 показан пример 1D лабиринта. В остальном он идентичен двухмерному лабиринту с высотой 1, как показано на рисунке 5. Обратите внимание, в частности, на рисунке 5 позиции точки решетки, отмеченные +, которые чередуются слева направо; в одномерном лабиринте любой другой символ, начинающийся с крайней левой стены, также является точкой решетки.

                                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  D|  D E|G E F|  F  |  G  |    |  D|  D E|G E F|  F  |  G  |
                                 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            Figure 4                         Figure 5

Правила навигации по этому лабиринту следующие. Каждое движение может быть представлено как вперед ( >) или назад ( <). Вперед и назад здесь по умолчанию имеют то же значение, что и наше интуитивное пространственное понимание; вперед переходит в положение сразу вправо, а назад сразу влево.

Точки деформации представляют местоположения, которые асимметрично меняют местность с соседями. Если вы идете от соседа к точке деформации, положение двух точек деформации меняется местами; если вы переходите от точки деформации к соседу, они не меняются местами. Например, на рисунке 6 перемещение назад от 1 приводит вас к 2 (поскольку 1 является соседом G, а мы переходим от соседа, точки 2 и @ меняются местами). Движение вперед от 2 (точка деформации G) приводит вас к 3 (здесь мы начинаем с точки деформации, поэтому нет свопа). Аналогично, переход назад от 3 приведет вас к @.

        54 2367    89^   @1
|  D|  D E|G E F|  F  |  G  |
                     Y     X
          Figure 6

На рисунке 6 также показан пример навигации от X до Y с использованием последовательности ходов <<>><>>>>>. Эти шаги приводят вас к точкам, помеченным 123456789^соответственно, в указанном порядке. Не стесняйтесь исследовать его самостоятельно, используя фрагмент кода в следующем разделе.

Преобразование 2D в 1D

Используя одномерный лабиринт, можно создать график, где каждый узел является либо тупиком, либо парой точек деформации, и существуют ребра между любыми двумя узлами, соединенными вдоль коридора. Этот график позволяет сравнивать 1D и 2D лабиринты.

Например, 1D лабиринт на рисунке 4 - это тот же лабиринт на рисунке 1. Чтобы понять почему, рисунок 7 добавляет метки в тупики. Используя эти метки для построения графика, график на рисунке 7 снова просто рисунок 3. На рисунке 8 показан прорыв построения этого графика.

|  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

(Обратите внимание, что метки и расположение каждого графа были искусственно выбраны для выравнивания в целях иллюстрации; в общем, это проблема изоморфизма графа ).

Следующий фрагмент предоставлен, чтобы помочь визуализировать механику 1D-лабиринта и связь между 1D-лабиринтом, графиком эквивалентности и 2D-лабиринтом.

Показать фрагмент кода

При перемещении по 1D-лабиринту в этом фрагменте последние два узла, к которым вы прикоснулись, подсвечиваются. Одинаковые узлы подсвечиваются одинаково на графике эквивалентности и в двумерном лабиринте.

В общем, для любого традиционного двухмерного лабиринта может быть создан эквивалентный одномерный лабиринт этого типа. Несколько более сложный пример - рисунок 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

Этот лабиринт имеет узел с четырьмя путями (E на рисунке 10). Рисунок 11 показывает его график. Фиг.12 - эквивалентный 1D лабиринт; и на рисунке 13 показан тот же лабиринт с метками для тупиков, чтобы сравнить с рисунком 11.

Вызов

Используя 2D Лабиринт в качестве входных данных, напишите функцию или программу, которая преобразует 2D лабиринт в 1D лабиринт с точками деформации. Очки деформации могут использовать любую из 52 букв в каждом случае.

Гарантии ввода (если что-либо из этого не выполнено во вводе, вам не нужно иметь с этим дело):

  • Входной лабиринт подключен (то есть вы всегда можете перейти из любой точки в любую другую).
  • Входной лабиринт закрыт.
  • Входной лабиринт прямоугольный.
  • Все точки решетки используют +.
  • Все стены между точками решетки в одном ряду используют |
  • Все стены между точками решетки в одном и том же столбце используют -.
  • Все пространства являются частью пути (и все внутри лабиринта).
  • Пути - это все пробелы (это всегда будет традиционным, не деформированным)
  • Дорожки шириной ровно в одно пространство.
  • Лабиринт построен путем соединения точек на решетке.
  • В графе лабиринта не более 52 узлов (т. Е. Тупиков и точек принятия решений).

Выходной формат:

  1. Ваш вывод должен быть одной строкой, показывающей 1D лабиринт.
  2. Ваш вывод не должен иметь пробелов в начале / конце; за исключением того, что завершающий перевод новой строки в порядке.
  3. Первый символ и каждый последующий символ являются точками решетки.
  4. Все стены должны быть на точках решетки; и все точки перекоса между ними.
  5. График вашего 1D лабиринта должен быть эквивалентен графику 2D лабиринта.
  6. Ваши 1D лабиринты должны быть компактными; все точки без решетки должны быть тупиками (т.е. смежными со стенами) или точками деформации.
  7. В только буквы в вашем выводе должны быть точки основы. Каждая точка деформации происходит на линии ровно дважды.

Пример:

|  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

Это код-гольф. Победителем считается правильное представление без лазеек с наименьшим количеством байтов.

тестирование

Для этой задачи нет тестовых случаев, поскольку для любого нетривиального лабиринта имеется большое количество правильных выходных данных.

Однако я построил средство проверки в C ++ (оно проверяет оба решения посредством канонизации графа ).

Кроме того, вот несколько примеров, которые помогут проиллюстрировать правильное форматирование:

Пример 1

+-+-+-+-+-+-+
| |   |     |
+ + + + +-+-+
|   | |     |
+-+-+ +-+-+ +
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
->
|  D|  D E|G E F|  F  |  G  |

Пример 2

+-+-+-+-+-+-+
| |   |   | |
+ + + + + + +
|   | | |   |
+-+-+ + +-+-+
|           |
+-+-+-+ +-+ +
|         | |
+ +-+-+-+ + +
| |       | |
+-+-+-+-+-+-+
->
|  D|  D E  |F E  |  F  |

Больше примеров можно найти здесь .

code-golf graph-theory maze H Уолтерс
источник
1
Я не думаю, что объяснение 1D лабиринтов очень ясно ... Может быть, добавление меньшего / более простого примера поможет.
mbomb007
Это круто. Да, это помогает.
mbomb007
Даже если ваш интерактивный скрипт помог, это все еще сложная проблема. Так что я просто пропустил это. Мое понимание этого все еще остается слабым в лучшем случае.
mbomb007
Описание 1D лабиринта схематично. Мне пришлось читать до рисунка 7, чтобы понять, что символы вертикальной черты в одномерном лабиринте - это стены, через которые вы не можете пройти.
edc65
1
Пример 1 с 1d лабиринта сложен в 2d лабиринта , где каждая пара букв является лестницей: gist.github.com/sparr/36d6355cc4c785a27b12157666169082
Sparr

Ответы:

3

Python 2 с играфой , 492 369 байт

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+'|'

(Пятая и шестая строки начинаются с табуляции, а не с четырех пробелов, как показывает StackExchange.)

  • Сохранено шесть байтов, переставляющих некоторую арифметику
  • Сохранено семь байт с использованием фрагмента вместо zip
  • Сохранено три байта с использованием g+=tuple(v.neighbors())вместоg.add_edge(*v.neighbors())
  • Сохранено семь байтов g-=g.es[g.incident(v)]вместоg.delete_edges(g.incident(v))
  • Сохранено одиннадцать байтов псевдонимов g.d=g.degree
  • Сохранено 52 байта (!), Исключая петлю, которая сокращала все коридоры, заменяя вершины степени 2 ребром между соседями. Вместо этого выходной цикл просто игнорирует эти вершины.
  • Сохранено 13 байт, которые отмечают, что при присваивании имен igraph не заботится, слишком ли длинна предоставленная итерация
  • Сохранение четырех байтов за счет отсутствия переменной Rдля количества строк, перемещение ее вычисления в единственную точку использования
  • Сохранены два байта, изменяющие отступ второго уровня на табуляции вместо пробелов
  • Сохранено шесть байтов, переставляющих 2*(i%C)в i%C*2, 2*(i/C)в i/C*2и (C-1)*jвj*C-j
  • Сохранено четыре байта именования N='n'
  • Сохраняется один байт, определяющий, использует ли символ пробел, <'-'а не ==' 'в предположении, что отображаются только допустимые символы.
  • Затем понял, что я могу назвать атрибут вершины ' 'вместо 'n', и повторно использовать Nдля двух литеральных пространств в источнике, и ==Nвместо того <'-', чтобы сохранить еще пять байтов

Несколько неутешительная версия следует. Основная идея состоит в том, чтобы сначала построить график по всем вершинам лабиринта (пятна с нечетной строкой и столбцом при нулевом индексировании.) В одной и той же строке есть ребро от одной вершины до следующей, если следующий символ является пробелом и нет |. Существует вершина от вершины к той, которая находится прямо под ней, если соответствующий символ в следующей строке является пробелом, а не -.

После построения этого графика мы выбираем любой лист и следуем вдоль последовательно смежных вершин, записывая их имена, если они не являются коридором, и удаляя использованные ребра, пока мы не застряли. Затем мы берем еще один лист и продолжаем, пока все края не исчезнут.

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+'|'

Вы можете увидеть результаты для пяти примеров лабиринтов . (К сожалению, igraphнедоступно в Try It Online; эти результаты были экспортированы из SageMathCloud .)

Ник Маттео
источник
4

Haskell - 481 405 387 байт

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)))))

Это создает список пространств в лабиринте, пронумерованных индексом в строке, и использует его для поиска всех пар смежных пространств. Затем он объединяет пары в более длинные последовательности точек на основе сопоставления первого / последнего элементов и удаляет коридоры, так что каждая последовательность представляет собой одну комнату в одномерном лабиринте. Последовательности затем переводятся в строку, заменяя точки внутри, по крайней мере, одной комнаты (точки деформации) соответствующими буквами, а остальные - пробелами.

2D лабиринт считывается из STDIN, а 1D лабиринт печатается в STDOUT.

Edit: Снижение на 62 байт перестановкой кучу вещей и изменения алгоритма немного, и еще 14, заменив chrс toEnumкак это было предложено Laikoni.

Редактировать 2: Сохранено еще 13 байтов за счет упрощения логики (!), 3 с использованием сахарного сопоставления с шаблоном списка и 2 с помощью >>=объединения u.

faubi
источник
Я думаю, что вам не нужны новые строки и пробелы, прежде чем шаблонные охранники, например, o(x:p)q|x==last q=[q++p]|1>0=[]тоже должны работать.
Лайкони
И toEnumдолжен работать вместо того chr, чтобы потом import Data.Charможно было уронить.
Лайкони
И наконец, когда задача запрашивает программу или функцию, вы можете заменить ее main=interact(\m->...)просто f m=.... Этого должно быть достаточно, чтобы обойти ответ Python, если это что-то значит для вас.
Лайкони