[racket] a small programming exercise

From: Matthias Felleisen (matthias at ccs.neu.edu)
Date: Thu Oct 14 12:29:51 EDT 2010


Thanks for setting my head straight! 

I ran this stress test for your 5 line solution and mine: 

> (define *the-list* (build-list 10000000 (lambda (i) (random (+ i 1)))))
> (time (______ *the-list*))

For small benchmarks, your solution may take twice as long as my 8 line ASL solution, 
but for something of the above size -- there can't be that many lakes in MN -- it takes
almost the same time. 

In short, don't be afraid of 10 iterations over long lists, and don't bother with 
hash tables and fancy algorithmics until you know you need it -- by measuring. 

I used to believe this but have temporarily forgotten this lesson due to external influences. 

-- Matthias




On Oct 14, 2010, at 12:09 PM, Nadeem Abdul Hamid wrote:

> Here's a solution in ISL:
> 
> ;; benson : [listof positive-number] -> [listof (list number number)]
> (define (benson a-lon)
>  (let ([digs (map (compose
>                    string->number first explode number->string
> exact->inexact) a-lon)])
>    (build-list 10
>                (λ(i) (list i
>                            (/ (length (filter (λ(d) (= i d)) digs))
>                               (length digs)))))))
> 
> 
> ;; TESTS (matthias' and jay's, modified)
> 
> (require racket)   ; (only-in ... for/list)
> 
> (check-expect (filter (lambda (p) (not (zero? (second p))))
>                      (benson '(123 124 125 126 23 24 31)))
>              (list (list 1 4/7) (list 2 2/7) (list 3 1/7)))
> 
> (check-expect
> (benson (list 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.10
>            11 12 13 14 15 16 17 18 19
>            21 22 23 24 25 26 27 28
>            31 32 33 34 35 36 37
>            41 42 43 44 45 46
>            51 52 54 54 55
>            61 62 63 64
>            71 72 73
>            81 82
>            91))
> (for/list ([i (in-range 10)])
>   (list i
>         (/ (- 10 i)
>            (+ 10 9 8 7 6 5 4 3 2 1))))
> )
> 
> 
> 
> 
> On Thu, Oct 14, 2010 at 11:30 AM, Matthias Felleisen
> <matthias at ccs.neu.edu> wrote:
>> 
>> 
>> I love this solution but let me supply a solution in ASL, the teaching language:
>> 
>> 
>> ;; ASL
>> (require racket) ; (only-in ... hash->list)
>> ;; I could have used the key for sort to get around the second lambda
>> 
>> ;; [Listof String] -> [Listof (cons Digit Nat)]
>> ;; compute a frequency count of the leading digit in the number of lon
>> ;; assume: the digits are positive
>> (define (collect lon)
>>  (local ((define loch (map (compose string->list number->string) lon))
>>          (define (upd c H) (hash-set H c (+ (hash-ref H c 0) 1)))
>>          (define hash (foldl (lambda (x H) (upd (first x) H)) #hash() loch))
>>          (define loh# (hash->list hash))
>>          (define srtd (sort loh# (lambda (l r) (> (cdr l) (cdr r))))))
>>    (map (lambda (x) (cons (string->number (string (car x))) (cdr x))) srtd)))
>> 
>> (check-expect (collect '(123 124 125 126 23 24 31))
>>              (list (cons 1 4) (cons 2 2) (cons 3 1)))
>> 
>> 
>> If actual I/O is required, I'd use batch-io to read CSV files and
>> display the list above in a batch action.
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://lists.racket-lang.org/listinfo/users
>> 
> 
> 
> 
> -- 
> Nadeem Abdul Hamid
> Associate Professor, Computer Science
> Berry College
> PO Box 5014
> 2277 Martha Berry Hwy NW
> Mount Berry, GA 30149-5014
> (706) 368-5632
> http://cs.berry.edu/~nhamid/



Posted on the users mailing list.