Extra Credit from the final

[ Follow Ups ] [ Post Followup ] [ WWWBoard for 308-203A ] [ FAQ ]

Posted by William Renner on December 16, 19100 at 17:39:30:

The algorithm is breadth-first search.

First argument: a string giving an edge set, e.g.

"abbcca" => { (a,b), (b,c), (c,a) }

Second argument an initial queue: e.g. "b"

When you call bar(), the breadth-first search is performed
by cutting out some edges from the graph (marked by '*'), and
then creating a new Foo object with the smaller graph and an
updated queue.

Since the two vertices in an edge are at positions n and n+1 in
the string, n being an even number, the binary operations & and ^
are handy to access these things:

charAt(x ^ 1) will be the other vertex of interest, whether x is
even or odd

charAt(x & 1) will be the first of the two vertices in the edge,
where again x can be even or odd

There's a runnable version of this little monstrosity accessible from
the course homepage.

Happy holidays,


Follow Ups:

Post a Followup




Optional Link URL:
Link Title:
Optional Image URL:

[ Follow Ups ] [ Post Followup ] [ WWWBoard for 308-203A ] [ FAQ ]