Re: [racket-users] Long division algorithm in HtDP way

```I couldn’t help myself. So here is 90% of what John proposed in HtDP’s ISL+
language. Exercise for the reader: fix the failing tests. ```
```

#lang htdp/isl+

;; long division

;; Trace = [cons N [cons N [Listof [List N N]]]

;; N N -> Trace
;; compute the trace for the division of x and y

;; example, worked
;; 5432 : 12 = 452
;;-48
;;--
;;  63
;; -60
;;  --
;;   32
;;  -24
;;   --
;;    8
;;    =

(check-expect (long 5432 12) (list 452 8 (list 54 48) (list 32 24)))
(define (long x y)
(local ((define x-as-digits (number->digits x))
(define result      (long-helper (list (first x-as-digits)) (rest
x-as-digits) y))
(define quotient    (digits->number (first result))))
(list quotient (second result))))

;; [Listof Digit] [Listof Digit] N -> Trace
;; compute the trace of a long division of (digits->number (append fst-digits
rest-digits)) by y
(check-expect (long-helper '(5) '(4 3 2) 12) (list 452 8 (list 54 48) (list 32
24)))
(define (long-helper fst-digits rest-digits y)
(local ((define fst-number (digits->number fst-digits)))
(cond
[(< fst-number y)
(if (empty? rest-digits)
(list '() fst-number)
(long-helper (snoc fst-digits (first rest-digits)) (rest rest-digits)
y))]
[(= fst-number y) (list (list 1) 0)]
[else (local ((define next-digit (subtract-often-enough fst-number y))
(define remainder  (- fst-number (* next-digit y)))
(define result     (long-helper (list remainder) rest-digits
y))
(define quotient   (first result))
(define remainder2 (second result)))
(list (cons next-digit quotient) remainder2))])))

;; N N -> [List N N]
;; subtract y from x until x < y
(check-expect (subtract-often-enough 54 12) 4)
(define (subtract-often-enough x y)
(cond
[(< x y) 0]
[else (+ (subtract-often-enough (- x y) y) 1)]))

;; [Listof X] X -> [Listof X]
;; add x to end of l
(check-expect (snoc '() 1) '(1))
(check-expect (snoc '(1) 2) '(1 2))
(define (snoc l x)
(append l (list x)))

;; [listof Digit] -> N
;; render the given sequence of digits as a number
(check-expect (digits->number '(1 2 3)) 123)
(define (digits->number digits)
(string->number (implode (map number->string digits))))

;; N -> [Listof Digit]
;; split number into sequence of digits
(check-expect (number->digits 123) '(1 2 3))
(define (number->digits x)
(map string->number (explode (number->string x))))

--
You received this message because you are subscribed to the Google Groups
"Racket Users" group.
To unsubscribe from this group and stop receiving emails from it, send an email