8
\$\begingroup\$

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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ Are x,y non-negative? \$\endgroup\$
    – user475
    Commented Feb 10, 2011 at 14:12
  • 2
    \$\begingroup\$ What's the upper limit of x and y? \$\endgroup\$
    – user475
    Commented Feb 10, 2011 at 14:23

8 Answers 8

5
\$\begingroup\$

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");
  };
}
\$\endgroup\$
3
\$\begingroup\$

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"
\$\endgroup\$
0
3
\$\begingroup\$

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.
\$\endgroup\$
4
  • \$\begingroup\$ Why do you need the C is A,D is B? \$\endgroup\$
    – J B
    Commented Feb 10, 2011 at 23:19
  • \$\begingroup\$ Fails on c([[1,0],[0,0],[2,0]]). \$\endgroup\$
    – J B
    Commented Feb 10, 2011 at 23:24
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – gusbro
    Commented Feb 11, 2011 at 13:42
  • \$\begingroup\$ d'oh. Thanks. My prolog is getting rusty. \$\endgroup\$
    – J B
    Commented Feb 11, 2011 at 13:51
3
\$\begingroup\$

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'
\$\endgroup\$
1
  • 4
    \$\begingroup\$ Could you please keep to one language per answer? It's a bit hard to know what we're voting for now. \$\endgroup\$
    – J B
    Commented Feb 10, 2011 at 23:20
3
\$\begingroup\$

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';
\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can reduce this to 122: sub f{@c=@_;$m{pop,pop}++while@_;g@c;!%m} \$\endgroup\$
    – Timwi
    Commented Mar 25, 2011 at 1:46
2
\$\begingroup\$

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

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

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)]
\$\endgroup\$

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.