sicp exercise 3.19

; Exercise 3.19.  Redo exercise 3.18 using an algorithm that takes only a constant amount of space. (This requires a very clever idea.)
;
;

; The clever idea is Floyd's "Hare and Tortoise Algorithm"
; Floyd's cycle-finding algorithm, also known as the Tortoise and the Hare, detects a cycle in a list by using two iterators, a slow iterator ("tortoise") that walks the list one element at the time, and a fast iterator ("hare") that walks it two at a time. If there is a cycle, at some point the hare will overtake the tortoise; if there is no cycle, the hare gets to the end of the list first.

; I have used two "pointer", 'hare' and 'tort' and using set! to modify their value. I guess this is the way to go about the solution, as the problem requires constant amount of space to be used.

(define (detect-loop lsta)
  (let ((hare lsta) (tort lsta))
    (define (loop)
      (set! hare (cdr hare))
      (if (null? hare) #f                    ; hare reaches the end... no loop
         (if (eq? hare tort) #t              ; hare overtakes the tort... loop
           (begin (set! hare (cdr hare))
            (if (null? hare) #f              ; hare reaches the end... no loop
              (if (eq? hare tort) #t         ; hare overtakes the tort... loop
                (begin (set! tort (cdr tort))
                 (loop))))))))
    (loop)))


(define part1 (list 1 2 3 4))
(define part2 (list 9 8 7 6))

; no loop till now
(display (detect-loop part1))(newline)
(display (detect-loop part2))(newline)

; join the two parts
(set-cdr! (last-pair part1) part2)
; make a loop
(set-cdr! (last-pair part2) part2)

(display part1) (newline)

(display (detect-loop part1))(newline)
(display (detect-loop part2))(newline)