Re: connected?

On Tue, 17 Feb 2004, David Van Horn wrote:

> I think the only difference between our two algorithms is that the set I
> accumulate is connected throughout the process, whereas yours may not be.
>
> (define (connected? s)
>   (if (<= (length s) 1) #t
>       (lset= equal? s
>              (append-map
>               (lambda (x) (filter (lambda (y) (touching? x y)) s))
>               s))))
>
> This is probably much more effecient than mine.  You do only one lset=
> operation, I do one on each iteration.
>
> Maybe you could post your gawk version for comparison to that. ;)

-1 Not generalized.
-1 Not using set theory.
-1 Not elegant.
-1 Takes 5 times as many lines of code.
-1 Written in Awk.

### edges_continuous(pieces, n_edges, edge, n_pieces)
 # Start at some piece in pieces, color each connected piece, then
 # iterate through all pieces making sure it has been colored.
 ##
function edges_continuous(pieces, n_edges, edge, n_pieces,     colored,
                          i, piece)
{
  if (n_pieces <= 1) {
    ## Only one or less pieces.
    return TRUE;
  } ## else
  piece = pieces[1];
  color_connected_to(colored, n_edges, edge, piece);
  for (i = 1; i <= n_pieces; i++) {
    piece = pieces[i];
    if (!(piece in colored)) {
      ## There was a piece not colored.
      return FALSE;
    }
  }
  ## Every piece visited was colored, so:
  return TRUE;
}

### color_connected_to(colored, n_edges, edge, piece)
 # Mark current piece as colored (set equal to 1).
 # For all edges of current piece that aren't already colored, color
 # pieces to which it is connected.
 ##
function color_connected_to(colored, n_edges, edge, piece,    i, next_piece)
{
  colored[piece] = 1;
  for (i = 1; i <= n_edges[piece]; i++) {
    next_piece = edge[i, piece];
    if (!(next_piece in colored)) { ## if this piece isn't already colored
      color_connected_to(colored, n_edges, edge, edge[i, piece]);
      ## "I lost my eye-piece!" -- 2004.02.16 12:41 AM
    }
  }
}

> > Couldn't both our approaches benefit just by finding the connected set C
> > of any element and seeing if this set is the same as the original set S.
> > This could be done by comparing the sizeof(S) == sizeof(C).
>
> Yes, but for me, using lists as a set datastructure, the sizeof operation is
> not trivial (not that lset= is either) (nor is sizeof actually part of the
> library).  It's not just the list length operation, which is linear in the
> size of the list.  List length doesn't work since (= (length '(1 1)) (length
> '(1))) is false, but the sets are of the same size.

Awk doesn't have sizeof either, but this is where I can use dirty little
counters while i'm iterating over my dirty little data structures in the
dirty little language i implemented in.

On Tue, 17 Feb 2004, Jon wrote:

> is this in relation to the checkers contest this past weekend?

speaking of which, my analogous Awk version of the between? predicate had
a bug resulting in infinite recursion when the distance between the
locations was odd but greater than 1 (a very common and realistic
situation).  bummer.

so I wouldn't bother installing Gawk or testing my solution, David.
unless you want to wait awhile.
i guess this is where the contest's 1-minute runtime limit comes in handy.
/a