/
tree_loop.scm
65 lines (55 loc) · 1.7 KB
/
tree_loop.scm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
(define cnt 0)
(define (no-cycle?-aux tr tr2 fst)
(set! cnt (+ cnt 1))
(if (and (not fst) (eq? tr tr2) (not (null? tr)))
#f
(if (and (pair? tr2) (pair? tr))
(and
(if (pair? (car tr2))
(and
(no-cycle?-aux (car tr) (car (car tr2)) #f)
(no-cycle?-aux (cdr tr) (car (car tr2)) #f)
(no-cycle?-aux (car tr) (cdr (car tr2)) #f)
(no-cycle?-aux (cdr tr) (cdr (car tr2)) #f))
#t)
(if (pair? (cdr tr2))
(and
(no-cycle?-aux (car tr) (car (cdr tr2)) #f)
(no-cycle?-aux (cdr tr) (car (cdr tr2)) #f)
(no-cycle?-aux (car tr) (cdr (cdr tr2)) #f)
(no-cycle?-aux (cdr tr) (cdr (cdr tr2)) #f))
#t))
#t)))
(define (no-cycle? tr)
(no-cycle?-aux tr tr #t))
;; (print (no-cycle? '(a b x)))
;; (print (no-cycle? '((a b) x c)))
;; (define n '((a b) x c))
;; (set-cdr! (cdr (car n)) (car n))
;; (print (no-cycle? n))
;; (define m '(a (a b) x c))
;; (set-car! m m)
;; (print (no-cycle? n))
;; (print (no-cycle? '(1 (2 (3 4) ()) ())))
;; (print (no-cycle? '((a . #1=(c . d)) #1#)))
;; (print (no-cycle? '(#1=(a (b (c d) e) (f (g h) (i (j (k l) m)))
;; (n (o p) (q r)) s (t (u v) (w x (y z #1#)))))))
;; (print (no-cycle? '(#1=(a (b (c d) e) (f (g h) (i (j (k l) m)))
;; (n (o p) (q r)) s (t (u v) (w x (y z)))))))
(define (gen-line n c)
(if (> n 0)
(cons (gen-line (- n 1) c) c) c))
(print (gen-line 3 1))
(define (gen-tree-aux n m)
(if (> n 0)
(let ((c (gen-tree-aux (- n 1) m)))
(cons (gen-line m c) c))
(gen-line m 1)))
(define (gen-tree n) (gen-tree-aux n n))
(define (run n)
(if (> n 0) (let ()
(run (- n 1))
(no-cycle? (gen-tree n))
(print cnt)
(set! cnt 0))))
(run 25)