project-euler1〜20 - trotrの日記

clojureで書くことに慣れるために簡単な問題を解いてみる。

my.math.prime

自分用の個人的なライブラリはどのあたりに置くのが良いのだろう(今は~/mylib/clojure以下に置いている)

(ns my.math.prime
  (:use clojure.contrib.math))

(defn prime? [n]
  (let [sqn (int (sqrt n))]
    (or (= 2 n)
	(and (odd? n)
	     (loop [i 3]
	       (cond (> i sqn) true
		     (zero? (rem n i)) false
		     :else (recur (+ i 2))))))))


(def prime-seq
     (let [seq ((fn step [n]
		  (lazy-seq
		   (if (prime? n) (cons n (step (+ 2 n))) (step (+ 2 n)))))
		3)]
     (lazy-cat [2] seq)))

(defn- divide-even [n]
  (loop [r 1, n n]
    (if (even? n)
      (recur (* r 2) (bit-shift-right n 1))
      [r n])))

(defn prime-factors [n]
  (let [[r n*] (divide-even n)
	rs (if (= 1 r) '() (list r))]
    (loop [rs rs, n n*, i 3]
      (cond (= n 1) (cons n rs)
	    (zero? (rem n i)) (recur (cons i rs) (/ n i) i)
	    :else (recur rs n (+ i 2))))))

1.clj

http://projecteuler.net/index.php?section=problems&id=1

(def dividable? (comp zero? rem))

(reduce (fn [n x] (if (or (dividable? x 3) (dividable? x 5)) (+ x n) n))
	0 (range 1 1000)) ; => 233168

2.clj

http://projecteuler.net/index.php?section=problems&id=2

(use '[clojure.contrib.seq-utils :only (rec-cat)])
(use '[clojure.contrib.math :only (expt)])

(let [n (* 4 (expt 10 6))]
  (->> (rec-cat s [0 1] (map + s (rest s)))
       (take-while #(< % n))
       (filter even?)
       (reduce +))) ; => 4613732

3.clj

http://projecteuler.net/index.php?section=problems&id=3

(use my.math.prime)
(apply max (prime-factor 13195)) ; => 29
(apply max (prime-factor 600851475143)) ; => 6857

4.clj

http://projecteuler.net/index.php?section=problems&id=4

(defn palindrome? [n]
  (let [s (str n)]
    (= s (apply str (reverse s)))))

(defn solve [from to]
  (let [xs (for [i (range from to)
		 j (range i to)
		 :when (palindrome? (* i j))]
	     (* i j))]
    (apply max xs)))
  
(solve 100 1000) ; => 906609

5.clj

http://projecteuler.net/index.php?section=problems&id=5

(use '[clojure.contrib.math :only (lcm)])
(reduce lcm (range 1 10)) ; => 2520
(reduce lcm (range 1 20)) ; => 232792560

6.clj

http://projecteuler.net/index.php?section=problems&id=6

(let [sq #(* %1 %1), n 101]
  (- (sq (reduce + (range 1 n)))
     (->> (range 1 n)
	  (map sq)
	  (reduce +)))) ; => 25164150

7.clj

http://projecteuler.net/index.php?section=problems&id=7

(use my.math.prime)
(nth prime-seq (- 6 1)) ; => 13
(nth prime-seq (- 10001 1)) ; => 104743

8.clj

http://projecteuler.net/index.php?section=problems&id=8

(use '[clojure.contrib.duck-streams :only (reader)])

(binding [*in* (reader "8.dat")]
  (->> (str (read-line))
       (partition 5 1)
       (map (comp (partial reduce *) 
		  (partial map #(- (int %) 48))))
       (apply max))) ; => 40824

9.clj

http://projecteuler.net/index.php?section=problems&id=9

(defn solve [n]
  (let [sq #(* %1 %1)]
    (loop []
      (let [a (rand-int n)
	    b (rand-int (- n a))
	    c (- n a b)
	    [a* b* c*] (apply vector (sort > (list a b c)))]
	(if (= (sq a*) (+ (sq b*) (sq c*)))
	  (* a* b* c*)
	  (recur))))))

(solve 1000) ; => 31875000

10.clj

http://projecteuler.net/index.php?section=problems&id=10

(use my.math.prime)
(reduce + (take-while #(< % 2000000) prime-seq)) ; => 142913828922

11.clj

http://projecteuler.net/index.php?section=problems&id=11

(use '[clojure.contrib.duck-streams :only (read-lines)])
(use '[clojure.contrib.str-utils :only (re-split)])
(use '[clojure.contrib.seq-utils :only (indexed)])

(def map-to-vector (comp (partial apply vector) map))
(defn read-data [file]
  (map-to-vector (fn [line] 
		   (map-to-vector #(Integer/parseInt %) (re-split #"\s" line))) 
		 (read-lines file)))

(defn transpose [xs] (apply map list xs))
(def horizontals (partial mapcat #(partition 4 1 %))) 
(def verticals (comp horizontals transpose))

(defn- gen$ [yfn xfn]
  #(take 4 (iterate (fn [p] [(yfn (p 0)) (xfn (p 1))]) %)))
(defn- mget [m ps] (reduce #(get %1 %2 0) m ps))

(defn diagonally [mat gen]
  (let [h (count mat), w (count (first mat))
	mget* (partial mget mat)]
    (for [i (range 0 h), j (range 0 w)]
      (map mget* (gen [i j])))))

(defn solve [file]
  (let [xs (read-data file)]
    (->> (lazy-cat (horizontals xs)
		   (verticals xs)
		   (diagonally xs (gen$ inc inc))
		   (diagonally xs (gen$ inc dec)))
	 (map (partial reduce *))
	 (apply max))))

(solve file)

12.clj

http://projecteuler.net/index.php?section=problems&id=12

(use '[clojure.contrib.seq-utils :only (reductions)])
(use '[clojure.contrib.math :only (sqrt)])

(defn divisors [n]
  (let [sqn (int (sqrt n))]
    (loop [r (list 1 n), i 2]
      (cond (> i sqn) r
	    (zero? (rem n i)) (let [q (/ n i)]
				(if (= q i) 
				  (recur (cons i r) (inc i))
				  (recur (cons i (cons q r)) (inc i))))
	    :else (recur r (inc i))))))

(def tn-seq (reductions + (iterate inc 1)))

(first 
 (drop-while (fn [i] (> 500 (count (divisors i)))) 
	     tn-seq)) ; => 76576500

13.clj

http://projecteuler.net/index.php?section=problems&id=13

(use '[clojure.contrib.duck-streams :only (read-lines)])
(reduce (fn [n line] (+ n (BigInteger. line)))
	0 (read-lines "13.dat")) ; => 5537376230390876637302048746832985971773659831892672

14.clj

http://projecteuler.net/index.php?section=problems&id=14

(use '[clojure.contrib.math :only (expt)])

(defn f [n]
  (loop [i 0, n n]
    (cond (= 1 n) (inc i)
	  (even? n) (recur (inc i) (bit-shift-right n 1))
	  :else (recur (inc i) (+ (* 3 n) 1)))))

(reduce (fn [[r n] i]
	  (let [n* (f i)]
	    (if (> n* n) [i n*] [r n])))
	[0 0] (range 1 (expt 10 6))) ; => [837799 525]

15.clj

http://projecteuler.net/index.php?section=problems&id=15

(defn fact [n] (reduce * 1 (range 1 n)))
(/ (fact 40) (fact 20) (fact 20)) ; => 1378465288200

16.clj

http://projecteuler.net/index.php?section=problems&id=16

(use '[clojure.contrib.math :only (expt)])
(reduce + (map (comp #(- % 48) int) (str (expt 2 1000)))) ; => 1366

17.clj

http://projecteuler.net/index.php?section=problems&id=17

(defn f [i]
  (condp = i
    0 "", 1 "one",  2 "two", 3 "three", 4 "four", 5 "five", 6 "six", 7 "seven", 8 "eight", 9 "nine"
    10 "ten", 11 "eleven", 12 "twelve", 13 "thirteen", 14 "fourteen", 15 "fifteen", 
    16 "sixteen", 17 "seventeen", 18 "eighteen", 19 "nineteen"))

(defn g [i j]
  (if (<= i 1)
    (f (+ (* i 10) j))
    (str 
     (condp = i
       2 "twenty", 3 "thirty", 4 "forty", 5 "fifty", 6 "sixty", 7 "seventy", 8 "eighty", 9 "ninety")
     (f j))))

(defn h [i j k]
  (if (and (zero? k) (zero? j))
    (str (f i) "hundred")
    (str (f i) "hundred" "and" (g j k))))

(defn dispatch [x]
  (condp = (count x)
    1 (apply f x)
    2 (apply g x)
    3 (apply h x)))

(+ (count "onethousand")
   (->> (range 1 1000)
	(map (comp count dispatch (partial map (comp #(- % 48) int)) str))
	(reduce + 0)))

18.clj

http://projecteuler.net/index.php?section=problems&id=18

(use '[clojure.contrib.duck-streams :only (read-lines)])
(use '[clojure.contrib.str-utils :only (re-split)])

(defn read-data [file]
  (map (fn [line] 
	 (map #(Integer/parseInt %) (re-split #"\s" line)))
       (read-lines file)))

(defn solve [coll]
  (apply max
	 (reduce (fn [acc row]
		     (map max 
			  (map + (next acc) row) 
			  (map + (reverse (next (reverse acc))) row)))
		 (first coll) (next coll))))

(solve (reverse (read-data "18.dat"))) ; => 1074

19.clj

http://projecteuler.net/index.php?section=problems&id=19

(import 'java.util.Calendar)

(defn calendar
  ([#^Calendar cal] (.clone cal)) 
  ([y m d]
     (doto (Calendar/getInstance)
       (. clear) 
       (. set y (dec m) d))))

;;instance作りまくっているけれど良いのかな？
(let [sun (Calendar/SUNDAY)]
  (->> (calendar 1901 1 1)
       (iterate (fn [cal] 
		  (doto (calendar cal)
		    (. add Calendar/MONTH 1))))
       (filter #(= sun (.get % (Calendar/DAY_OF_WEEK))))
       (take-while #(>= 2000 (.get % (Calendar/YEAR))))
       (count)))

20.clj

http://projecteuler.net/index.php?section=problems&id=20

(->> (reduce * (range 1 101))
     (str)
     (map (comp #(- % 48) int))
     (reduce +)) ; => 648