Tag Archive for "scheme" tag

Problem 7 ver. 1 and 2: bruteforce and optimization

March 8th, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

Find the 10001st prime.

The problem of finding primes is the most famous computational task in the number theory.

At first, let's update the (generate-list-iteratively) function. It now includes i - the parameter, which denotes number of eligible elements up to this moment. We use it in the stopping condition.

  1.         (define (generate-list-iteratively seed filter map step stop)
  2.            (define (iterate current i) (if (stop current i) '()
  3.                                            (let* ([ok (filter current)] [next (if ok (+ i 1) i)] [rest (iterate (step current) next)])
  4.                                              (if ok (cons (map current) rest) rest))))
  5.            (iterate seed 0))

Dependant functions are rewritten also. I refactored the factorization functions and added primality tests (usual straightforward ones):

  1.         (define (minimal-factor-bruteforce n)
  2.            (define (iterate n x) (if (> x n) n (if (divides? n x) x (iterate n (+ x 1)))))
  3.            (iterate n 2))
  4.          (define (minimal-factor-sqrt-complexity n)
  5.            (define (iterate n x) (if (> x (sqrt n)) n (if (divides? n x) x (iterate n (+ x 1)))))
  6.            (iterate n 2))
  7.          (define (factorize n minimal-factor) (let ([p (minimal-factor n)]) (if (= p n) (list p) (cons p (factorize (/ n p) minimal-factor)))))
  8.          (define (prime?-bruteforce n) (= (minimal-factor-bruteforce n) n))
  9.          (define (prime?-sqrt-complexity n) (= (minimal-factor-sqrt-complexity n) n))
  10.          (define (primes-list n prime?) (generate-list-iteratively 2 prime? (lambda (x) x) (lambda (x) (+ x 1)) (lambda (x i) (= i n))))

Now, having an extra function that returns the last element in a list, we can easily solve the 7-th problem:

  1.         (define (last list) (if (null? (cdr list)) (car list) (last (cdr list))))
  2. (define (solution-7-bruteforce n) (last (primes-list n prime?-bruteforce)))
  3. (define (solution-7-optimized-1 n) (last (primes-list n prime?-sqrt-complexity)))

The complexity in memory is O(n), as we store n primes. It could be O(1), of course, but I prefer this way for now. The performance complexity of the algorithm is hard to determine. Probably, I need to overlook some literature for that.

Problem 6 ver. 1: brute-force

March 6th, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

What is the difference between the sum of the squares and the square of the sums?

No problems with brute-force here.

  1.         (define (square n) (* n n))
  2. (define (solution-6-bruteforce n) (let ([ns (numbers 1 n)]) (- (square (sum-list ns)) (sum-list (map square ns)))))

The number of operations (additions and multiplications) here is 3*n + 2. The complexity is O(n), and the algo is O(n) in memory as well (of course, can be done with O(1) in memory).

Problem 5 ver. 1: brute-force

March 6th, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

What is the smallest number divisible by each of the numbers 1 to 20?

This is also quite known problem --- finding a least common multiple (LCM).

As usual, let's start with the brute-force solution.

  1.         (define (least-common-multiple-bruteforce divisors)
  2.            (define (iterate x) (if (all-divide? x divisors) x (iterate (+ x 1))))
  3.            (iterate (max-list divisors)))
  4. (define (solution-5-bruteforce n) (least-common-multiple-bruteforce (numbers 2 n)))

This is the most inefficient way we can invent for the task of finding LCM. The complexity in the worst case is something like O(p^n), when n divisors out there are prime numbers, each is p at the average (but different, of course, then their LCM is just their product). More strictly, the number of divisions is up to n*p^n in the worst case (would be that if not shorcutted logical operations in (all-divide?) function).

Problem 4 ver. 1: brute-force

March 5th, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

Find the largest palindrome made from the product of two 3-digit numbers.

An additional function that filters out empty lists from a list of lists:

  1.         (define (filter-empty-lists lists) (filter (lambda (list) (not (null? list))) lists))

The function that represents a number in arbitrary number system and the function that returns 10-base digits for a number (starting from the rightmost digit):

  1.         (define (represent-in-radix n k) (if (= n 0) '() (cons (mod n k) (represent-in-radix (div n k) k))))
  2.          (define (digits n) (represent-in-radix n 10))

(digits) function could use standard (number->string), but this generalized solution I like more. Now a solution to the problem looks as easy as:

  1.         (define (palindrome-number? n) (let ([d (digits n)]) (equal? d (reverse d))))
  2.          (define (find-palindromes-among-products n) (map (lambda (x) (map (lambda (y) (* x y)) (numbers-filtered x n (lambda (y) (palindrome-number? (* x y)))))) (numbers 1 n)))
  3.  
  4. (define (solution-4-bruteforce n) (max-list (map max-list (filter-empty-lists (find-palindromes-among-products n)))))

Notice, for comparing lists we use (equal?), not (eq?) and not (eqv?) - they would return just #f. However, we could use (eq?) instead of (null?) in (filter-empty-lists) to compare a list to the empty one. As regards number of operations, we have n^2 / 2 multiplications, as many (palindrome-number?) calls that create digits lists (up to 6 divmod per each) and compare them (up to 6 comparisons per each). So, the complexity is O(n^2), and memory use is proportional to the palindrome numbers density in the n by n matrix (half of which we actually iterate over to find an answer).

Problem 3 ver. 1 and 2: brute-force and optimization

March 4th, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

Problem 3

Find the largest prime factor of a composite number.

is a very well known problem called factorization. The fundamental theorem of arithmetics comes in handy.

Brute-force in this case is just iterating from 2 upwards, searching for factors:

  1.         (define (factorize-bruteforce n)
  2.            (define (iterate n x) (if (> x n) (list n) (if (divides? n x) (cons x (iterate (/ n x) x)) (iterate n (+ x 1)))))
  3.            (iterate n 2))

If a factor is found, we divide the number by it, and continue with searching factors of a quotient. We don't need to start from 2 again (see the theorem).

The complexity for finding one factor is O(n) in the worst case. Let us optimize at once, stopping the iteration at sqrt(n). Indeed, a number cannot have a factor greater than its square root. This improves the worst case complexity drastically to O(\sqrt(n)) and this is the classical factorization algo.

  1.         (define (factorize-sqrt-complexity n)
  2.            (define (iterate n x) (if (> x (sqrt n)) (list n) (if (divides? n x) (cons x (iterate (/ n x) x)) (iterate n (+ x 1)))))
  3.            (iterate n 2))

Now, having written additional function (max-list) for finding maximums through lists, we can solve the third problem:

  1.         (define (max-list list) (fold-left max (car list) list))        
  2. (define (solution-3-bruteforce n) (max-list (factorize-bruteforce n)))
  3. (define (solution-3-optimized-1 n) (max-list (factorize-sqrt-complexity n)))

Problem 2 ver. 1: brute-force solution

March 4th, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

I've written the generic procedure to generate lists iteratively:

  1.         (define (generate-list-iteratively seed filter map step stop)
  2.            (define (iterate current) (if (stop current) '()
  3.                                          (let ([rest (iterate (step current))])
  4.                                            (if (filter current) (cons (map current) rest) rest))))
  5.            (iterate seed))

I've refactored (create-filtered-numbers-list from to filter) function into (numbers-filters) and added also (numbers) for future use:

  1.         (define (numbers-filtered from to filter) (generate-list-iteratively from filter (lambda (x) x) (lambda (x) (+ x 1)) (lambda (x) (> x to))))
  2.          (define (numbers from to) (numbers-filtered from to (lambda (x) #t)))

Now the brute-force solution for the problem 2

Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million

looks like this:

  1.         (define (fibonacci to) (generate-list-iteratively (cons 1 1) (lambda (pair) #t) (lambda (pair) (car pair)) (lambda (pair) (cons (cdr pair) (+ (car pair) (cdr pair)))) (lambda (pair) (> (car pair) to))))
  2.  
  3. (define (solution-2-bruteforce n) (sum-numbers (filter even? (fibonacci n))))

The complexity is O(n). I decided not to generate a filtered list, but rather first generate, then filter, (fibonacci) function goes to the library for future use (for future functions I will not mention placing into my library). This is an optimal algorithm for generating a Fibonacci sequence, unlike computing the n-th member of it, which can be done more efficiently. However, for computing a sum of members, perhaps, there is a better solution, I will think about it later.

Problem 1 ver. 2: brute-force solution generalized to a list of divisors

March 3rd, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

I refactored the previous solution and extracted such library functions, they could be useful in future:

  1.         (define (some-divides? n divisors) (exists (lambda (x) (divides? n x)) divisors))
  2.          (define (sum-numbers numbers) (fold-left + 0 numbers))
  3.          (define (create-filtered-numbers-list from to filter)
  4.            (define (iterate current) (if (> current to) '()
  5.                                          (let ([rest (iterate (+ current 1))])
  6.                                            (if (filter current) (cons current rest) rest))))
  7.            (iterate from))

I think for these algoritms, where we have to iterate through large lists of numbers, the laziness (e.g. in Haskell) would give slightly more elegant code at certain places.

The first problem solution now becomes:

  1. (define (sum-of-multiples-bruteforce up-to-n divisors)
  2.   (let ([multiples (create-filtered-numbers-list 1 up-to-n (lambda (x) (some-divides? x divisors)))])
  3.     (sum-numbers multiples)))
  4.  
  5. (define (solution-1-bruteforce n) (sum-of-multiples-bruteforce (- n 1) '(3 5)))

For a list of divisors with length k the number of operations will be k*n. Actually, less than that because of shortcut (exists). Assuming k fixed and small, the complexity is still O(n). We could make use of the not yet written (create-numbers-list) function and filter that afterwards instead of the (create-filtered-numbers-list) function, but let us take less space in memory at once.

How to write and connect an own library in R6RS Scheme (PLT Windows solution)

March 2nd, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags:

It took me quite a while to understand. Today I'm using a laptop with Windows, so here is solution for the windows-version of the PLT Scheme implementation. Under Linux it will not differ much. By the way, to use R6RS in PLT DrScheme you need to choose Module language (Ctrl+L) and write #!r6rs in the beginning of each program.

First, write your own library. I separated the function (divides?) from the previous program:

  1. #!r6rs
  2. (library (project-euler-lib)
  3.          (export divides?)
  4.          (import (rnrs))
  5.          
  6.          (define (divides? n x) (= (mod n x) 0))
  7.          )

Second, save it under the path, for example, C:\Projects\projecteulersolutions\project-euler-lib.scm and, as it is explained in "C:\Program Files\PLT\doc\r6rs\Installing_Libraries.html", compile and install the library into collections folder by running the command (the first way explained there seems not to be working):

"C:\Program Files\PLT\plt-r6rs.exe" --install C:\Projects\projecteulersolutions\project-euler-lib.scm

Some files drop into the directory "C:\Users\User\AppData\Roaming\PLT Scheme\4.1.4\collects\project-euler-lib"

Third, you connect it to the program by replacing (import (rnrs)) clause with (import (rnrs) (project-euler-lib)). And, of course, delete (divides?) function form the top-level program body.

Fourth, before recompiling a library, don't forget to clean the folder:

rmdir /s /q "C:\Users\User\AppData\Roaming\PLT Scheme\4.1.4\collects\project-euler-lib"

Problem 1 ver. 1: brute-force solution

March 2nd, 2009 by Ivan Lakhturov | 0 Category: Programming | Tags: |

Let us start with solutions to Project Euler problems. I will always start with brute-force solutions if those are possible and later on post optimized solutions. Every solution will be given in Scheme (R6RS) along with quick estimate of complexity. The reason for solving those problems is training myself in Scheme and, of course, fun.

Find the sum of all the multiples of 3 or 5 below 1000.

Solution:

  1. #!r6rs
  2. (import (rnrs))
  3.  
  4. (define n 1000)
  5.  
  6. (define (divides? n x) (= (mod n x) 0))
  7.  
  8. (define (divided-by-3-or-5? n) (or (divides? n 3) (divides? n 5)))
  9.  
  10. (define (add-dividends n sum) (if (< n 1) sum (add-dividends (- n 1) (if (divided-by-3-or-5? n) (+ sum n) sum))))
  11.  
  12. (display (add-dividends (- n 1) 0))

This is the simplest straightforward approach. Backward-recursion is used, with tail-recursion optimization, which is obligatory for all Scheme implementations, will be transformed into iteration. Backward direction is to simplify a function signature (otherwise an extra parameter is needed).

The complexity is O(n), assuming the (mod) operation is atomic. More strictly, the number of operations is 2*n. By the way, in R5RS (mod) is called (remainder).

Bug, compiling PLT-Scheme

February 19th, 2009 by Ivan Lakhturov | 0 Category: Linux, Programming | Tags: | |

The most easy-to-use Scheme compiler/interpreter is PLT, simple IDE is included. Emerging the latest ebuild gives errors under -O3 optimization flag, I confirmed it at the bugtracker. The solution is to switch temporarily to -O2.