Project Euler 1 (sum of multiples of 3 or 5 under 1000)

Question

I solved this a while ago. In the moment I solved it I was learning Scheme and, well, I still am. I'm not looking at the best solution (I searched for it and coded it already, in Python), what I want is to improve this code, maintaining the same (brute) approach, so I can learn some best practices and tips in Scheme. Maybe there are some suggestions on how I wrote the routines, for example.

#lang racket
(define (check x) (or (= (modulo x 3) 0)
                      (= (modulo x 5) 0)))

(define (count-check x) (if (check x)
                            x
                            0))

(define (sum-multiples-rec actual limit acc) (if (< actual limit)
                                                 (sum-multiples-rec (+ actual 1) limit (+ (count-check actual) acc))
                                                 acc))

(define (sum-multiples lower-limit upper-limit) (sum-multiples-rec lower-limit upper-limit 0))

(sum-multiples 0 1000)

Answer 1

So, any time you want to write a "helper" recursive function, the standard way to write that is to use a named let. So here's how I might restructure your program (but keeping the same algorithm):

(define (sum-multiples start end)
  (let loop ((sum 0)
             (i start))
    (cond ((>= i end) sum)
          ((or (zero? (modulo i 3))
               (zero? (modulo i 5)))
           (loop (+ sum i) (add1 i)))
          (else (loop sum (add1 i))))))

Named let is a macro, which in this case expands to the same expression as:

(define (sum-multiples start end)
  ((letrec ((loop (lambda (sum i)
              (cond ((>= i end) sum)
                    ((or (zero? (modulo i 3))
                         (zero? (modulo i 5)))
                     (loop (+ sum i) (add1 i)))
                    (else (loop sum (add1 i)))))))
     loop)
   0 start))

(I've taken the liberty of using (add1 i) instead of (+ i 1) since you're using Racket.)

---

Here's a version that's even more Rackety, using for/sum to accumulate the sum rather than using a manual loop:

(define (sum-multiples start end)
  (for/sum ((i (range start end)))
    (if (or (zero? (modulo i 3))
            (zero? (modulo i 5)))
        i 0)))

Answer 2

Better programming practice would be to decompose the problem in such a way that the procedures adhere to the Single Responsibility Principle. In other words, the answer should be obtained by evaluating something like

(sum (filter (multiple-of-any? 3 5) (range 0 1000)))

… which reads just like the problem to be solved.

Here's a set of functions that could achieve that. Note that, unlike the functions you've defined (check, count-check, sum-multiples-rec, sum-multiples), which are highly specific to solving Project Euler Problem 1, these functions are flexible and could likely be reused to solve other problems.

(define (sum list)
     (if (eq? list '())
         0
         (+ (car list) (sum (cdr list)))))

(define (range min max)
    (if (= min max)         
        '()
        (cons min (range (+ min 1) max))))

(define (filter pred? list)
    (cond ((eq? list '()) list)
          ((pred? (car list)) (cons (car list) (filter pred? (cdr list))))
          (else (filter pred? (cdr list)))))

(define (multiple-of-any? . divisors)
    (lambda (n) (cond ((eq? divisors '()) #f)
                      ((= 0 (modulo n (car divisors))) #t)
                      (else ((apply multiple-of-any? (cdr divisors)) n)))))

Answer 3

As noted in the comment, your code currently looks like it has a (admittedly fairly minor) problem. In sum-multiples, you try to pass actual and limit as parameters to sum-multiples-rec, but those names aren't bound to anything at that point. You need/want something more like:

(define (sum-multiples lower-limit upper-limit) 
    (sum-multiples-rec lower-limit upper-limit 0))

As far as style goes, the main thing I'd change would be to write your ancillary functions inside of sum-multiples. Right now, sum-multiples-rec, count-check and check are all "publicly" visible, but they're unlikely to be of any use except to count-multiples. As such, they should really be "hidden" inside it.

As such, your code could end up something like this:

(define (sum-multiples lower-limit upper-limit)  
  (define (sum-multiples-rec actual limit acc)
    (define (count-check x) 
      (define (check x) (or (= (modulo x 3) 0)
                            (= (modulo x 5) 0)))
      (if (check x) 
          x 
          0))
    (if (< actual limit)
        (sum-multiples-rec (+ actual 1) limit (+ (count-check actual) acc))
        acc)) 
 (sum-multiples-rec lower-limit upper-limit 0))

[Indentation probably open to improvement]

So, check is only defined/visible inside of count-check. count-check (in turn) is only defined/visible inside of sum-multiples-rec, and sum-multiples-rec is only defined/visible inside of sum-multiples. If (for example) you try to execute something like (check 3) outside of sum-multiples, you'll get an error like:

check: undefined; cannot reference an identifier before its definition

This is pretty much the same general idea as (for example) a class in something like Java or C++ making as many if its members private as possible. Limiting the visibility of names dramatically reduces the chances of a name collision that could result in your calling entirely the wrong function. This is particularly important with names like check that could mean all sorts of different things under different circumstances.

Of course, much like with those other languages, this sort of discipline becomes much more important for larger programs. For a really tiny program, it's not all that big of a deal.

Answer 4

The approach you have taken is to check each number between 0 and 1000 to see if it is a multiple of either 3 or 5, and if so, add it to the accumulator.

A more straightforward solution is to use the Inclusion-Exclusion Principle. Add the multiples of 3 and the multiples of 5. Since the multiples of 15 are double-counted, subtract the multiples of 15.

(define (sum list)
     (if (eq? list '())
         0
         (+ (car list) (sum (cdr list)))))

(define (multiples min max step)
     (if (>= min max)
         '()
         (cons min (multiples (+ min step) max step))))

(- (+ (sum (multiples 0 1000 3))
      (sum (multiples 0 1000 5)))
   (sum (multiples 0 1000 15)))