Infinite Labyrinths

Question

Background

You are the apprentice of a powerful wizard, and your master is currently developing a spell for creating an inter-dimensional labyrinth to trap his enemies in. He wants you to program his steam-powered computer to analyze the possible layouts. Programming this diabolical machine is highly dangerous, so you'll want to keep the code as short as possible.

Input

Your input is a two-dimensional grid of periods . and hashes #, signifying empty space and walls, given as a newline-delimited string. There will always be at least one . and one #, and you can decide whether there is a trailing newline or not.

This grid is the blueprint of an infinite labyrinth, which is made by aligning infinitely many copies of the grid next to each other. The labyrinth is divided into cavities, which are connected components of empty spaces (diagonally adjacent spaces are not connected). For example, the grid

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

results in the following labyrinth (continued infinitely in all directions):

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

This particular labyrinth contains a cavity of infinite area. On the other hand, this blueprint results in a labyrinth with only finite cavities:

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

Output

Your output shall be a truthy value if the labyrinth contains an infinite cavity, and a falsy value if not. Note that the labyrinth may contain both finite and infinite cavities; in that case, the output shall be truthy.

Rules

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Additional Test Cases

Infinite cavities:

.#

#.#
...
#.#

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

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

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

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

Finite cavities:

###
#.#
###

.#
#.

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

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

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

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

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


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

Answer 1

JavaScript (ES6), 235 253

Same method used by @mac. For each free cell, I try a recursive fill, marking used cells with the coordinate I am using (that can be outside the orginal template). If during the fill I arrive to a cell already marked having a different coordinate, I am in an infinite path.

The quirky way of handling the modulo in JS it's quite annoying.

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 Firefox / FireBug console

Infinite

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

Output

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

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

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

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

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

Finite

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

Output

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

".#
#." false

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

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

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

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

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

Answer 2

C# - 423 375 bytes

Complete C# program, accepts input via STDIN, outputs "True" or "False" to STDOUT as appropriate.

I could not bare to leave that Linq in there... thankfully its removal paid off! It now keeps track of seen and visited cells in an array (given it only ever looks at a finite number of them anyway). I also re-wrote the directional code, removing the need for a Lambda, and generally making the code more impossible to understand (but with substantial byte savings).

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

It is a breadth-first (not that this matters) search which just carries on until it either gets stuck in a finite cavern, or it decides the cavern is big enough that it must be infinitely large (when it has as many cells as the original rectangle, this means there must be a path from one cell to itself somewhere else, which we can continue to follow forever).

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

Answer 3

Python 2 - 258 210 244 bytes

Recursively check paths, if stack overflow return 1 (truthy) else return None (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])

Answer 4

Python 2 - 297 286 275 bytes

Picks an arbitrary "open" cell to begin a flood fill from. Labyrinth is infinite if during the fill we re-visit a cell we've already visited, but it has a different coordinate to the previous visit. If the flood fill fills the entire region without finding such a cell, try a different region. If such a region can't be found, the labyrinth is finite.

Takes file to process on command line, returns exit code 1 for infinite, and 0 for finite.

Returns correct results for all test cases.

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)