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.

Keith Randall

Posted 2011-02-10T07:21:35.447

Reputation: 19 865

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

Answers

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"

Arnaud Le Blanc

Posted 2011-02-10T07:21:35.447

Reputation: 2 286

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

dmckee --- ex-moderator kitten

Posted 2011-02-10T07:21:35.447

Reputation: 2 726

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'

roobs

Posted 2011-02-10T07:21:35.447

Reputation: 299

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

J B

Posted 2011-02-10T07:21:35.447

Reputation: 9 638

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.

gusbro

Posted 2011-02-10T07:21:35.447

Reputation: 131

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)]

boothby

Posted 2011-02-10T07:21:35.447

Reputation: 9 038

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;

user475

Posted 2011-02-10T07:21:35.447

Reputation:

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

J B

Posted 2011-02-10T07:21:35.447

Reputation: 9 638