Is this figure connected?

Question

You are given a list of (x,y) grid coordinates. Your function should decide whether the figure obtained by coloring in the squares of the grid with the given coordinates is connected or not.

Squares adjacent diagonally are not considered connected.

Example input:

(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),
(1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)

which looks like:

****
*
****
   *
****

Output:

YES

Example input:

(0,0),(1,0),(2,0),(0,1),(0,2),(2,2),(3,2),(4,2),(0,3),
(4,3),(0,4),(1,4),(2,4),(4,4),(4,5),(2,6),(3,6),(4,6)

which looks like:

  ***
    *
*** *
*   *
* ***
*
***

Output:

NO

Your function must take as input a list of pairs of integers (e.g. in C++, maybe vector<pair<int,int>>) and return a boolean. You may not assume any particular ordering of the input points. The coordinates will be between 0 and 99 inclusive.

Smallest code wins.

Answer 1

c99 -- 620ish neccessary characters

#include <stdlib.h>
#define S return
typedef struct n N;struct n{int x,y;N*n;};
N*I(int x,int y,N*l){if(!l)goto z;N*m=l;do{if((m->x==x)&&(m->y==y))
S m;m=m->n;}while(m!=l);z:S NULL;}N*A(N*n,N*l){if(!l)n->n=n,l=n;
else n->n=l->n,l->n=n;S l;}N*R(N*n,N*l){if(!l||(l==n&&n->n==n))goto z;
N*m=l;do{if(m->n==n){m->n=n->n;S m;}m=m->n;}while(m!=l);z:S NULL;}
int E(N*l){int i=0;if(!l)goto z;N*m=l;do{++i;m=m->n;}while(m!=l);z:S i;}
int C(N*l){N*c=NULL,*n=l,*m=l=R(n,l);c=A(n,c);int a=E(l)*E(l);do{
if(!l)S 1;n=m->n;if(I(m->x-1,m->y,c)||I(m->x+1,m->y,c)||I(m->x,m->y-1,c)
||I(m->x,m->y+1,c))l=R(m,l),c=A(m,c);m=n;}while(--a);S 0;}

More than half the bulk is taken up by a minimal implementation of a linked list---c is horribly deficient in that sense.

The code here includes the definition of the nodes and all the list manipulation functions called by C, my connectedness checker.

The method is to maintain two lists (one of connected nodes initialized by the first node) and one of yet-to-be-connected nodes (starting with everything else). What follows is an exhaustive cyclic search to find a connection for each node in turn. There is an upper limit on the number of attempts conservatively set to length-of-the-list squared, which marks the end of attempts. Very inefficient, but functional.

It completes several simple cases of my own devising and both of the given test cases correctly.

Full program with test scaffold and some comments

#include <stdio.h>
#include <stdlib.h>
typedef struct n N;
struct n{
  int x,y;
  N*n;
};
N*I(int x,int y,N*l){ /* Return pointer to node x,y in l or NULL */
  if(!l)goto z;
  N*m=l;
  do{
    if((m->x==x)&&(m->y==y)){
      return m;
    }
    m=m->n;
  }while(m!=l);
 z:return NULL;
}; 
N*A(N*n,N*l){ /* Add node n to list l. Return the new l */
  if(!l){
    n->n=n;
    l=n;
  }else{
    n->n=l->n;
    l->n=n;
  }
  return l;
};
N*R(N*n,N*l){ /* Remove node n from list l. Return the new l */
  if(!l||(l==n&&n->n==n))goto z;
  N*m=l;
  do{
    if(m->n==n){m->n=n->n; return m;}
    m=m->n;
  }while(m!=l);
 z:return NULL;
}
int E(N*l){ /* Return the Enumberation of nodes in list l */
  int i=0;
  if(!l)goto z;
  N*m=l;
  do{++i;m=m->n;}while(m!=l);
 z:return i;
}
int C(N*l){ /* return true if all nodes in list l are connected */
  N*c=NULL,*n=l,*m=l=R(n,l); /* put the first node in the connected
                            list, and mark the start of the
                            working list */
  c=A(n,c);
  int a=E(l)*E(l); /* maximum number of times to try to place nodes */
  do {
    if (!l) return 1; /* when l is empty: we win! */
    n=m->n; 
    if ( I(m->x-1,m->y  ,c) ||
     I(m->x+1,m->y  ,c) ||
     I(m->x  ,m->y-1,c) ||
     I(m->x  ,m->y+1,c) ) l=R(m,l), c=A(m,c);
    m=n;
  } while (--a);
  return 0;
}
void P(N*l){ /* Print the list */
  printf("List: [");
  if(!l)goto z;
  N*m=l;
  do{printf(" (%d, %d)",m->x,m->y);m=m->n;}while(m!=l);
 z:printf(" ]\n");
}
N*G(int x,int y){ /* generate a new node with (x, y) */
  N*n;
  if(n=malloc(sizeof(N)))n->x=x,n->y=y;
  return n;
}
int main(){
  N*n,*l=NULL;

  n=G(0,0); l=A(n,l);
  n=G(1,0); l=A(n,l);
  n=G(2,0); l=A(n,l);
  n=G(0,1); l=A(n,l);
  n=G(0,2); l=A(n,l);
  n=G(2,2); l=A(n,l);
  n=G(3,2); l=A(n,l);
  n=G(4,2); l=A(n,l);
  n=G(0,3); l=A(n,l);

  n=G(4,3); l=A(n,l);
  n=G(0,4); l=A(n,l);
  n=G(1,4); l=A(n,l);
  n=G(2,4); l=A(n,l);
  n=G(4,4); l=A(n,l);
  n=G(4,5); l=A(n,l);
  n=G(2,6); l=A(n,l);
  n=G(3,6); l=A(n,l);
  n=G(4,6); l=A(n,l);

  P(l);
  if (C(l)) {
    printf("Connected!\n");
  } else {
    printf("Not connected.\n");
  };
}

Answer 2

Ruby - 82

c=->s{(a=->x,y{a[x,y-1]&a[x+1,y]&a[x,y+1]&a[x-1,y]if s.delete [x,y];s})[*s[0]][0]}

Ungolfed:

def c(s)
        a=->x,y{
            if s.delete([x,y])
                a[x,y-1]
                a[x+1,y]
                a[x,y+1]
                a[x-1,y]
            end
        }
        x,y=s.first
        a[x,y]
        s.size != 0
end

Usage:

print s([ [0,0],[2,0],[3,0],[3,1],[3,2],[2,2],[1,2],
    [0,2],[0,3],[0,4],[1,4],[2,4],[3,4]
]) ? "NO" : "YES"

Answer 3

Prolog - 118

c([_]).
c([[X,Y]|L]):-member([A,B],[[X+1,Y],[X-1,Y],[X,Y+1],[X,Y-1]]),C is A,D is B,select([C,D],L,N),c([[C,D]|N]),!.

Usage:

?- c([[0,0],[1,0],[2,0],[3,0],[3,1],[3,2],[2,2],[1,2],[0,2],[0,3],[0,4],[1,4],[2,4],[3,4]]).
true.

?- c([[0,0],[1,0],[2,0],[0,1],[0,2],[2,2],[3,2],[4,2],[0,3],[4,3],[0,4],[1,4],[2,4],[4,4],[4,5],[2,6],[3,6],[4,6]]).
false.

Answer 4

My first python version (loosely) translated into golfscript. Urgh. 80 chars.

{1$!!1$!!&{(~:v;:u;[1u+v u 1v+u 1- v u v 1-]2/@.@&.@\-\@|g}{;!}if}:g;{([.;]g}:f;

test cases:

# test cases
[[0 0] [1 0] [2 0] [3 0] [3 1] [3 2] [2 2] [1 2] [0 2] [0 3] [0 4] [1 4] [2 4] [3 4]]:a0;
[[0 0] [1 0] [2 0] [0 1] [0 2] [2 2] [3 2] [4 2] [0 3] [4 3] [0 4] [1 4] [2 4] [4 4] [4 5] [2 6] [3 6] [4 6]]:a1;
a0 f p
a1 f p

python 2.6; second attempt

def f(a):
    a = set(a)
    e = lambda (x, y) : set([(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)])
    p = lambda k : a.discard(k) or map(p, e(k) & a)
    p(a.pop())
    return not a

python 2.6; first attempt

def f(a):
    a = set(a)
    e = lambda (x, y) : set([(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]) 
    b = set([a.pop()])
    while b and a:
        c = a & e(b.pop())
        a -= c
        b |= c
    return not a

usage:

a_0 = [
    (0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),
    (1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)
]
a_1 = [
    (0,0),(1,0),(2,0),(0,1),(0,2),(2,2),(3,2),(4,2),(0,3),
    (4,3),(0,4),(1,4),(2,4),(4,4),(4,5),(2,6),(3,6),(4,6)
]
for a in (a_0, a_1):
    print 'YES' if f(a) else 'NO'

Answer 5

Perl, 130 133

A simple mark-and-sweep depth-first traversal, made much longer than I'd like by Perl sigils.

sub g{my($a,$b)=@_;g($a-1,$b),g(
$a+1,$b),g($a,$b-1),g($a,$b+1)if
delete$m{$a,$b}}sub f{($a,$b)=@_;
$m{pop,pop}++while@_;g$a,$b;!%m}

Sample use:

say f( (0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),
       (1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4) )
  ? 'YES' : 'NO';
say f( (0,0),(1,0),(2,0),(0,1),(0,2),(2,2),(3,2),(4,2),(0,3),
       (4,3),(0,4),(1,4),(2,4),(4,4),(4,5),(2,6),(3,6),(4,6) )
  ? 'YES' : 'NO';

Answer 6

Perl - 150

sub f{$m[pop][pop]++while@_;for$i(0..@m){for$j(0..9){$_.=$m[$i][$j]||0}$_.="3"}s/1/2/;for$n(0..99){s/(?<=2)1|1(?=2)|1(?=.{10}2)|(?<=2.{10})1/2/}!m/1/}

Works for 10 columns. For more I'd need another character.

Expands the color of one square a lot of times with one regex. Building the string takes a lot more space than I'd like it to.

Ungolfed:

sub f{
    $m[pop][pop]++ while @_;
    for $i (0..@m) {
        for $j (0..9) {
            $_ .= $m[$i][$j] || 0
        }
        $_ .= "3";
    }
    s/1/2/;
    for$n(0..99) {
        s/(?<=2)1|1(?=2)|1(?=.{10}2)|(?<=2.{10})1/2/
    }
    !m/1/
}

print f((0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2), (1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)) ? YES : NO;

Answer 7

Haskell 98, 98

g p@(x,y)z|elem p z=foldr g(filter(/=p)z)[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]|0<1=z
f z=null$g(z!!0)z

Sample use:

*Main> f [(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),
          (1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)]
True
*Main> f [(0,0),(1,0),(2,0),(0,1),(0,2),(2,2),(3,2),(4,2),(0,3),
          (4,3),(0,4),(1,4),(2,4),(4,4),(4,5),(2,6),(3,6),(4,6)]
False

Answer 8

Sage: 55 53 char

graphs.GridGraph([100]*2).subgraph(x).is_connected()

Where x is a list of coordinates,

x=[(0,0),(1,0),(2,0),(3,0),(3,1),(3,2),(2,2),(1,2),(0,2),(0,3),(0,4),(1,4),(2,4),(3,4)]