Arc Forumnew | comments | leaders | submitlogin
2 points by rocketnia 4458 days ago | link | parent

"The key difficulty is that there's two dimensions, so does the number of hares double each iteration?"

Hmm. As the tortoise goes down branches, its location becomes indeterminate. As the hare goes down branches, its location becomes indeterminate relative to the tortoise, so we might need multiple hare markers per branch if we're doing a tortoise-directed search. If we try using the hare to direct the search instead, then we may still need to keep a growing history of hare locations on each branch so the tortoise can follow.

Either way, keeping a hash table sounds more straightforward to me.

Are you using this algorithm properly? I haven't seen any of your example code do a second pass to find out where the cycle begins and what its period is. But maybe you don't need to...?



1 point by akkartik 4458 days ago | link

I'm just taking a constant-factor hit :) A few extra iterations doesn't change the result for either print or iso. And for cycles that loop back all the way to the start it turns out there's zero overhead.

  x <- '(1 2 3)
  lastcdr.x <- x  # 1 2 3 1 2 3 1 ...
  print x
  1
  2
  3
  ...  # exactly one iteration
But:

  x <- '(1 2 3)
  lastcdr.x <- cdr.x   # 1 2 3 2 3 2 3 ...
  print x
  1
  2
  ...

-----

2 points by rocketnia 4458 days ago | link

  You posted:
  
  x <- '(1 2 3)
  lastcdr.x <- cdr.x   # 1 2 3 2 3 2 3 ...
  print x
  1
  2
  ...
Is that the behavior you expect? I would expect "1 2 3 ...", but it looks like the rabbit and the hare meet at the (3 ...) cons and stop.

  1 2 3 2 3 2 3
  *              Print "1".
    * *          Print "2".
      *   *      Print "...".

-----

1 point by akkartik 4458 days ago | link

Yeah I tried it out before posting. I had to take pains in iso to make sure we do one full traversal. With print I didn't care as much.

Update: Ack, I found a bug in iso (http://arclanguage.org/item?id=17365):

  x <- '(1 2 3)
  y <- '(1 2 4)
  (do1 nil (<- lastcdr.x x lastcdr.y y))  # Avoid printing the cycles
  (iso x y)   # not nil!

-----

2 points by rocketnia 4458 days ago | link

Here's a slightly different bug I found before your update. It's another case where I don't know what behavior you expect, but it probably isn't this. :-p

  (do (a <- '(1 2 3)) (lastcdr.a <- cdr.a) nil)
  => nil
  (do (b <- '(1 2 3 2 3)) (lastcdr.b <- cdr.b) nil)
  => nil
  (not+not+iso a b)
  => nil
  (not+not+iso b a)
  => 1
(I'm using not+not+iso so it returns a predictable value rather than an address.)

-----

1 point by rocketnia 4458 days ago | link

"the rabbit and the hare"

Whoops. I didn't mean that. XD

-----