Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Imagine a two-dimensional array of boolean values, where the 0s represent squares of grass on a rectangular plot of land and the 1s represent fences.

Write a function that accepts the 2D array as an input and determines whether you can travel from any one area of grass to any other area of grass, using only north/east/west/south movements, without running into a fence.

If any area of grass in the array is fully enclosed by fences (meaning you can't travel N/E/W/S to reach every other area of grass in the array) the function should return false; otherwise, it should return true.

Below are two sample arrays you can use as inputs, although your function should be able to handle not just these but any 2D array of boolean values:

0 0 0 0 0
0 1 0 0 0 
0 1 1 1 1
0 0 0 0 0
0 0 0 1 1

(should return true)

0 1 0 1 0
0 1 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 1 1 0 

(should return false, since the middle 0 in the top row is fully enclosed)

Shortest working code wins. I'll pick the winner after either a week has passed or there have been no new submissions within 24 hours.

share|improve this question
    
Can you also forbid binary operators? I'd love to see what people would come up with. –  Pierre Arlaud Jan 2 at 14:28
    
I do believe this is very similar to a USACO problem from last year (2012/2013 season). There are some huge test cases that can be accessed there... –  anorton Jan 2 at 14:52
    
Will the size of the array always be 5*5? –  ProgramFOX Jan 2 at 15:02
1  
@ProgramFOX Assume array could be any height, any width. And sure, output anything boolean. –  jawns317 Jan 2 at 16:02
1  
what about the 3X3 matrix 1 1 1; 1 0 1; 1 1 1? There is one grass cell in the center. Visually the grass cell in the center is fully enclosed by fences, but by your definition it is not. –  emory Jan 3 at 14:37

12 Answers 12

up vote 1 down vote accepted

Matlab 45

input('');c=bwconncomp(~ans,4);c.NumObjects<2
share|improve this answer
1  
@jawns317 I don't see why this is the accepted answer. This isn't a function. The only other answer that isn't a function accepts from stdin. This one doesn't even do that. –  Tim Seguine Jan 17 at 11:12
1  
Accepting standard input could be done as such input('');c=bwconncomp(~ans,4);c.NumObjects<2 This would make it 45 characters. –  Dennis Jaheruddin Jan 29 at 10:49

APL (39)

{∧/,⊃{⍺∨⊖⍵}/{⍵∨(∧\~⍵)∨⌽∧\⌽~⍵}¨s,⊖¨s←⊂⍵}

Usage:

      board1 board2
 0 0 0 0 0  0 1 0 1 0 
 0 1 0 0 0  0 1 1 0 0 
 0 1 1 1 1  0 0 0 0 0 
 0 0 0 0 0  0 0 0 1 0 
 0 0 0 1 1  1 1 1 1 0 
      {∧/,⊃{⍺∨⊖⍵}/{⍵∨(∧\~⍵)∨⌽∧\⌽~⍵}¨s,⊖¨s←⊂⍵} ¨ board1 board2
1 0
share|improve this answer
9  
The benefit of APL is that it looks so much like line noise that nobody wants to verify it is correct. –  Tim Seguine Jan 2 at 15:36
    
@Tim Anyone can download an interpreter to run it and check. –  Gareth Jan 2 at 19:24
3  
@Gareth Yeah, The comment was supposed to be tongue in cheek. –  Tim Seguine Jan 2 at 20:33
    
@Tim Oh sorry. Missed that. :-( –  Gareth Jan 2 at 23:00

Mathematica, 60 58 chars

f=Max@MorphologicalComponents[1-#,CornerNeighbors->1>2]<2&

Usage:

f[{{0, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 1, 1, 1, 1}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 1}}]

True

f[{{0, 1, 0, 1, 0}, {0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 1, 1, 0}}]

False

share|improve this answer
2  
Same length f=Max@WatershedComponents[Image@#,CornerNeighbors->1>2]<2& –  belisarius Jan 2 at 18:25

Ruby, 202 198 193

a=$<.read.split('
').map(&:split)
f=->x,y{a[x][y]=1
[[-1,0],[1,0],[0,-1],[0,1]].map{|o|d,e=x+o[0],y+o[1]
f[d,e]if a[d]&&a[d][e]==?0}}
f[i=a.index{|x|x.index ?0},a[i].index(?0)]
p !(a.join=~/0/)

Does a flood-fill, then checks to see if there are any 0s left.

share|improve this answer
    
Damn! If I hadn't tested my code first I would have been faster. ;) –  Tim Seguine Jan 2 at 15:15
    
@Tim But then it would have been wrong! :P –  Doorknob Jan 2 at 15:21

PHP 147 202 177 165 149 bytes

EDIT I beat my gzip hack with a real php solution.

A little long.... input as a text string, no spaces, rows delimited by newlines. It flood fills with cs and then checks to see if there are any zeros left. In the loop I use exp as a crude upper bound on the number of iterations required. I take advantage of the symmetry to handle the duplicate cases in less code

function f($s){$r=strpos;$n=$r($s,'
');$s[$r($s,'0')]=c;for(;$i++<1<<$n;)$s=strrev(ereg_replace('0(.{'.$n.'})?c','c\1c',$s));return!1==$r($s,'0');}

Here is an ungolfed test case:

<?php
$s1="00000
01000
01111
00000
00011";

$s2="01010
01100
00000
00010
11110";

function f($s){
    $n=strpos($s,"\n");
    $s[strpos($s,'0')]=c;
    for(;$i<strlen($s);++$i)
        $s=strrev(ereg_replace(
            '0(.{'.$n.'})?c',
            'c\1c'
            ,$s));
    return!1===strpos($s,'0');
}

var_dump(f($s1));
var_dump(f($s2));
share|improve this answer

Python (219 bytes)

Definitely not the shortest, but it's my first try here, so I'm proud of it:

def f(n):
 m=[int(c) for c in n if c!='\n']
 for i in range(len(m)):
  if m[i]<1:m[i]=2;break
 g(m,n.find('\n'),i);return not 0in m
def g(n,w,i):
 for x in i-w,i-1,i+1,i+w:
  if 0<=x<len(n):
   if n[x]<1:n[x]=2;g(n,w,x)

It's input should be a String of 0s & 1s where rows are delimited by a newline (\n) character.

Example usage:

>>> f("00000\n01000\n01111\n00000\n00011")
True
>>> f("01010\n01100\n00000\n00010\n11110")
False
share|improve this answer
    
you can combine the last two if statements into one with and, I think it saves some chars –  Tim Seguine Jan 2 at 21:07
    
You can use tabulator as 8 spaces. –  xfix Jan 2 at 21:22

Python (196)

Standard flood filling.

g=raw_input()
m=g.find(' ')
g=g.replace(' ','')
V={}
def D(V,x):
 if V.get(x,0)or g[x]=='1':return
 V[x]=1;[D(V,x+i)for i in 1,-1,m,-m if 0<=x+i<len(g)]
D(V,g.find('0'))
print len(V)==g.count('0')

Takes the matrix through STDIN with each row separated by a single space. For example "01010 01100 00000 00010 11110".

share|improve this answer

Mathematica 53

f=Max@(Symbol@@Names@"I*`i*B*l")[Image[1-#],0,1>2]<2&

It calls the internal function Image`MorphologicalOperationsDump`imageBinaryLabel, which is similar to MorphologicalComponents.

f[{{0, 0, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 1, 1, 1, 1}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 1}}]
f[{{0, 1, 0, 1, 0}, {0, 1, 1, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 1, 0}, {1, 1, 1, 1, 0}}]

True

False

share|improve this answer

Excel:VBA (215)305

Yes, haha VBA, but the matrix nature of the problem suggets a practical solution in Excel might be interesting (Plus someone has already submitted an answer in my other languages!). Obviously VBA is not going to be the most succinct, but I think it's reasonable.

This flood fills from an arbitrary starting point then checks if any "grass" left

R is a worksheet range with 1's and 0's representing the fences and grass as defined in the problem. Bonus, the playing field doesn't have to be rectangular or even contiguous.

0 1 1 1 1
0   0 0 0 0
0 1 1 1 1

For example, would return False. The zeros on the right can't be reached from the zeros on the left. The irregular field doesn't break it.

Function F(R)
L R, R.Find(0)
F = Not IsNumeric(R.Find(0))
End Function

Sub L(R, S As Range)
If S Or IsEmpty(S) Then Exit Sub
S = 1
L R, S.Offset(1, 0)
L R, S.Offset(-1, 0)
L R, S.Offset(0, 1)
L R, S.Offset(0, -1)
End Sub

Some notes on the golfing.

I think some chars could be trimmed if the requirement was inverted in regards to 1 and 0, but not enough to make it worth inverting.

VBA insists on a bunch a whitespace (a = b vs a=b), which doesn't help the char count.

S needs to be explicitly declared as a range. If it's left a variant, it turns into a range value rather than a range.

Maybe a better way to branch the flood? I couldn't come up with a loop that saved any chars to send it N/E/S/W

Edit: rethougt the base case on the flood fill, managed to trim quite a bit off by checking if it's at a base case after recursion rather than preventing the recursion.

share|improve this answer

PHP (286 chars)

Way too long, I probably went the long long way.

function D($a){$x=count($a);$y=count($a[0]);for($i=0;$i<$x;$i++)$a[$i][-1]=$a[$i][$y]=1;for($j=0;$j<$y;$j++)$a[-1][$j]=$a[$x][$j]=1;for($i=0;$i<$x;$i++){for($j=0;$j<$y;$j++){if($a[$i][$j]!=1){if($a[$i][$j-1]==1&&$a[$i][$j+1]==1&&$a[$i-1][$j]==1&&$a[$i+1][$j]==1)return 0;}}}return 1;}

Non-golfed:

function D($a)
{
$x=count($a);
$y=count($a[0]);
for ($i=0;$i<$x;$i++)
    $a[$i][-1]=$a[$i][$y]=1;
for ($j=0;$j<$y;$j++)
    $a[-1][$j]=$a[$x][$j]=1;
for ($i=0;$i<$x;$i++)
{
    for ($j=0;$j<$y;$j++)
    {
        if ($a[$i][$j] != 1)
        {
            if ($a[$i][$j-1] == 1 && $a[$i][$j+1] == 1 && $a[$i-1][$j] == 1 && $a[$i+1][$j] == 1)
                return 0;
        }
    }
}
return 1;
}
share|improve this answer
    
This isn't correct. It only checks to see if there are no single zeros which are surrounded by ones. There are more complicated ways to wall off zeroes. –  Tim Seguine Jan 2 at 15:32
    
Of course you are right. I was looking for another way to solve this without floodfills, I guess my search continues! –  Vereos Jan 2 at 16:13
    
It is just a graph reachability problem, and floodfill in this case is basically floyd-warshall without explicitly creating or representing the reachability graph. You could try to extract the graph and do the transitive closure yourself, but my guess is it will be longer. –  Tim Seguine Jan 2 at 20:55

C# (235)

int[][]D;int w,h,n;bool Q(int x,int y){var r=x>=0&&x<w&&y>=0&&y<h&&(D[x][y]++==0);if(r){Q(x-1,y);Q(x+1,y);Q(x,y+1);Q(x,y-1);}return r;}
bool P(int[][]B){D=B;w=D[0].Length;h=D.Length; for(int i=0;i<w*h;i++)if(Q(i%w,i/w))n++;return n==1;}

It tries to flood fill every cell in the board, it it makes only one flood fill returns true.

bool R( int x, int y)
{
    var r = (x >= 0 && x < w && y >= 0 && y < h && D[x, y]++ == 0);
    if (r)
    {
        R(x-1, y);
        R(x+1, y);
        R(x, y+1);
        R(x, y-1);
    }
    return r;
}

public bool Do()
{
    D = Board1;
    w = D.GetLength(0);
    h = D.GetLength(1);
    for (int x = 0; x < w; x++) for (int y = 0; y< h; y++) if (R(x, y)) n++;
    return n == 1;
}
share|improve this answer

Python 2.X + 3.X: 335 chararcters

Golfed:

def f(n):
 x,y=0,0
 z=lambda x,y:y<len(n)and x<len(n[0])and n[x][y]!=1
 while not z(x,y):
  y+=1
  if y==len(n):
   y=0
   x+=1
  if x==len(n[0]):
   return False
 t=set([(x,y)])
 v=set()
 while t:
  (x,y)=t.pop()
  v|=set([(x,y)])
  if z(x+1,y):
   t|=set([(x+1, y)])
  if z(x,y+1):
   t|=set([(x, y+1)])
 return len(v)+sum(map(sum,n))==len(n)*len(n[0])

Ungolfed:

def f(n):
    """In the following filed, starting from a 0: is it possible to
       get to every other 0?

        >>> f([[0,0,0,0,0],\
               [0,1,0,0,0],\
               [0,1,1,1,1],\
               [0,0,0,0,0],\
               [0,0,0,1,1]])
        True
        >>> f([[0,1,0,1,0],\
               [0,1,1,0,0],\
               [0,0,0,0,0],\
               [0,0,0,1,0],\
               [1,1,1,1,0]])
        False
        >>> f([[1,1,1,1,1],\
               [1,1,1,1,1],\
               [1,1,1,1,1],\
               [1,1,1,1,1],\
               [1,1,1,1,1]])
        False
        >>> f([[1,1,1,1,1],\
               [1,1,1,1,1],\
               [1,1,1,1,1],\
               [1,0,1,1,1],\
               [1,1,1,1,1]])
        True
        >>> f([[1,1,1,1,1],\
               [1,1,1,1,1],\
               [0,1,1,1,1],\
               [1,0,1,1,1],\
               [1,1,0,1,1]])
        False
        >>> f([[1,1,1,1,1],\
               [1,1,1,1,1],\
               [1,1,1,1,1],\
               [1,1,1,1,1],\
               [1,1,1,1,0]])
        True
    """
    x, y = 0,0
    isValid = lambda x,y: y<len(n) and x<len(n[0]) and n[x][y] != 1
    for i in range(len(n)*len(n[0])):
        x = i%len(n)
        y = i/len(n)
        if isValid(x,y):
            break

    while not isValid(x,y):
        y += 1
        if y == len(n):
            y = 0
            x += 1
        if x == len(n[0]):
            return False # Problem is not clearly defined here
    toGo=set([(x,y)])
    visited=set()
    while toGo:
        (x,y) = toGo.pop()
        visited |= set([(x,y)])
        if isValid(x+1,y):
            toGo |= set([(x+1, y)])
        if isValid(x,y+1):
            toGo |= set([(x, y+1)])
    return len(visited)+sum(map(sum,n)) == len(n)*len(n[0])

if __name__ == "__main__":
    import doctest
    doctest.testmod()
share|improve this answer
    
Could you move the golfed version to to the top? Some people have a user script for this site which counts the characters in the first block of code. –  Gareth Jan 11 at 19:46
    
@Gareth: Done.. –  moose Jan 11 at 19:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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