josephoswaldgg@hotmail.com <josephoswald@gmail.com> wrote:
+---------------
| I don't want to post a homework solution, but the basic principle is
| clear: walk down both lists. When *any* of the lists comes to an end,
| unless *every other* list has come to an end at the same time, the
| lists are different lengths. As a bonus, one might return the length by
| counting on the way down.
+---------------
Yup. But...
+---------------
| I believe this can be extended even to cover the case when all lists
| are circular, using the standard trick to detect circularity in the
| list structure. I.e., if any list is detected to be circular, all must
| be circular.
+---------------
Unfortunately, it's not that simple. While what I think you meant
to say works as far as it goes -- that is, if any list is detected
to be circular, one can require that all other lists detect circularity
at the same step -- it still doesn't ensure that the lists are all
of the same "shape". For example, the following two lists are detected
as being equal in "length" and content by the naive tortoise & hare
algorithm [two-pointer trick]:
(0 0 0 0 0 0 0 0 0 . #1=(0 0 . #1#))
(0 0 0 0 0 0 . #1=(0 0 0 0 0 . #1#))
as are the following pair:
(0 1 2 3 4 2 3 4 . #1=(2 3 4 . #1#))
(0 1 . #1=(2 3 4 2 3 4 2 3 4 . #1#))
Yet both the initial prefix and the periodicity of the circular parts
of each pair of lists are different, though circularity is detected
at the same step and the same list items are compared at each step.
So if "shape" is not considered, each pair could be considered to be
in some sense "equal"; but if "shape" is important, they aren't.
Exercise for the reader: given two circular lists for which the
classical tortoise & hare algorithm declares circularity at the
same time, what else needs needs to be done to determine whether
the prefixes and/or the circular tails are/aren't of the same length?
[Hint: Google is your friend.]
-Rob
-----
Rob Warnock <rpw3@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607