← Back to branch summary

~rhcarvalho/+junk/racket

« back to all changes in this revision

Viewing changes to project-euler-17.rkt

  • Committer: Rodolfo Carvalho
  • Date: 2011-07-25 07:43:24 UTC
  • Revision ID: rhcarvalho@gmail.com-20110725074324-v3u7e2kt0v3u55mc
Add summation solution

Show diffs side-by-side

added added

removed removed

Lines of Context:
project-euler-17.rkt
1
 
#lang racket
 
1
#lang racket/base
2
2
;; This code solves Problem 17 from Project Euler
3
3
;; http://projecteuler.net/index.php?section=problems&id=17
4
4
;;
15
15
;; Rodolfo Carvalho, 2011/07/24
16
16
 
17
17
(require (planet williams/describe/describe)
 
18
         (planet stephanh/mathsymbols/mathsymbols)
18
19
         plot
19
20
         slideshow)
20
21
 
26
27
(define (slim-letter-count-of-integers-up-to n)
27
28
  (for/fold ([sum 0])
28
29
    ([i (in-range 1 (add1 n))])
29
 
    (+ sum ((compose string-length integer->string) i))))
 
30
    (+ sum (string-length (integer->string i)))))
 
31
 
 
32
; Solve using summation
 
33
(define (greek-letter-count-of-integers-up-to n)
 
34
  (Σ ([i (in-range 1 (add1 n))])
 
35
     (string-length (integer->string i))))
30
36
 
31
37
; Solve recursively
32
38
(define (recur-letter-count-of-integers-up-to n)
61
67
  (list-ref (sort lst <) (ceiling (/ (length lst) 2))))
62
68
 
63
69
(define (generate-data f)
64
 
  (let* ([min 1000]
65
 
         [max 100000]
66
 
         [points# 10]
67
 
         [repeat# 7])
68
 
    (for/list ([n (in-range min (add1 max) (/ (- max min) (sub1 points#)))])
69
 
      (list n
70
 
            (apply map (λ elms
71
 
                         (if (list? (car elms))
72
 
                             (car elms)
73
 
                             (median elms)))
74
 
                   (for/list ([i (in-range repeat#)])
75
 
                     (call-with-time f n)))))))
 
70
  (displayln (format "Generating data for ~a" f))
 
71
  (time
 
72
   (let* ([min 1000]
 
73
          [max 100000]
 
74
          [points# 10]
 
75
          [repeat# 7])
 
76
     (for/list ([n (in-range min (add1 max) (/ (- max min) (sub1 points#)))])
 
77
       (list n
 
78
             (apply map (λ elms
 
79
                          (if (list? (car elms))
 
80
                              (car elms)
 
81
                              (median elms)))
 
82
                    (for/list ([i (in-range repeat#)])
 
83
                      (call-with-time f n))))))))
76
84
 
77
85
; TODO: "datum" should be a struct and all these below would come for free
78
86
(define (datum-n datum)
127
135
 
128
136
(let ([slim-data (generate-data slim-letter-count-of-integers-up-to)]
129
137
      [fat-data (generate-data fat-letter-count-of-integers-up-to)]
 
138
      [greek-data (generate-data greek-letter-count-of-integers-up-to)]
130
139
      [recur-data (generate-data recur-letter-count-of-integers-up-to)]
131
140
      [tail-data (generate-data tail-letter-count-of-integers-up-to)]
132
141
      [let-data (generate-data let-letter-count-of-integers-up-to)])
133
142
  (for ([title (list "number of letters used" "CPU time" "Real time" "GC time")]
134
143
        [y-max (find-max-value slim-data
135
144
                               fat-data
 
145
                               greek-data
136
146
                               recur-data
137
147
                               tail-data
138
148
                               let-data)]
139
149
        [getter (list datum-result datum-cpu-time datum-real-time datum-gc-time)])
140
150
    (let ([slim-points (data->points slim-data getter 'blue)]
141
151
          [fat-points (data->points fat-data getter 'red)]
 
152
          [greek-points (data->points greek-data getter 'yellow)]
142
153
          [recur-points (data->points recur-data getter 'green)]
143
154
          [tail-points (data->points tail-data getter 'violet)]
144
155
          [let-points (data->points let-data getter 'turquoise)])
146
157
       #:title (format "~a" title)
147
158
       (frame
148
159
        (inset
149
 
         (table 6
 
160
         (table 7
150
161
                (append
151
162
                 (list (t "N")
152
163
                       (colorize (t "slim") "blue")
153
164
                       (colorize (t "fat") "red")
 
165
                       (colorize (t "greek") "yellow")
154
166
                       (colorize (t "recur") "green")
155
167
                       (colorize (t "tail") "violet")
156
168
                       (colorize (t "let") "turquoise"))
159
171
                       (make-data-table getter
160
172
                                        slim-data
161
173
                                        fat-data
 
174
                                        greek-data
162
175
                                        recur-data
163
176
                                        tail-data
164
177
                                        let-data))))
171
184
         (mix
172
185
          slim-points
173
186
          fat-points
 
187
          greek-points
174
188
          recur-points
175
189
          tail-points
176
190
          let-points)
184
198
         #:y-label title
185
199
         #:title (format "~a x N" title)))))))
186
200
 
187
 
(displayln "Enjoy the slides!")
 
 
b'\\ No newline at end of file'
 
201
(displayln "Enjoy the slides!")