## Is this figure connected?

7

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.

1Are x,y non-negative? – None – 2011-02-10T14:12:07.833

1What's the upper limit of x and y? – None – 2011-02-10T14:23:46.310

3

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


5

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");
};
}


3

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'


4Could you please keep to one language per answer? It's a bit hard to know what we're voting for now. – J B – 2011-02-10T23:20:57.900

3

## 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';


1You can reduce this to 122: sub f{@c=@_;$m{pop,pop}++while@_;g@c;!%m} – Timwi – 2011-03-25T01:46:18.460 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.  Why do you need the C is A,D is B? – J B – 2011-02-10T23:19:43.017 Fails on c([[1,0],[0,0],[2,0]]). – J B – 2011-02-10T23:24:45.307 1@JB: you need the C is A, D is B to evaluate the new coordinates. Suppose you have A=X+1, then C is A evaluates X+1 to the actual value. – gusbro – 2011-02-11T13:42:59.630 d'oh. Thanks. My prolog is getting rusty. – J B – 2011-02-11T13:51:32.673 2 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)]  2 # 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;  2 ## 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