22
\$\begingroup\$

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.

\$\endgroup\$
10
  • \$\begingroup\$ Can you also forbid binary operators? I'd love to see what people would come up with. \$\endgroup\$ Jan 2, 2014 at 14:28
  • \$\begingroup\$ 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... \$\endgroup\$
    – apnorton
    Jan 2, 2014 at 14:52
  • 1
    \$\begingroup\$ @ProgramFOX Assume array could be any height, any width. And sure, output anything boolean. \$\endgroup\$
    – jawns317
    Jan 2, 2014 at 16:02
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – emory
    Jan 3, 2014 at 14:37
  • 1
    \$\begingroup\$ What if the array is all 1s? What should it return then? \$\endgroup\$
    – Joe
    Jan 6, 2014 at 18:10

12 Answers 12

8
\$\begingroup\$

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
\$\endgroup\$
4
  • 9
    \$\begingroup\$ The benefit of APL is that it looks so much like line noise that nobody wants to verify it is correct. \$\endgroup\$ Jan 2, 2014 at 15:36
  • \$\begingroup\$ @Tim Anyone can download an interpreter to run it and check. \$\endgroup\$
    – Gareth
    Jan 2, 2014 at 19:24
  • 3
    \$\begingroup\$ @Gareth Yeah, The comment was supposed to be tongue in cheek. \$\endgroup\$ Jan 2, 2014 at 20:33
  • \$\begingroup\$ @Tim Oh sorry. Missed that. :-( \$\endgroup\$
    – Gareth
    Jan 2, 2014 at 23:00
4
\$\begingroup\$

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

\$\endgroup\$
1
  • 2
    \$\begingroup\$ Same length f=Max@WatershedComponents[Image@#,CornerNeighbors->1>2]<2& \$\endgroup\$ Jan 2, 2014 at 18:25
4
\$\begingroup\$

Excel VBA, 305 215 Bytes

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Damn! If I hadn't tested my code first I would have been faster. ;) \$\endgroup\$ Jan 2, 2014 at 15:15
  • \$\begingroup\$ @Tim But then it would have been wrong! :P \$\endgroup\$
    – Doorknob
    Jan 2, 2014 at 15:21
3
\$\begingroup\$

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));
\$\endgroup\$
0
2
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ you can combine the last two if statements into one with and, I think it saves some chars \$\endgroup\$ Jan 2, 2014 at 21:07
  • \$\begingroup\$ You can use tabulator as 8 spaces. \$\endgroup\$
    – 0..
    Jan 2, 2014 at 21:22
2
\$\begingroup\$

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".

\$\endgroup\$
2
\$\begingroup\$

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

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

Matlab 45

input('');c=bwconncomp(~ans,4);c.NumObjects<2
\$\endgroup\$
2
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ Jan 17, 2014 at 11:12
  • 1
    \$\begingroup\$ Accepting standard input could be done as such input('');c=bwconncomp(~ans,4);c.NumObjects<2 This would make it 45 characters. \$\endgroup\$ Jan 29, 2014 at 10:49
1
\$\begingroup\$

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;
}
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 2, 2014 at 15:32
  • \$\begingroup\$ Of course you are right. I was looking for another way to solve this without floodfills, I guess my search continues! \$\endgroup\$
    – Vereos
    Jan 2, 2014 at 16:13
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 2, 2014 at 20:55
1
\$\begingroup\$

C#, 235 Bytes

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;
}
\$\endgroup\$
0
\$\begingroup\$

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()
\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Gareth
    Jan 11, 2014 at 19:46
  • \$\begingroup\$ @Gareth: Done.. \$\endgroup\$ Jan 11, 2014 at 19:49

Your Answer

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

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