Project Euler–Problem 1 solved with Scheme

It was time to brush up my Scheme and Algorithm skills. For some inspiring problems I went over to the Project Euler website.

Here is my first attempt in Scheme. I’m already working on a Streamed version of this solution which is far more efficient.

Another plan is to solve the same problem in Javascript and maybe some other languages… Just to sharpen the saw. Tips and suggestions are welcome!

; Project Euler - Problem 1
; 05 October 2001
;
; http://projecteuler.net/index.php?section=problems&id=1
;
; If we list all the natural numbers below 10 that are
; multiples of 3 or 5, we get 3, 5, 6 and 9.
; The sum of these multiples is 23.
;
; Find the sum of all the multiples of 3 or 5 below 1000.

; ALIASES
(define first-in car)
(define rest-of cdr)
(define empty-list '())
(define combine cons)
(define (++ value) (+ value 1))
(define (empty-list? list) (equal? list empty-list))

; RANGE FUNCTION
(define (range min max)
   (if (> min max) empty-list
       (combine min (range (++ min) max))))

; FILTER FUNCTION
(define (where list criteria)
   (if (empty-list? list) empty-list
       (if (criteria (first-in list))
           (combine (first-in list)
                    (where (rest-of list) criteria))
           (where (rest-of list) criteria))))

; IS A NUMBER DIVADABLE BY ANOTHER NUMBER?
(define (dividable-list? value by-list)
   (if (empty-list? by-list) #f
       (or (dividable? value (first-in by-list))
           (dividable-list? value (rest-of by-list)))))
(define (dividable? value by)
   (= 0 (modulo value by)))

; SUM FUNCTION
(define (sum-list list)
   (if (empty-list? list) 0
       (+ (first-in list) (sum-list (rest-of list)))))

; PROJECT EULER - Problem1
(define (Problem1 list multiples)
   (sum-list
      (where list
             (lambda (x) (dividable-list? x multiples)))))

Welcome to DrScheme, version 4.2.3 [3m].
Language: Pretty Big; memory limit: 128 megabytes.
>(Problem1 (range 1 9) '(3 5))
23
>(Problem1 (range 1 999) '(3 5))
233168
>
Advertisements

About this entry