Project Euler Problem 3 in Clojure - part 2

So the solution in part 1 was no good - it took half an hour to run. I spent a while trying and failing to make a lazy, purely functional version but after talking to Ed about his solution I came up with this, which runs in about 500msec :

(defn factor? [big small]
  (zero? (mod big small)))

(defn prime? [n]
  (not-any? #(factor? n %) (range 2 n)))

(defn primes []
  (filter #(prime? %) (iterate inc 2)))

(defn prime-factors [n]
  (let [factors (atom ())]
    (last
     (for [candidate (primes) :while (< (apply * @factors) n)]
       (if (factor? n candidate)
      (swap! factors conj candidate))))))

(defn solve []
  (first (prime-factors 600851475143)))

Project Euler Problem 3 in Clojure - part 1

This one is proving a bit tougher. First you need a list of prime numbers. I'm using the Euler's Sieve to produce primes.

First I wrote this function:

(defn sieve-numbers [position numbers]
  (if (>= position (count numbers))
  numbers
    (let [prime (nth numbers position)]
      (let [products (map #(* prime %) numbers)]
        (let [filtered (remove #(some #{%} products) numbers)]
          (recur (inc position) filtered))))))

which worked but was dog-slow:

;; (dotimes [_ 5] (time (sieve-euler 1000)))
;; "Elapsed time: 484.981564 msecs"
;; "Elapsed time: 459.624835 msecs"
;; "Elapsed time: 462.771112 msecs"
;; "Elapsed time: 460.312279 msecs"
;; "Elapsed time: 462.203786 msecs"
;; nil

To solve the problem we need to primes up to ceil(sqrt(N)) which is 775147 so that first method would take days.

To speed up the filtering I rewrote to use a SortedSet:

(defn sieve-numbers [primes candidates]
  (if (empty? candidates)
  primes
  (let [prime (first candidates)]
    (let [products (map #(* prime %) candidates)]
      (let [filtered (difference candidates products #{prime})]
        (recur (conj primes prime) filtered))))))

which is about 32 times faster:

;; (dotimes [_ 5] (time (sieve-euler 1000)))

;; "Elapsed time: 13.061787 msecs"
;; "Elapsed time: 12.994529 msecs"
;; "Elapsed time: 13.716897 msecs"
;; "Elapsed time: 13.237088 msecs"
;; "Elapsed time: 14.33136 msecs"

Still not good enough though. I need a faster sieve before I can even attempt to factor the large(ish) number and solve problem 3 inside a minute. I think my next step will be to pre-filter some of the non-primes with a Wheel Factorisation. This method wont remove all the non-primes, but it might be fun to implement.

I'm leaving the current sieve chugging away tonight to see how long it takes anyway, for comparison.

Project Euler Problem 2 in Clojure

;; lazy fibo stolen from programming clojure p137
(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [1 2])))

(defn solve []
(reduce + (filter even? (take-while #(> 4000000 %) (fibo)))))

Project Euler Problem 1 in Clojure

I'm trying to solve Project Euler using Clojure as an exercise to learn the language. My aim is to favour readability over performance, but still execute each problem inside a minute.


(defn is-multiple [number factor]
(zero? (mod number factor)))

(defn is-multiple-3-or-5 [number]
(or (is-multiple number 3)
(is-multiple number 5)))

(defn solve []
(reduce + (filter is-multiple-3-or-5 (range 1 1000))))

Easy way to get information about a running JVM

kill -3 $PID

outputs a load of information about your running JVM to stdout. Very handy.

Happy Hacking Keyboard Lite 2 Xmodmap settings for Ubuntu Linux

During the upgrade to Ubuntu 9.10 I managed to clobber my hard-won Xmodmap settings to make my Happy Hacking Keyboard Lite 2 (the USB version, with the arrow keys) work properly.

Here is the commented xmodmap file I use to modify the default key mappings, which is slightly British oriented. To use the file, run xmodmap path_to_file.

Some features:

• £ and € symbols are mapped to right-diamond-3 and right-diamond-e, respectively.
  
• Arrow keys work.
• PageUp/PageDown on Fn-Arrows work.
• Left Diamond is another Alt.
• Tilde, pipe, backslash and backtick behave themselves.

I just hope I don't ever have to work all this out again.


------------------- SNIP FILE -------------------

! This is an xmodmap input file for the Happy Hacking Keyboard, model HHKB Lite 2. It assumes that the
! keymap is already set up for a gb-105 keyboard, then applies fixes for arrow keys and British conventions
!
! This file makes the following changes:
!
! Fix the arrow keys
!
keycode 111 = Up
keycode 116 = Down
keycode 113 = Left
keycode 114 = Right
!
! Fix the Fn-Arrows to give PgUp, PgDown, Home and End
!
keycode 112 = Prior
keycode 117 = Next
keycode 110 = Home
keycode 115 = End
!
! Fix the Alt and Diamond keys
!
keycode 133 = Super_L
keycode 134 = Mode_switch
keycode 64 = Alt_L
keycode 108 = Alt_R
!
! Put the @ on shift-' as British keyboards do
!
keycode 48 = apostrophe at
!
! Put the " on shift-2 as British keyboards do
!
keycode 11 = 2 quotedbl
!
! Put the Pound symbol on right-diamond-3
!
keycode 12 = 3 numbersign sterling sterling
!
! Put the Euro symbol on right-diamond-e
!
keycode 26 = e E EuroSign
!
! Fix tilde
!
keycode 49 = grave asciitilde
!
! Fix backslash
!
keycode 51 = backslash bar
!
!
! Remove all the existing modifier key mappings
!
clear Shift
clear Lock
clear Control
clear Mod1
clear Mod2
clear Mod3
clear Mod4
clear Mod5
!
! Put the modifier key mappings back
!
add Shift = Shift_L Shift_R
add Lock = Caps_Lock
add Control = Control_L Control_R
!
! including this line which makes both Alt keys and the left diamond key act as Alt keys
!
add Mod1 = Alt_L Alt_R Super_L
!
! makes the right diamond acts as the Mode_switch modifier (mapped to right diamond above)
!
add Mod3 = Mode_switch
add Mod5 = Scroll_Lock

------------------------- END OF FILE -----------------------

Share a git repository with unix groups

If you have a shared Linux/Unix box that all your developers use to share code with git, there are various ways of setting up the shared repository. If you just use git over ssh, you don't need to maintain any more servers.

The simplest possible solutions assume that there is a single user account and different developers are authenticated on the server with their ssh public keys. I needed to restrict which developers get access to different repositories, and to be able to switch these permissions on and off. Unix has already solved this problem of course, with users and groups. Here is how to use real users and groups on your unix server to control git access.

1. Set up unix accounts for your users. "adduser jim"
   
2. Set up groups for each project, "addgroup wonderproject-developers"
3. Add the appropriate developers to the group "adduser jim wonderproject-developers"
4. In a private directory on your server, logged in as yourself, make a directory for the git repository "mkdir wonderproject.git"
5. Make the new group the group owner of the git repository "chgrp wonderproject-developers wonderproject.git/"
6. Fix the perms so only the group and the owner can read and write the repository "chmod 770 wonderproject.git/"
7. Make the repository setgid, so that any new files created inside it have group ownership the same as the directory "chmod g+s wonderproject.git"
8. cd wonderproject.git
9. create the git repository "git --bare init --shared=group" the --shared option ensures that git keeps the correct permissions when the various developers push commits into the repository.
10. Now, if your project is empty, clone this new repository onto your desktop and start committing "git clone ssh://jim@git.example.com:port/path/to/repos/wonderproject.git
11. If you have an existing repository on your desktop and you want to push it into the empty shared repository, edit your .git/config remote url to point at the new server url and then do a "git push --all"