roddy: (Default)
[personal profile] roddy
This is the first in a series of posts about attempting Project Euler in PLT Scheme. The posting schedule is, for the most part, every Friday. For more information, see the introductory post.

The first problem on Project Euler is relatively simple:

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.
Project Euler

First things first, I figure I need a function to determine if one number is a multiple of another number. Since I can't recall there being any such function built into PLT Scheme, and the manual page about numbers has nothing like it, I decide to write my own:
(define (multiple-of? first second) (if (= 0 (modulo first second)) #T #F))
My uninspired variable names notwithstanding, the function returns true of first%second=0, false otherwise.

Unfortunately we need to test if a number is multiple of 3 or 5. So we could either call multiple-of? twice for each, or be lazy and write a function do test against multiple multiples. (Pun fully intended.)

I'm lazy. I wrote the function.
(define multiple-of-many?
  (lambda (test bases)
    (cond
      ((number? bases) (multiple-of? test bases))

      ((or (not (list? bases)) (empty? bases) (list? (member #f (map (lambda (x) (number? x)) bases)))) #F)

      ((list? (member #t (map (lambda (x) (multiple-of? test x)) bases))) #T)

      (else #F))))

Being primarily a Java coder, there has been many a time when I have prayed to the Java gods for a map function. Note the gratuitous use of said function in the previous example.

The first condition checks to see if we've actually passed in a list of multiple bases or just one. If it's just one, it simply calls multiple-of? and gets on with it.

The second condition validates that -- (in order) yes, the list of multiple bases is actually a list, the list is not empty, and every element in the list is a number.

The third condition actually tests the premise and tests the number against the multiple base list. This is done through a map function that calls multiple-of? against every element in the list.

And the else case is the this-is-a-multiple case. Returns automatic fail.

That's it for the helper functions. Now we need something that will iterate through the numbers 1 to 1000 and add the multiples of 3 and 5. I came up with the following:
(define sum_all
  (lambda (current start finish bases)
    (cond
      ( (>= start finish) current)

      ( (<= start 0) (sum_all 0 1 finish bases))

      ( (multiple-of-many? start bases) (sum_all (+ current start) (add1 start) finish bases))

      ( else (sum_all current (add1 start) finish bases)))))


The function takes four parameters: current, start, finish, base. "Current" holds the current sum. "Start" doesn't actually hold the first of the range, though it does initially; it actually holds the current number we're considering -- that is, if start is a multiple of 3 or 5, it is what is added to current. "End" is the target endpoint, in our case 1000. Finally, "bases" is a list of the bases we care about.

Truthfully if I hard-coded in the values of 1000 for "end" and '(3 5) for bases, we could make do with only two parameters for the function, but I tend to make my functions reusable. Who knows when I might someday need to sum the multiples of, say, 7 and 11 from 9 to 9000?

The first condition is the end-condition: if start=end, we've reached the end of our summation process and current now holds the final sum.

The second condition is an error-checking condition: if start is less than or equal to zero, re-call the sum_all function with start=1 instead.

The third condition actually checks if start is a multiple-of? the bases. If it is, it re-calls the sum_all function with current=current+start, start++, end, and bases (with end and bases remaining the same).

The else condition occurs if start is not a multiple-of? the bases. In this case, it calls the sum_all function again and passes in start++.

Finally, to run, we call:
(sum_all 0 0 1000 '(3 5))
The answer is 233168.

Code


The code, in its entirety:
(define (multiple-of? first second) (if (= 0 (modulo first second)) #T #F))

(define multiple-of-many?
  (lambda (test bases)
    (cond
      ((number? bases) (multiple-of? test bases))

      ((or (empty? bases) (not (list? bases)) (list? (member #f (map (lambda (x) (number? x)) bases)))) #F)

      ((list? (member #t (map (lambda (x) (multiple-of? test x)) bases))) #T)

      (else #F))))

(define sum_all
  (lambda (current start finish bases)
    (cond
      ( (>= start finish) current)

      ( (<= start 0) (sum_all 0 1 finish bases))

      ( (multiple-of-many? start bases) (sum_all (+ current start) (add1 start) finish bases))

      ( else (sum_all current (add1 start) finish bases)))))


Short Form
Alternatively, it is possible to do everything in a single function. As I mentioned before, I am primarily a Java programmer, so I like functions. But if you wanted to you could just do as follows:
(define sum_all_short_form
  (lambda (current start finish bases)
    (cond
      ( (or (>= start finish) (not? (list? bases)) (empty? bases) (list? (member #f (map (lambda (x) (number? x)) bases)))) current)

      ( (<= start 0) (sum_all 0 1 finish bases))

      ( (list? (member #t (map (lambda (x) (if (= 0 (modulo start x)) #T #F)) bases))) (sum_all (+ current start) (add1 start) finish bases))

      ( else (sum_all current (add1 start) finish bases)))))


Short form, no error checking
Note once more that the majority of the code is error checking. If we were to remove that, it would be even shorter:
(define sum_all_short_form
  (lambda (current start finish bases)
    (if
     (list? (member #t (map (lambda (x) (if (= 0 (modulo start x)) #T #F)) bases))) (sum_all (+ current start) (add1 start) finish bases)

     (sum_all current (add1 start) finish bases))))
From:
Anonymous( )Anonymous This account has disabled anonymous posting.
OpenID( )OpenID You can comment on this post while signed in with an account from many other sites, once you have confirmed your email address. Sign in using OpenID.
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

roddy: (Default)
Roddy of the Frozen Peas

Expand Cut Tags

No cut tags

November 2010

S M T W T F S
 123456
78910111213
14151617181920
21222324252627
282930    

Style Credit

Tags