105 lines
3.6 KiB
Racket
105 lines
3.6 KiB
Racket
#lang pl
|
|
|
|
; I'm keeping my own type declarations in bc the racket ones are literally unreadable.
|
|
; gcd2: a: Int, b: Int → Int
|
|
(: gcd2 : (Integer Integer -> Integer))
|
|
; Given two non-negative integers, determine their greatest common divisor.
|
|
(define (gcd2 a b)
|
|
(cond
|
|
[(or (negative? a) (negative? b)) (error 'neg "Given negative number.")]
|
|
[(= a 0) b]
|
|
[(= b 0) a]
|
|
[(and (even? a) (even? b)) (* 2 (gcd2 (floor (/ a 2)) (floor (/ b 2))))]
|
|
[(even? b) (gcd2 a (floor (/ b 2)))]
|
|
[(even? a) (gcd2 (floor (/ a 2)) b)]
|
|
[else (if (<= a b)
|
|
(gcd2 a (- b a))
|
|
(gcd2 b (- a b)))]))
|
|
|
|
(test (gcd2 0 0) => 0)
|
|
(test (gcd2 288 64) => 32)
|
|
; What's the point of the symbol in the error definition if it isn't even used to compare errors?
|
|
(test (gcd2 2 -1) =error> "Given negative number.")
|
|
|
|
; out-of-bounds?: start: Number,
|
|
; lower: Number,
|
|
; upper: Number,
|
|
; l: [Number] → Bool
|
|
(: out-of-bounds? : (Number Number Number (Listof Number) -> Boolean))
|
|
; Determines if an object that begins at the starting location and then moves delta by delta ever ever steps outside of the bounds (inclusive).
|
|
(define (out-of-bounds? start lower upper l)
|
|
(if (or (< start lower) (> start upper))
|
|
#t
|
|
(match l
|
|
['() #f]
|
|
[(cons frst rst) (out-of-bounds? frst lower upper rst)])))
|
|
|
|
(test (out-of-bounds? 0 -1 2 '(0 -2 3 -4 6)) => #t)
|
|
(test (out-of-bounds? 0 -1 1 '(1)) => #f)
|
|
(test (out-of-bounds? 0 -1 1 '()) => #f)
|
|
(test (out-of-bounds? 0 1 2 '()) => #t)
|
|
(test (out-of-bounds? 0 0 0 '()) => #f)
|
|
|
|
; A binary tree.
|
|
(define-type BT
|
|
[Node Number BT BT]
|
|
[End '()]) ; Couldn't figure out a better way to do this.
|
|
(define end (End '()))
|
|
|
|
(define sprout (Node 0 end end))
|
|
(define seedling (Node 5 sprout (Node 6 end end)))
|
|
(define sapling (Node 10
|
|
(Node 6 sprout end)
|
|
(Node 12 end end)))
|
|
(define deeply-broke-tree
|
|
(Node 10
|
|
(Node 6 end (Node 11 end end))
|
|
(Node 12 end end)))
|
|
|
|
; <2: U{Num, Sym}, Num, U{Num, Sym} → Bool
|
|
(: <2 : ((U Number Symbol) Number (U Number Symbol) -> Boolean))
|
|
; Convenient form of greater than. Slightly hack.
|
|
(define (<2 a b c)
|
|
(cond [(and (symbol? a) (symbol? c)) #t]
|
|
[(symbol? a) (< b c)]
|
|
[(symbol? c) (< a b)]
|
|
[else (< a b c)]))
|
|
|
|
; recurse: t: Tree, lower: U{Num, Sym}, upper: U{Num, Sym} → Bool
|
|
(: good-bt?r : (BT (U Number Symbol) (U Number Symbol) -> Boolean))
|
|
; Recursively checks left & right with lower & upper bounds.
|
|
(define (good-bt?r t lower upper)
|
|
(cases t
|
|
[(Node n t1 t2) (and (<2 lower n upper)
|
|
(good-bt?r t1 lower n)
|
|
(good-bt?r t2 n upper))]
|
|
[(End what) #t]))
|
|
|
|
; good-bt?: t BT → Bool
|
|
(: good-bt? : (BT -> Boolean))
|
|
; Determine whether bt is good.
|
|
(define (good-bt? t)
|
|
(good-bt?r t 'quite-little 'very-big))
|
|
|
|
(test (good-bt? sprout) => #t)
|
|
(test (good-bt? sapling) => #t)
|
|
(test (good-bt? deeply-broke-tree) => #f)
|
|
|
|
; goodies/help: l: [A], i: Index, a: [Index] → [Index]
|
|
(: goodies/help : (All(A) (A -> Boolean) (Listof A) Number (Listof Number) -> (Listof Number)))
|
|
(define (goodies/help good? l i a)
|
|
(match l
|
|
['() (reverse a)]
|
|
[(cons f r) (if (good? f)
|
|
(goodies/help good? r (add1 i) (cons i a))
|
|
(goodies/help good? r (add1 i) a))]))
|
|
|
|
; goodies: good?: (A → Boolean), l: [A] → [Index]
|
|
(: goodies : (All(A) (A -> Boolean) (Listof A) -> (Listof Number)))
|
|
; Returns a list of indices considered "good."
|
|
(define (goodies good? l)
|
|
(goodies/help good? l 0 '()))
|
|
|
|
(test (goodies even? '(1 2 3 4 5)) => '(1 3))
|
|
(test (goodies even? '()) => '())
|