Бесконечные лабиринты

35

Задний план

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

вход

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

Эта сетка является планом бесконечного лабиринта, который создается путем выравнивания бесконечного числа копий сетки рядом друг с другом. Лабиринт разделен на полости , которые связаны компонентами пустых пространств (диагонально смежные пространства не связаны). Например, сетка

##.####
...##..
#..#..#
####..#
##...##

приводит к следующему лабиринту (продолжается бесконечно во всех направлениях):

##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##
##.######.######.####
...##.....##.....##..
#..#..##..#..##..#..#
####..#####..#####..#
##...####...####...##

Этот конкретный лабиринт содержит полость бесконечной области. С другой стороны, этот проект приводит к лабиринту только с конечными полостями:

##.####
##..###
####...
..####.
#..####

Выход

Ваш вывод должен быть истинным значением, если лабиринт содержит бесконечную полость, и ложным значением, если нет. Обратите внимание, что лабиринт может содержать как конечные, так и бесконечные полости; в этом случае вывод должен быть правдивым.

правила

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

Дополнительные тестовые случаи

Бесконечные полости:

.#

#.#
...
#.#

#.###.#.###.#
#.#...#...#.#
#.#.#####.#.#
..#.#...#.#..
###.#.#.#.###
#...#.#.#...#
#.###.#.###.#

##.###
#..###
..##..
###..#
##..##

..#..#..#..#..#..#
.#..#..#..#..#..#.
#..#..#..#..#..#..

#.####.###.###.####
#...#..#...###..###
###.#..#.######..##
....####.#######...
###..###...########
##########.##....##
..###......##.##...
#.........##..#####
###########..###..#
#...........####..#
#.###########.##..#
#.##....##.....####
#.####.###.###.####

Конечные полости:

###
#.#
###

.#
#.

####
.#..
####

#.#.#
..#..
#####
..#..
#.#.#

#.#.#.#.#.#
..#...#.#..
###.###.###
..#.#......
#.#.#######
#.#.......#
#.#######.#
#.#.....#.#
#.#.#.#.#.#

##....#####
.#..#...##.
.##.#..#...
..###.###..
#..##.#####
#...##....#
#.#.#####.#
###..####.#
....####...
###...#####

###....##.#########
####...##....#...##
..####.#######.###.
....##..........##.
###..#####.#..##...
####..#..#....#..##
..###.####.#.#..##.
..###...#....#.#...
..####..##.###...##
#.####.##..#####.##
####...##.#####..##


###########
........#..
#########.#
..........#
.##########
.#.........
##.########
...#.......
code-golf grid graph-theory decision-problem maze Zgarb
источник
Есть ли завершающий символ новой строки?
FUZxxl
@FUZxxl Это зависит от вас.
Згарб
Может ли бесконечный лабиринт быть прямой линией, уходящей в бесконечность.
1
@ Нил, я не уверен, что ты имеешь в виду. Первый и второй бесконечные примеры имеют бесконечные строки, но есть по крайней мере один .и один #на входе.
Згарб
1
Хороший вызов, сложнее, чем кажется
edc65

Ответы:

2

JavaScript (ES6), 235 253

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

Изворотливый способ обработки по модулю в JS это очень раздражает.

L=g=>(
  g=g.split('\n').map(r=>[...r]),
  w=g[0].length,h=g.length,
  F=(x,y,t=((x%w)+w)%w,u=((y%h)+h)%h,v=g[u][t],k=0+[x,y])=>
    v<'.'?0:v>'.'?v!=k
    :[0,2,-3,5].some(n=>F(x+(n&3)-1,y+(n>>2)),g[u][t]=k),
  g.some((r,y)=>r.some((c,x)=>c=='.'&&F(x,y)))
)

Тест в консоли Firefox / FireBug

бесконечность

['##.###\n#..###\n..##..\n###..#\n##..##'
,'#.#\n...\n#.#'
,'#.###.#.###.#\n#.#...#...#.#\n#.#.#####.#.#\n..#.#...#.#..\n###.#.#.#.###\n#...#.#.#...#\n#.###.#.###.#'
,'##.###\n#..###\n..##..\n###..#\n##..##'
,'#.####.###.###.####\n#...#..#...###..###\n###.#..#.######..##\n....####.#######...\n###..###...########\n##########.##....##\n..###......##.##...\n#.........##..#####\n###########..###..#\n#...........####..#\n#.###########.##..#\n#.##....##.....####\n#.####.###.###.####'
].forEach(g=>console.log(g,L(g)))

Выход

"##.###
#..###
..##..
###..#
##..##" true

"#.#
...
#.#" true

"#.###.#.###.#
#.#...#...#.#
#.#.#####.#.#
..#.#...#.#..
###.#.#.#.###
#...#.#.#...#
#.###.#.###.#" true

"##.###
#..###
..##..
###..#
##..##" true

"#.####.###.###.####
#...#..#...###..###
###.#..#.######..##
....####.#######...
###..###...########
##########.##....##
..###......##.##...
#.........##..#####
###########..###..#
#...........####..#
#.###########.##..#
#.##....##.....####
#.####.###.###.####" true

конечный

['###\n#.#\n###', '.#\n#.', '####\n.#..\n####'
,'#.#.#\n..#..\n#####\n..#..\n#.#.#'
,'#.#.#.#.#.#\n..#...#.#..\n###.###.###\n..#.#......\n#.#.#######\n#.#.......#\n#.#######.#\n#.#.....#.#\n#.#.#.#.#.#'
,'##....#####\n.#..#...##.\n.##.#..#...\n..###.###..\n#..##.#####\n#...##....#\n#.#.#####.#\n###..####.#\n....####...\n###...#####'
,'###....##.#########\n####...##....#...##\n..####.#######.###.\n....##..........##.\n###..#####.#..##...\n####..#..#....#..##\n..###.####.#.#..##.\n..###...#....#.#...\n..####..##.###...##\n#.####.##..#####.##\n####...##.#####..##'
].forEach(g=>console.log(g,L(g)))

Выход

"###
#.#
###" false

".#
#." false

"####
.#..
####" false

"#.#.#
..#..
#####
..#..
#.#.#" false

"#.#.#.#.#.#
..#...#.#..
###.###.###
..#.#......
#.#.#######
#.#.......#
#.#######.#
#.#.....#.#
#.#.#.#.#.#" false

"##....#####
.#..#...##.
.##.#..#...
..###.###..
#..##.#####
#...##....#
#.#.#####.#
###..####.#
....####...
###...#####" false

"###....##.#########
####...##....#...##
..####.#######.###.
....##..........##.
###..#####.#..##...
####..#..#....#..##
..###.####.#.#..##.
..###...#....#.#...
..####..##.###...##
#.####.##..#####.##
####...##.#####..##" false
edc65
источник
Да, daft modulo также был проблемой в C #, но я думаю, что нашел способ эффективно использовать его в своей рабочей копии с кодом направления (я буду отправлять репост только в том случае, если смогу получить 10% уменьшение или лучше): (j%4-1)%2дает хороший повторяющийся узор.
VisualMelon
Я полагаю, что неназванные функции допустимы, и, таким образом, если функция не включает в себя вызов (как кажется, не), то допустимо не подсчитывать количество L=байтов.
SuperJedi224
@ SuperJedi224 вы, вероятно, правы, но он достаточно короткий, как и в конце концов
edc65
21

C # - 423 375 байт

Завершить программу на C #, принять ввод через STDIN, вывести «True» или «False» в STDOUT в зависимости от ситуации.

Я не мог оставить этого Линка там ... к счастью, его удаление окупилось! Теперь он отслеживает просмотренные и посещенные ячейки в массиве (учитывая, что он все равно просматривает только их конечное число). Я также переписал код направления, устраняя необходимость в лямбда-выражениях и вообще делая код более недоступным для понимания (но с существенной экономией байтов).

using C=System.Console;struct P{int x,y;static void Main(){int w=0,W,k=0,o,i,j;P t;string D="",L;for(;(L=C.ReadLine())!=null;D+=L)w=L.Length;for(i=W=D.Length;i-->0&k<W;){k=1;P[]F=new P[W];for(F[j=0].x=i%w+W*W,F[0].y=i/w+W*W;D[i]>35&j<k;)for(t=F[j++],o=1;o<5&k<W;t.y+=(o++&2)-1){t.x+=o&2;if(D[--t.x%w+t.y%(W/w)*w]>35&System.Array.IndexOf(F,t)<0)F[k++]=t;}}C.WriteLine(k>=W);}}

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

Код без полей:

using C=System.Console;

struct P
{
    int x,y;

    static void Main()
    {
        int w=0, // w is the width
        W, // W is the length of the whole thing
        k=0, // k is visited count
        o, // o is offset, or something (gives -1,0 0,-1 +1,0 0,+1 t offset pattern)
        i, // i is the start cell we are checking currently
        j; // j is the F index of the cell we are looking at

        P t; // t is the cell at offset from the cell we are looking at

        string D="", // D is the map
        L;

        for(;(L=C.ReadLine())!=null; // read a line, while we can
            D+=L) // add the line to the map
            w=L.Length; // record the width

        for(i=W=D.Length;i-->0&k<W;) // for each cell
        {
            k=1;

            P[]F=new P[W]; // F is the list of visited cells,

            for(F[j=0].x=i%w+W*W,F[0].y=i/w+W*W; // there are reasons (broken modulo)
                D[i]>35&j<k;) // for each cell we've visited, until we've run out
                for(t=F[j++], // get the current cell
                    o=1; // o is just a counter which we use to kick t about
                    o<5& // 4 counts
                    k<W; // make sure we havn't filled F
                    t.y+=(o++&2)-1) // kick and nudge y, inc o
                {
                    t.x+=o&2; // kick x
                    if(D[--t.x%w+t.y%(W/w)*w]>35 // nudge x, it's a dot
                       &System.Array.IndexOf(F,t)<0) // and we've not seen it before
                        F[k++]=t; // then add it
                }
        }

        C.WriteLine(k>=W); // result is whether we visited lots of cells
    }
}
VisualMelon
источник
1
Вероятно, в первый раз, когда я увидел C#ответ как лучший получатель голосов здесь.
Майкл МакГриф
1
Main () в структуре, теперь это мило.
PTwr
10

Python 2 - 258 210 244 байта

Рекурсивно проверять пути, если переполнение стека возвращает 1 (правда), в противном случае возвращает Нет (фальси).

import sys
def k(s):
 a=len(s);m=[[c=='.'for c in b]*999for b in s.split('\n')]*999;sys.setrecursionlimit(a)
 for x in range(a*a):
  try:p(m,x/a,x%a)
  except:return 1
def p(m,x,y):
 if m[x][y]:m[x][y]=0;map(p,[m]*4,[x,x,x+1,x-1],[y+1,y-1,y,y])
Кайл Гуллион
источник
1
Вы можете сохранить несколько байтов, используя ;для строк p, так как вы получите их на одной строке с if.
PurkkaKoodari
11
«Если переполнение стека возвращает true» - мне нравится это условие завершения рекурсии :)
schnaader
3
Я не уверен, что это правильный подход. Использование переполнения стека для обнаружения «бесконечной» области приведет к ложным срабатываниям. Спецификация проблемы не устанавливает никаких ограничений на входные диапазоны, но что-то вроде лабиринта 300x300 не кажется необоснованным и может заключать в себе очень длинные конечные пути.
JohnE
4
Почти все конечные лабиринты также могут вызвать переполнение стека. Это не действительная программа.
PyRulez
@johne Обновлен, поэтому предел рекурсии составляет порядка размера лабиринтов. К сожалению, добавлено 34 байта, но теперь это должно быть правильно (по крайней мере, настолько корректно, насколько это возможно).
Кайл Гуллион
5

Python 2 - 297 286 275 байт

Выбирает произвольную «открытую» ячейку, чтобы начать заполнение потока. Лабиринт бесконечен, если во время заполнения мы повторно посещаем ячейку, которую мы уже посетили, но у нее есть координата, отличная от предыдущего посещения. Если заливка заполняет весь регион, не найдя такой ячейки, попробуйте другой регион. Если такая область не может быть найдена, лабиринт конечен.

Принимает файл для обработки в командной строке, возвращает код 1завершения для бесконечного и 0для конечного.

Возвращает правильные результаты для всех тестов.

import sys
e=enumerate
C=dict([((i,j),1)for i,l in e(open(sys.argv[1]))for j,k in e(l)if'.'==k])
while C:
 d={}
 def f(r,c):
  n=(r%(i+1),c%j)
  if n in d:return(r,c)!=d[n]
  if C.pop(n,0):d[n]=(r,c);return any(map(f,[r-1,r,r+1,r],[c,c+1,c,c-1]))
 if f(*C.keys()[0]):exit(1)
макинтош
источник
1
Вы не можете предполагать, что какая-то клетка будет членом бесконечной пещеры, вы можете легко иметь как бесконечные, так и конечные пещеры.
VisualMelon
2
@VisualMelon: извините, описание не совсем верно. Код на самом деле проверяет все возможные области взаимосвязанных ячеек, а не только одну (как предполагается в настоящее время). Это то, для чего предназначен последний цикл while - выбор областей для проверки, пока еще остаются непроверенные ячейки.
Mac