Hintergrund

Sie sind der Lehrling eines mächtigen Zauberers, und Ihr Meister entwickelt derzeit einen Zauberspruch für die Schaffung eines interdimensionalen Labyrinths, in das er seine Feinde einfängt. Er möchte, dass Sie seinen dampfbetriebenen Computer so programmieren, dass er die möglichen Layouts analysiert. Das Programmieren dieser teuflischen Maschine ist äußerst gefährlich, daher sollten Sie den Code so kurz wie möglich halten.

Eingang

Ihre Eingabe ist ein zweidimensionales Raster aus Punkten .und Hashes #, das leere Räume und Wände als durch Zeilenumbrüche getrennte Zeichenfolge kennzeichnet. Es wird immer mindestens eins .und eins geben #, und Sie können entscheiden, ob es eine nachgestellte Zeile gibt oder nicht.

Dieses Gitter ist die Blaupause eines unendlichen Labyrinths, bei dem unendlich viele Kopien des Gitters nebeneinander ausgerichtet werden. Das Labyrinth ist in Hohlräume unterteilt , die miteinander verbundene Bestandteile von Leerräumen sind (diagonal benachbarte Räume sind nicht miteinander verbunden). Zum Beispiel das Gitter

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

ergibt folgendes Labyrinth (unendlich in alle Richtungen fortgesetzt):

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

Dieses besondere Labyrinth enthält einen Hohlraum mit unendlicher Fläche. Andererseits führt diese Blaupause zu einem Labyrinth mit nur endlichen Hohlräumen:

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

Ausgabe

Ihre Ausgabe ist ein wahrer Wert, wenn das Labyrinth eine unendliche Höhle enthält, und ein falscher Wert, wenn nicht. Beachten Sie, dass das Labyrinth sowohl endliche als auch unendliche Hohlräume enthalten kann. In diesem Fall ist die Ausgabe wahr.

Regeln

Sie können ein vollständiges Programm oder eine Funktion schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Zusätzliche Testfälle

Unendliche Hohlräume:

.#

#.#
...
#.#

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

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

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

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

Endliche Hohlräume:

###
#.#
###

.#
#.

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

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

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

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

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


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

JavaScript (ES6), 235 253

Gleiche Methode wie bei @mac. Für jede freie Zelle versuche ich eine rekursive Füllung und markiere benutzte Zellen mit der von mir verwendeten Koordinate (die außerhalb der Originalvorlage liegen kann). Wenn ich während des Füllens zu einer Zelle komme, die bereits mit einer anderen Koordinate markiert ist, befinde ich mich auf einem unendlichen Pfad.

Die skurrile Art, mit dem Modulo in JS umzugehen, ist ziemlich ärgerlich.

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

Test In der Firefox / FireBug-Konsole

Unendlich

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

Ausgabe

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

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

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

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

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

Endlich

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

Ausgabe

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

".#
#." false

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

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

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

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

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

C # - 423 375 Bytes

Vollständiges C # -Programm, akzeptiert Eingaben über STDIN, gibt je nach Bedarf "True" oder "False" an STDOUT aus.

Ich konnte es nicht ertragen, diesen Linq dort zu lassen ... zum Glück hat sich seine Entfernung ausgezahlt! Es verfolgt jetzt gesehene und besuchte Zellen in einem Array (da es sowieso immer nur eine begrenzte Anzahl von ihnen betrachtet). Ich habe auch den Richtungscode neu geschrieben, um die Notwendigkeit für ein Lambda zu beseitigen und den Code im Allgemeinen unverständlicher zu machen (aber mit erheblichen Byteeinsparungen).

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

Es ist eine Breitensuche (nicht, dass es darauf ankommt), die nur so lange dauert, bis sie entweder in einer endlichen Höhle steckt oder die Höhle so groß ist, dass sie unendlich groß sein muss (wenn sie so viele Zellen wie die hat) Dies bedeutet, dass es einen Pfad von einer Zelle zu sich selbst geben muss, dem wir für immer folgen können.

Nicht zugeschnittener Code:

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 Bytes

Überprüfen Sie rekursiv die Pfade, wenn der Stapelüberlauf 1 (wahr) zurückgibt, andernfalls None (falsch).

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 Bytes

Wählt eine beliebige "offene" Zelle aus, von der aus eine Überflutung beginnen soll. Labyrinth ist unendlich, wenn wir während des Füllens eine Zelle erneut besuchen, die wir bereits besucht haben, aber sie hat eine andere Koordinate als der vorherige Besuch. Wenn die Überflutungsfüllung die gesamte Region ausfüllt, ohne eine solche Zelle zu finden, versuchen Sie es mit einer anderen Region. Wenn eine solche Region nicht gefunden werden kann, ist das Labyrinth endlich.

Lässt die Datei in der Befehlszeile verarbeiten, gibt den Exit-Code 1für unendlich und zurück0 für endlich zurück.

Gibt korrekte Ergebnisse für alle Testfälle zurück.

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)