6
\$\begingroup\$

You are locked in a massive fortress, slowly starving to death. Your guards inform you that there is food in the fortress, and even tell you where it is and provide a map of the building.

However, you are not sure that you can actually reach the food, given that the every door is locked, and every room is its own labyrinth. Are you able to reach the food? If you're in the same room, you should try. If you're not in the same room, then you might as well stay put, preserving your strength in case help from the outside world comes.

Input

Two arrays: 3 coordinates of where you are, and 3 coordinates of where the food is. (Both are 0-based)

:Optional: an array of three numbers, indicating the size of the following fortress in each dimension.

A three dimensional array of the fortress, where each point in the array is either 1/true (if that point is a wall) or 0/false (if the point is empty). The array is a rectangular prism, and there is no guarantee that the structure follows the laws of physics. (Thus, the bottom floor might be completely empty.)

The place where you are and the place where the food is both have a 0/false.

Output

Are the two points in the same room, unseparated by a wall? Note that you can not move through a diagonal.

Format

You may write a program or a function.

The input may be through STDIN, command line or function arguments, or reading from a file. If you choose a text-based input (like STDIN) you may use any delimiters to help your program parse the input.

The output may be through STDOUT or the function result. You can output/return "true"/"false", 0/1, or the like.

Examples

In these examples, I put a Y where you are, and a F where the food is. This is just to help you understand the examples; in the actual input they would be 0/false.

Input

[0 0 1]      // You are at x = 0, y = 0, z = 1
[1 2 2]      // The food is at x = 1, y = 2, z = 2
[[[0 0 0]    // z = 0, y = 0
  [0 0 0]    // z = 0, y = 1
  [1 1 1]]   // z = 0, y = 2
 [[Y 0 0]
  [0 0 0]    // z = 1
  [1 1 1]]
 [[0 0 0]
  [1 1 0]    // z = 2
  [0 F 0]]]

Output

True. (The places are connected. You can move from [0 0 1] > [2 0 1] > [2 0 2] > [2 2 2] > [1 2 2].)

Input

[3 0 1]    
[1 1 0]
[4 2 2]         // If you want, you can include this in the input, to indicate the fortress's size
[[[0 1 0 0]     // z = 0, y = 0
  [0 F 1 0]]    // z = 0, y = 1
 [[0 0 1 Y]
  [0 1 0 0]]]

Output

False. (There are two rooms. Your room includes [2 0 0], [2 1 1], [3 0 0], [3 0 1], [3 0 1], and [3 1 1]. The food's room includes the other empty spaces. Note that a wall of 1's divides the fortress in half.

Winning criterion

Code golf. Shortest code for your function/program wins.

\$\endgroup\$
11
  • \$\begingroup\$ What is the maximum size of the array? And how does the program know the size of the array? Is that input too? or is it given by carriage returns or EOF markers in the input? \$\endgroup\$ Jun 3, 2014 at 18:52
  • \$\begingroup\$ @steveverrill I edited to allow an optional line for the size. Note that this isn't necessary in many languages (like Java). \$\endgroup\$
    – Ypnypn
    Jun 3, 2014 at 18:58
  • \$\begingroup\$ Can you move up or down whenever the target direction is empty? \$\endgroup\$
    – seequ
    Jun 3, 2014 at 18:59
  • \$\begingroup\$ "...you may use any delimiters to help your program parse the input." I'm not 100% sure how much freedom I have here. Is [0,0,1],[1,2,2],[[[0,0,0],[0,0,0],[1,1,1]],[[0,0,0],[0,0,0],[1,1,1]],[[0,0,0],[1,1,0],[0,0,0]]] a valid way to format your first example? \$\endgroup\$ Jun 3, 2014 at 19:08
  • 1
    \$\begingroup\$ Is [0,0,1],[1,2,2],[3,3,3],[0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,1,1,1,0,0,0,​1,1,0,0,0,0] a valid input? \$\endgroup\$
    – seequ
    Jun 3, 2014 at 20:08

4 Answers 4

4
\$\begingroup\$

Python 2.x - 177 168 167 bytes

Basic flood fill to kick the game going. Requires the dungeon size.

f,(a,b,c),(w,h,d),p=input()
def l(x,y,z):
 if w>x>-1<y<h>0<=z<d and p[z][y][x]<1:p[z][y][x]=2;[(l(x+i,y,z),l(x,y+i,z),l(x,y,z+i))for i in-1,1]
l(*f)
print p[c][b][a]>1

Examples:

Input:  [0,0,1],[1,2,2],[3,3,3],[[[0,0,0],[0,0,0],[1,1,1]],[[0,0,0],[0,0,0],[1,1,1]],[[0,0,0],[1,1,0],[0,0,0]]]
Output: True

Input:  [3,0,1],[1,1,0],[4,2,2],[[[0,1,0,0],[0,0,1,0]],[[0,0,1,0],[0,1,0,0]]]
Output: False

Ungolfed code:

(e,f,g),(a,b,c),(w,h,d),field=input()

def fill(x,y,z):
    if 0<=x<w and 0<=y<h and 0<=z<d and field[z][y][x]<1:
        field[z][y][x]=2
        fill(x+1,y,z)
        fill(x-1,y,z)
        fill(x,y-1,z)
        fill(x,y+1,z)
        fill(x,y,z-1)
        fill(x,y,z+1)

fill(e,f,g)
print field[c][b][a]==2
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 173 bytes

f=(v=#;(v=ReplacePart[v,Reverse[#+1]->#2])&@@@{{#3,2},{#4,3}};VertexConnectivity[VertexDelete[GridGraph[#2],Join@@(l=Flatten@v)~(s=Position)~1],(h=s[l,#][[1,1]]&)@2,h@3]>0)&

This defines a function f which can be called like

f[{{{0,1,0,0},...}, {4,2,2}, {3,0,1}, {1,1,0}]

using your second example.

Ungolfed:

f = (
   v = #;
   (v = ReplacePart[v, Reverse[# + 1] -> #2]) & @@@ {{#3, 2}, {#4, 3}};
   VertexConnectivity[
    VertexDelete[
     GridGraph[#2],
     Join @@ (l = Flatten@v )~(s = Position)~1
     ],
    (h = s[l, #][[1, 1]] &)@2,
    h@3] > 0
   ) &

I'm simply creating a grid graph for the entire building, then delete all walls (and their adjacent edges) from the graph and then check that the two vertices are connected.

\$\endgroup\$
3
  • \$\begingroup\$ +1 Nice idea. Also, coming this close to Mathematica is awesome. \$\endgroup\$
    – seequ
    Jun 3, 2014 at 20:13
  • \$\begingroup\$ @TheRare Thanks! :) Once the OP answers our questions, I might be able to shave off up to 15 bytes, I think. ;) \$\endgroup\$ Jun 3, 2014 at 20:15
  • \$\begingroup\$ And for now, I have beaten you. Mwah. \$\endgroup\$
    – seequ
    Jun 3, 2014 at 20:39
1
\$\begingroup\$

GolfScript, 93 characters

~[[]]@{,`{{1$+}%\;~}+%}/:A[\{{~}/}%]zip{~!*}%:S;]1/~{{3,{)1$/.())+\+\()(+\+}%{[]*}/}%S&}A,*&,

The code expects the input as specified above (including the fortress' dimensions) on STDIN. The result is 1 if food is reachable and 0 otherwise.

Try the code online.

\$\endgroup\$
1
\$\begingroup\$

Javascript (E6) 123 128 132 140 167 286 344

First try. Simple fill, not recursive, fortress size not needed.
Must simplify multidimensional array handling (90 chars!!).

Edit Recursive fill, no need to know the fortress dimensions, should work even for irregular shapes.
Edit Tips by TheRare to shorten the recursive call & golf more
Edit Contribution by MT0, cut same () and use exact equal
Edit Contribution by nderscore, multidimensional array handling (learned sth new again)
Edit With a clever trick, nderscore bring the food check back inside the loop, where it belongs. Now returning a boolean, 'some' is more fit than 'map' (and shorter)

A=(Y,F,M)=>(S=(x,y,z)=>(t=(M[z]||0)[y]||0)[x]-1&&[x,y,z]+''==F|[-1,t[x]=1].some(d=>S(x+d,y,z)|S(x,y+d,z)|S(x,y,z+d)))(...Y)

Usage

A([0,0,1],[1,2,2],
  [[[0,0,0],[0,0,0],[1,1,1]],
  [[0,0,0],[0,0,0],[1,1,1]],
  [[0,0,0],[1,1,0],[0,0,0]]])

Return 1

A([3,0,1],[1,1,0],
  [[[0,1,0,0],[0,0,1,0]],[[0,0,1,0],[0,1,0,0]]])

Return 0

Ungolfed

A=(Y,F,M)=>
  (S=(x,y,z)=>
     (t=(M[z]||0)[y]||0)[x]-1 // NaN==out,-1==open,0==wall or visited
     && [x,y,z]+''==F // compare with food position converting to string
     | [-1,t[x]=1] // mark as visited, then recurse popping out the return value if true
       .some(d=>S(x+d,y,z)|S(x,y+d,z)|S(x,y,z+d))
  )(...Y)
\$\endgroup\$
19
  • 1
    \$\begingroup\$ I would recommend the same trick I used in my Python answer, as this looks a lot like it (hint hint). That is, for(i as [-1,1]){S(x+i,y,z),S(x,y+i,z),S(x,y,z+i)} I'm not sure if this is legit ES6, but I'm sure you got the idea. \$\endgroup\$
    – seequ
    Jun 5, 2014 at 13:00
  • \$\begingroup\$ @TheRare 'a fill is a fill is a fill'... I borrowed the check for food found from your solution, mine was faster but yours was shorter. Next edit, i'll give a try to your hint. \$\endgroup\$
    – edc65
    Jun 5, 2014 at 13:53
  • 1
    \$\begingroup\$ F=(Y,F,M)=>(S=(x,y,z)=>M[z]&&(X=M[z][y])&&X[x]===0&&(X[x]=2,[-1,1].map(d=>S(x+d,y,z)&S(x,y+d,z)&S(x,y,z+d))))(...Y)&&M[F[0]][F[1]][F[2]] \$\endgroup\$
    – MT0
    Jun 5, 2014 at 21:19
  • 1
    \$\begingroup\$ 128: A=(s,f,m)=>(F=(x,y,z)=>(M=(m[z]||0)[y]||0)[x]-1&&[-1,M[x]=1].map(a=>F(x+a,y,z)|F(x,y+a,z)|F(x,y,z+a)))(...s)|m[f[2]][f[1]][f[0]] \$\endgroup\$
    – nderscore
    Jun 6, 2014 at 4:44
  • 1
    \$\begingroup\$ 127: A=(s,f,m)=>(F=(x,y,z)=>(M=(m[z]||0)[y]||0)[x]-1&&[x,y,z]+[]==f|[-1,M[x]=1].map(a=>s|=F(x+a,y,z)|F(x,y+a,z)|F(x,y,z+a))|s)(...s) \$\endgroup\$
    – nderscore
    Jun 6, 2014 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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