in Books, Doing Books, How to Solve it by Computer

How to Solve it by Computer #6

Problem 2.7.1: Design an algorithm that counts the number of digits in an integer.

Again, not a super interesting problem but one which we can solve for free. And I love free stuff.

user=> (count (get-digits 2345))
4
user=> (count (get-digits 890))
3

So is the next one.

Problem 2.7.2: Design an algorithm to sum the digits in an integer.

 

user=> (reduce + (get-digits 2345))
14
user=> (reduce + (get-digits 890))
17

And this one is good too.

Problem 2.7.3: Design an algorithm that reads in a set of n single digits and converts them into a single decimal integer. For example, the algorithm should convert the set of 5 digits {2,7,4,9,3} to 27493.

 

user=> (reduce + (map-indexed get-multiplied (reverse [2 7 4 9 3])))
27493

And that’s why it’s cool to make small complete functions without side-effects. Reusability, baby.

Problem 3.4.2: It is possible to implement a sieving algorithm which crosses out each composite (non-prime) number exactly once rather than a number of times. […] Try to implement this algorithm aka. Sieve of Eratosthenes.

The wikipedia page got a cool animation of this algorithm. It’s a great starting point to start with this.

Let’s make this interactive. I start with a list of all integers from 2 to 40:

user=> (def numbers (take 39 (iterate inc 2)))
#'user/numbers
user=> numbers
(2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40)

Now, imagine we know already that 2 is a prime number.

user=> (def primes [2])
#'user/primes
user=> primes
[2]

What we would now do is remove every number which is a multiple by 2. Or whose characteristic is mod 2 = 0.

 

user=> (remove #(= 0 (rem % (first primes))) numbers)
(3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39)

Neat. Now we just need to find the next prime. We know that the next bigger number in our number list is a prime, in this case 3. And then we start again.

Let’s write a function:

(defn prime-sieve
  "Generates all primes up to n using the Sieve of
   Eratosthenes"
  [n]
  {:pre [(> n 1)]}
  (loop [primes nil
         numbers (take (dec n) (iterate inc 2))]
    (if (seq numbers)
        (recur (conj primes (first numbers))
               (remove #(= 0 (rem % (first numbers))) numbers))
        primes)))

I was surprised how small and easy to function is. Let’s go through it. We start easily with creating a list of numbers, like before. It starts with 2 and ends with n. Also we have an empty collection primes in which we put our primes. We know that the first element of our list numbers is always a prime, so we can put that into there. The next step is to remove all multiplies of that prime in our list. Now we just recursively call that function again. This runs so long until there’s no number left in numbers and the function returns our – now – big list of primes.

 

user=> (prime-sieve 20)
(19 17 13 11 7 5 3 2)
user=> (prime-sieve 60)
(59 53 47 43 41 37 31 29 23 19 17 13 11 7 5 3 2)

Neat.

Write a Comment

Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.