Project Euler Problem 4 in Clojure

Most of my time was spent playing with for, trying to work out if it was best to do it all in the list comprehension. In the end I thought it was more readable to pull the creation of the products out into its own function.

(defn palindrome? [str]
  (if (= (first str) (last str))
    (if (<= 2 (count str))
      (recur (rest (butlast str)))
      true)
    false))

(defn three-digit-numbers []
  (range 100 1000))

(defn- products []
  (distinct
    (for [n1 (three-digit-numbers) n2 (three-digit-numbers)]
      (* n1 n2))))

(defn solve []
  (apply max (filter #(palindrome? (str %)) (products))))

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 -----------------------