7
\$\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\$
  • 1
    \$\begingroup\$ Are x,y non-negative? \$\endgroup\$ – user475 Feb 10 '11 at 14:12
  • 1
    \$\begingroup\$ What's the upper limit of x and y? \$\endgroup\$ – user475 Feb 10 '11 at 14:23
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\$
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\$

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\$
  • \$\begingroup\$ Why do you need the C is A,D is B? \$\endgroup\$ – J B Feb 10 '11 at 23:19
  • \$\begingroup\$ Fails on c([[1,0],[0,0],[2,0]]). \$\endgroup\$ – J B Feb 10 '11 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 Feb 11 '11 at 13:42
  • \$\begingroup\$ d'oh. Thanks. My prolog is getting rusty. \$\endgroup\$ – J B Feb 11 '11 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\$
  • 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 Feb 10 '11 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
    \$\begingroup\$ You can reduce this to 122: sub f{@c=@_;$m{pop,pop}++while@_;g@c;!%m} \$\endgroup\$ – Timwi Mar 25 '11 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, privacy policy and cookie policy

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