Tag Archives: github

Learning From Project Euler

If you’re just starting out with programming, like me, and haven’t yet checked out Project Euler and GitHub, please do. They’re not hard to get into, and I’ve found them really useful!

Project Euler is a particularly powerful impetus for you to improve on your programming skills. Like Codecademy, you start out simple and work your way up through challenges – unlike Codecademy, the challenge is actually worthwhile.

Github, meanwhile, is really useful for storing the code you’re working on and encouraging commentary/interaction with your fellow programmers. It’s also an introduction to version control, which is a useful thing to understand.

I’d urge you to listen to the people at Project Euler and avoid committing Problem answers to Github, as it kind of takes away from the challenge.

Project Euler

In the in-between, a problem with Project Euler forced me to re-design the function I built here, and I’m pretty happy with the results.

My original prime-finding function was taking well over a minute, so I had no choice but to refactor.

It’s a great demonstration of how Project Euler forces you out of your comfort zone – in my case, into Racket vectors. Even though they’re essentially the same as arrays in most other languages, something in me balked at using vectors in Racket. Something about their mutability struck me as not-right in a language so defined by its immutability.

Here’s the first draft of what I wrote, working with vectors to create a static sieve of eratosthenes of length (n):

(define (primes-to x)
  (letrec ([f (lambda (count vs n)
                (cond
                  [(= n 0) (begin (vector-set! vs 0 #f) (f (+ count 1) vs (+ n 1)))]
                  [(= n 1) (begin (vector-set! vs 1 #f) (f (+ count 1) vs (+ n 1)))]
                  [#t
                   (if (= n x)
                       vs
                       (if (< count x)
                           (if (= n count)
                               (f (+ count n) vs n)
                               (begin (vector-set! vs count #f)  (f (+ count n) vs n)))
                           (f (+ n 1) vs (+ n 1))))])

                )])
    (f 0 (make-vector x #t) 0)))

Since you can access vector members using vector-ref, and this program currently runs all the way to (= n x) – which means that we check almost every item on the list – there’s a lot of optimisation which could be done, and done profitably.

The important thing is (if (= n count), which takes away progressively larger chunks of things to check as the formula grows – I believe this puts it in O(n log n) space, or close to it. With this formula, I can check two million digits in ~6 seconds and I could cut that down substantially with some quick tweaks.

Eventually, I’ll hit a wall with the sieve of eratosthenes, and be forced to use the sieve of atkin – which I do not understand and actually dread facing. When I do have to face it, though, it will magically transform into a fun and interesting challenge. That’s the magic of Project Euler!

Last day, Capricorn-15s

Tagged , , ,
%d bloggers like this: