Skip to content

Instantly share code, notes, and snippets.

@pera
Created May 8, 2018 23:18
Show Gist options
  • Save pera/fea285e298075c6f8ab9f16dd4eb660f to your computer and use it in GitHub Desktop.
Save pera/fea285e298075c6f8ab9f16dd4eb660f to your computer and use it in GitHub Desktop.
(define node cons)
(define node-left car)
(define node-right cdr)
(define (make d)
(if (= d 0)
(node #f #f)
(let ([d2 (1- d)])
(node (make d2) (make d2)))))
(define (check t)
(if (node-left t)
(+ 1 (check (node-left t)) (check (node-right t)))
1))
(define (main n)
(define min-depth 4)
(define max-depth (max (+ min-depth 2) n))
(define stretch-depth (1+ max-depth))
(format #t "stretch tree of depth ~a\t check: ~a\n" stretch-depth (check (make stretch-depth)))
(let ([long-lived-tree (make max-depth)])
(do ([d 4 (+ d 2)]) ([not (< d (1+ max-depth))])
(let ([iterations (ash 1 (+ (- max-depth d) min-depth))])
(format #t "~a\t trees of depth ~a\t check: ~a\n"
iterations
d
(let sum ([i iterations] [n 0])
(if (zero? i)
n
(sum (1- i) (+ n (check (make d)))))))))
(format #t "long lived tree of depth ~a\t check: ~a\n"
max-depth
(check long-lived-tree))))
(main (string->number (list-ref (command-line) 1)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment