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

[Matthias Felleisen]

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 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

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

[Matthias Felleisen]

Let me support John’s email with a hint: 

#lang htdp/isl+

;; long division

;; Number Number -> (cons Number (cons Number [Listof Number]))
;; compute the list of steps needed to divide x by y

;; work thru an example
;; given  5432, 12
;; wanted [list 452 8) ... optional: (list 54 48) (list 63 60) (list 32 24)]
;; because 
;; (quotient 5432 12) = 12
;; (remainder 5432 12) = 8
;; IGNORE the trace part 

(define (long x y)
  (cond
[(< x y) (list 0 x)]
[(= y x) (list 1 0)]
[else (local ((define r (long (- x y) y))
  (define quotient  (first r))
  (define remainder (second r)))
(list (+ quotient 1) remainder))]))

(long 5432 12)




> On Sep 7, 2017, at 2:09 PM, 'John Clements' via Racket Users 
>  wrote:
> 
> 
>> On Sep 7, 2017, at 9:28 AM, jaroslaw.mo...@gmail.com wrote:
>> 
>> 
>> Dear Racketeers!
>> 
>> I would like to write the function divide in racket, for performing the long 
>> division, which would print the whole computational process, as the 
>> elementary school pupils do. For example, the call (divide 5432, 12) should 
>> print this:
>> 
>> 5432 : 12 = 452
>> -48
>> --
>> 63
>> -60
>> --
>>  32
>> -24
>>  --
>>   8
>>   =
> 
> Sounds like fun! 
> 
> If I were you, I would separate this into two problems.
> 
> 1) given the divisor and the divisee, produce a “trace” of the division.
> 2) given a “trace”, produce a (single multi-line) string representing it.
> 
> Most of the thinking will be in developing the data definition for the 
> “trace. ” Once this is done, the rest should be pretty straightforward.
> 
> John Clements
> 
> -- 
> 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 to racket-users+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

-- 
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 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[racket-users] Long division algorithm in HtDP way

[jaroslaw . modry]

Dear Racketeers!

I would like to write the function divide in racket, for performing the long 
division, which would print the whole computational process, as the elementary 
school pupils do. For example, the call (divide 5432, 12) should print this:

 5432 : 12 = 452
-48
 --
  63
 -60
  --
   32
  -24
   --
8
=


Finally, I wrote this function in python, but I'm not happy about it because 
I've been "tinkering around" and I feel that it can be much better written by 
following the principles described in HtDP. The problem is I don't know how to 
do that, though I read the book and solved a lot of problems from it. I simply 
don't know how to "derive" clean and nice program for this function.

My (ugly) python code looks like this:

def divide(x, y):
if x < y:
return 0, x
x = str(x)
q = ""
r = ""
workings = ""
firsttime = True
for i in range(1, len(x) + 1):
r = r + "0"
num = int(r) + int(x[i-1])
sum = 0
m = 0
while sum + y <= num:
m += 1
sum += y
r = str(num - sum)
q = q + str(m)
ls = len(str(sum))
if sum == 0 and firsttime:
continue
firsttime = False
workings += (i-ls)* " " + "-" + str(sum) + "\n"
workings += (i + 1 -ls) * " " + ls * "-" + "\n"
workings += (i + 1 - len(r)) * " " + r + ("" if i >= len(x) else x[i]) 
+ "\n"

workings += (len(x) - len(r) + 1) * " " + len(r) * "=" + "\n"
print(" " + x + " : " + str(y) + " = " + str(int(q)) + "\n" + workings)


I'm wondering how to write nice and clean version of the above program in the 
proper HtDP way. Can someone here show how to solve this problem strictly 
following the HtDP methodology?

Nice regards,
Jaroslaw Modry

-- 
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 
to racket-users+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.