tło

Jesteś uczniem potężnego czarodzieja, a twój mistrz obecnie opracowuje zaklęcie do tworzenia międzywymiarowego labiryntu, aby uwięzić swoich wrogów. Chce, abyś zaprogramował swój komputer napędzany parą, aby analizował możliwe układy. Programowanie tej diabelskiej maszyny jest bardzo niebezpieczne, więc będziesz chciał, aby kod był jak najkrótszy.

Wkład

Twój wkład jest dwuwymiarową siatką kropek .i skrótów #, oznaczającą pustą przestrzeń i ściany, podaną jako ciąg rozdzielany znakiem nowej linii. Zawsze będzie co najmniej jeden .i jeden #, i możesz zdecydować, czy jest końcowy znak nowej linii, czy nie.

Ta siatka jest planem nieskończonego labiryntu, który powstaje przez wyrównanie nieskończenie wielu kopii siatki obok siebie. Labirynt jest podzielony na wnęki , które są połączonymi komponentami pustych przestrzeni (przestrzenie sąsiadujące ze sobą po przekątnej nie są połączone). Na przykład siatka

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

skutkuje następującym labiryntem (kontynuowanym nieskończenie we wszystkich kierunkach):

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

Ten szczególny labirynt zawiera wgłębienie nieskończonego obszaru. Z drugiej strony ten plan daje labirynt z tylko skończonymi wnękami:

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

Wydajność

Twój wynik powinien być prawdziwą wartością, jeśli labirynt zawiera nieskończoną wnękę, a wartość fałszu, jeśli nie. Zauważ, że labirynt może zawierać zarówno skończone, jak i nieskończone wnęki; w takim przypadku dane wyjściowe będą zgodne z prawdą.

Zasady

Możesz napisać pełny program lub funkcję. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Dodatkowe przypadki testowe

Nieskończone wgłębienia:

.#

#.#
...
#.#

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

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

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

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

Skończone wnęki:

###
#.#
###

.#
#.

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

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

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

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

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


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

JavaScript (ES6), 235 253

Ta sama metoda stosowana przez @mac. Dla każdej wolnej komórki próbuję wypełnić rekurencyjnie, zaznaczając używane komórki współrzędną, której używam (która może znajdować się poza pierwotnym szablonem). Jeśli podczas wypełniania dojdę do komórki oznaczonej już inną współrzędną, jestem na nieskończonej ścieżce.

Ekscentryczny sposób obsługiwać modulo w JS to dość irytujące.

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

Przetestuj w konsoli Firefox / FireBug

Nieskończony

['##.###\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)))

Wydajność

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

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

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

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

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

Skończone

['###\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)))

Wydajność

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

".#
#." false

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

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

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

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

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

C # - 423 375 bajtów

Kompletny program w języku C #, akceptuje wprowadzanie danych przez STDIN, w razie potrzeby przekazuje STDOUT „True” lub „False”.

Nie mogłem się powstrzymać przed pozostawieniem tam Linq ... na szczęście jego usunięcie się opłaciło! Teraz śledzi widoczne i odwiedzane komórki w tablicy (biorąc pod uwagę, że i tak tylko przegląda ich skończoną liczbę). Ponownie napisałem kod kierunkowy, eliminując potrzebę korzystania z Lambda i ogólnie czyniąc kod trudniejszym do zrozumienia (ale przy znacznych oszczędnościach bajtów).

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

Jest to pierwsze wyszukiwanie (nie ma to znaczenia), które trwa, dopóki nie utknie w skończonej jaskini lub zdecyduje, że jest ona na tyle duża, że ​​musi być nieskończenie duża (gdy ma tyle komórek, ile oryginalny prostokąt, oznacza to, że musi istnieć ścieżka z jednej komórki do siebie gdzieś indziej, którą będziemy mogli podążać wiecznie).

Nieprzetworzony kod:

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

Python 2 - 258 210 244 bajtów

Rekurencyjnie sprawdzaj ścieżki, jeśli przepełnienie stosu zwraca 1 (prawda), w przeciwnym razie zwraca Brak (falsey).

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

Python 2 - 297 286 275 bajtów

Wybiera dowolną „otwartą” komórkę, aby rozpocząć wypełnianie zalewowe. Labirynt jest nieskończony, jeśli podczas wypełnienia ponownie odwiedzimy komórkę, którą już odwiedziliśmy, ale ma inną współrzędną niż poprzednia wizyta. Jeśli wypełnienie powodziowe wypełni cały region bez znalezienia takiej komórki, wypróbuj inny region. Jeśli takiego regionu nie można znaleźć, labirynt jest skończony.

Pobiera plik do przetworzenia w wierszu poleceń, zwraca kod wyjścia 1dla nieskończoności i0 dla skończonego.

Zwraca prawidłowe wyniki dla wszystkich przypadków testowych.

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)