35
\$\begingroup\$

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:

###
#.#
###

.#
#.

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

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

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

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

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


###########
........#..
#########.#
..........#
.##########
.#.........
##.########
...#.......
\$\endgroup\$
  • \$\begingroup\$ Is there a trailing newline character? \$\endgroup\$ – FUZxxl Mar 30 '15 at 16:06
  • \$\begingroup\$ @FUZxxl That's up to you. \$\endgroup\$ – Zgarb Mar 30 '15 at 16:07
  • \$\begingroup\$ Can the infinite labyrinth be a straight line that goes to infinity. \$\endgroup\$ – user38740 Mar 31 '15 at 2:23
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Zgarb Mar 31 '15 at 7:12
  • 1
    \$\begingroup\$ Nice challenge, more difficult than it seems \$\endgroup\$ – edc65 Mar 31 '15 at 23:34
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – VisualMelon Apr 1 '15 at 0:23
  • \$\begingroup\$ 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. \$\endgroup\$ – SuperJedi224 Jun 13 '15 at 16:45
  • \$\begingroup\$ @SuperJedi224 you're probably right, but it's short enough as is after all \$\endgroup\$ – edc65 Jun 13 '15 at 19:37
21
\$\begingroup\$

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
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Probably the first time I've seen a C# answer as the top vote getter here. \$\endgroup\$ – Michael McGriff Mar 31 '15 at 17:59
  • 1
    \$\begingroup\$ Main() in struct, now thats cute. \$\endgroup\$ – PTwr Apr 1 '15 at 7:05
10
\$\begingroup\$

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])
\$\endgroup\$
  • 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 Mar 31 '15 at 10:29
  • 11
    \$\begingroup\$ "If stack overflow return true" - I like that recursion end condition :) \$\endgroup\$ – schnaader Mar 31 '15 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 Mar 31 '15 at 23:14
  • 4
    \$\begingroup\$ Almost all finite mazes would also cause a stack overflow. This is not a valid program. \$\endgroup\$ – PyRulez Mar 31 '15 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 Gullion Mar 31 '15 at 23:45
5
\$\begingroup\$

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)
\$\endgroup\$
  • 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 Mar 31 '15 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 Mar 31 '15 at 11:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.