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:

###
#.#
###

.#
#.

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

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

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

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

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


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

Can the infinite labyrinth be a straight line that goes to infinity. — user38740, Commented Mar 31, 2015 at 2:23
@Neil I'm not sure what you mean. The first and second infinite examples have infinite lines, but there is at least one . and one # in the input. — Zgarb, Commented Mar 31, 2015 at 7:12

VisualMelon · Accepted Answer · 2015-03-31 01:41:38Z

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

Probably the first time I've seen a C# answer as the top vote getter here. — Michael McGriff, Commented Mar 31, 2015 at 17:59

Kyle G · Accepted Answer · 2015-03-31 23:38:16Z

10

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

edited Mar 31, 2015 at 23:38

answered Mar 31, 2015 at 3:06

Kyle G

8706 silver badges14 bronze badges

1

\$\begingroup\$ You can save some bytes by using ; for the lines in p, as you'll get them on the same line with the if. \$\endgroup\$
– PurkkaKoodari
Commented Mar 31, 2015 at 10:29
11

\$\begingroup\$ "If stack overflow return true" - I like that recursion end condition :) \$\endgroup\$
– schnaader
Commented Mar 31, 2015 at 13:31
3

\$\begingroup\$ I'm not convinced this is a valid approach. Using stack overflows to detect an "infinite" region will produce false positives. The problem spec doesn't state any limitations on input ranges but something like a 300x300 labyrinth doesn't seem unreasonable and could enclose very long finite paths. \$\endgroup\$
– JohnE
Commented Mar 31, 2015 at 23:14
5

\$\begingroup\$ Almost all finite mazes would also cause a stack overflow. This is not a valid program. \$\endgroup\$
– Christopher King
Commented Mar 31, 2015 at 23:39
\$\begingroup\$ @johne Updated so the recursion limit is on the order of the size of the labyrinths. Added 34 bytes unfortunately but it should be correct now (at least as correct as a hack like this can be). \$\endgroup\$
– Kyle G
Commented Mar 31, 2015 at 23:45

Add a comment |

Mac · Accepted Answer · 2015-04-01 00:12:50Z

5

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)

edited Apr 1, 2015 at 0:12

answered Mar 31, 2015 at 3:09

Mac

7394 silver badges9 bronze badges

1

\$\begingroup\$ You can't assume that some any cell will be a member of an infinite cavern, you can easily have both infinite and finite caverns. \$\endgroup\$
– VisualMelon
Commented Mar 31, 2015 at 9:35
2

\$\begingroup\$ @VisualMelon: sorry, the description isn't entirely correct. The code does actually check every possible region of interconnected cells, not just one (as is currently implied). That's what the final while loop is for - selecting regions to check while there are still any unchecked cells left. \$\endgroup\$
– Mac
Commented Mar 31, 2015 at 11:19

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

Yeah, daft modulo was a pain in C# as well, but I think I've found a way to make good use of it in my working copy with the directional code (I'll only re-post if I can get a 10% reduction or better): (j%4-1)%2 gives a nice repeating pattern. — VisualMelon, Commented Apr 1, 2015 at 0:23
I believe unnamed functions are permissible, and, thus, unless thfunction includes a call to itself (it would appear not to) it is permissible to not count the L= towards the byte count. — SuperJedi224, Commented Jun 13, 2015 at 16:45
@SuperJedi224 you're probably right, but it's short enough as is after all — edc65, Commented Jun 13, 2015 at 19:37

Stack Exchange Network

Infinite Labyrinths

Background

Input

Output

Rules

Additional Test Cases

4 Answers 4

C# - 423 375 bytes

Python 2 - 258 210 244 bytes

Python 2 - 297 286 275 bytes

JavaScript (ES6), 235 253

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
grid
graph-theory
decision-problem
maze
or ask your own question.

Hot Network Questions

Infinite Labyrinths

Background

Input

Output

Rules

Additional Test Cases

4 Answers 4

C# - 423 375 bytes

Python 2 - 258 210 244 bytes

Python 2 - 297 286 275 bytes

JavaScript (ES6), 235 253

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfgridgraph-theorydecision-problemmaze or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
grid
graph-theory
decision-problem
maze
or ask your own question.