--- a/euler.asd Sun Dec 16 18:02:32 2018 -0500
+++ b/euler.asd Tue Dec 24 13:50:19 2019 -0500
@@ -27,6 +27,7 @@
:iterate
:local-time
:losh
+ :lparallel
:pileup
:str
@@ -42,7 +43,6 @@
(:file "math")
(:file "utils")
(:file "hungarian")
- (:file "problems")
(:file "poker")
(:auto-module "problems")))))
--- a/package.lisp Sun Dec 16 18:02:32 2018 -0500
+++ b/package.lisp Tue Dec 24 13:50:19 2019 -0500
@@ -6,8 +6,11 @@
:define-problem
+ :irange
+ :nth-prime
+ :palindromep
:prime-factorization
- :irange
+ :pythagorean-triplets-of-perimeter
))
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/4d/polydivisible-numbers.lisp Tue Dec 24 13:50:19 2019 -0500
@@ -0,0 +1,56 @@
+(defpackage :euler/4d/polydivisible-numbers #.euler:*use*)
+(in-package :euler/4d/polydivisible-numbers)
+
+(setf lparallel:*kernel* (lparallel:make-kernel 30))
+
+(deftype radix ()
+ '(integer 2 64))
+
+(deftype digit ()
+ '(integer 1 63))
+
+(deftype digit-set ()
+ '(unsigned-byte 63))
+
+(defun make-digits (radix)
+ (1- (expt 2 (1- radix))))
+
+(defun-inline remove-digit (d digits)
+ (declare (optimize speed)
+ (type digit d)
+ (type digit-set digits))
+ (dpb 0 (byte 1 (1- d)) digits))
+
+(defun new-candidates (radix candidate remaining)
+ (declare (optimize speed)
+ (type radix radix)
+ (type digit-set remaining)
+ (type (integer 0) candidate))
+ (iterate
+ (declare (iterate:declare-variables)
+ (type (or (integer 0) digit) d)
+ (type digit-set n more))
+ (for d :from 1)
+ (for n :first remaining :then more)
+ (for (values more d?) = (truncate n 2))
+ (unless (zerop d?)
+ (collect (cons (+ (* radix candidate) d)
+ (remove-digit d remaining))))
+ (until (zerop more))))
+
+(defun find-polydivisible-numbers (radix)
+ (labels ((recur (n candidate remaining)
+ (when (or (zerop n) (dividesp candidate n))
+ (if (= n (1- radix))
+ (list candidate)
+ (funcall (if (< n 2)
+ #'lparallel:pmapcan
+ ;; #'mapcan
+ #'mapcan
+ )
+ (lambda (next)
+ (recur (1+ n) (car next) (cdr next)))
+ (new-candidates radix candidate remaining))))))
+ (cons radix (recur 0 0 (make-digits radix)))))
+
+
--- a/src/problems.lisp Sun Dec 16 18:02:32 2018 -0500
+++ b/src/problems.lisp Tue Dec 24 13:50:19 2019 -0500
@@ -1,36 +1,5 @@
(in-package :euler)
-(defun problem-7 ()
- ;; By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see
- ;; that the 6th prime is 13.
- ;;
- ;; What is the 10 001st prime number?
- (nth-prime 10001))
-
-(defun problem-8 ()
- ;; The four adjacent digits in the 1000-digit number that have the greatest
- ;; product are 9 × 9 × 8 × 9 = 5832.
- ;;
- ;; Find the thirteen adjacent digits in the 1000-digit number that have the
- ;; greatest product. What is the value of this product?
- (let ((digits (map 'list #'digit-char-p
- (remove #\newline
- (read-file-into-string "data/008-number.txt")))))
- (iterate (for window :in (n-grams 13 digits))
- (maximize (apply #'* window)))))
-
-(defun problem-9 ()
- ;; A Pythagorean triplet is a set of three natural numbers, a < b < c, for
- ;; which:
- ;;
- ;; a² + b² = c²
- ;;
- ;; For example, 3² + 4² = 9 + 16 = 25 = 5².
- ;;
- ;; There exists exactly one Pythagorean triplet for which a + b + c = 1000.
- ;; Find the product abc.
- (product (first (pythagorean-triplets-of-perimeter 1000))))
-
(defun problem-10 ()
;; The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
;; Find the sum of all the primes below two million.
@@ -2265,9 +2234,6 @@
;;;; Tests --------------------------------------------------------------------
-(test p7 (is (= 104743 (problem-7))))
-(test p8 (is (= 23514624000 (problem-8))))
-(test p9 (is (= 31875000 (problem-9))))
(test p10 (is (= 142913828922 (problem-10))))
(test p11 (is (= 70600674 (problem-11))))
(test p12 (is (= 76576500 (problem-12))))
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/007.lisp Tue Dec 24 13:50:19 2019 -0500
@@ -0,0 +1,13 @@
+(defpackage :euler/007 #.euler:*use*)
+(in-package :euler/007)
+
+;; By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see
+;; that the 6th prime is 13.
+;;
+;; What is the 10 001st prime number?
+
+(define-problem (7 104743)
+ (nth-prime 10001))
+
+
+
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/008.lisp Tue Dec 24 13:50:19 2019 -0500
@@ -0,0 +1,15 @@
+(defpackage :euler/008 #.euler:*use*)
+(in-package :euler/008)
+
+;; The four adjacent digits in the 1000-digit number that have the greatest
+;; product are 9 × 9 × 8 × 9 = 5832.
+;;
+;; Find the thirteen adjacent digits in the 1000-digit number that have the
+;; greatest product. What is the value of this product?
+
+(define-problem (8 23514624000 )
+ (let ((digits (map 'list #'digit-char-p
+ (remove #\newline
+ (read-file-into-string "data/008-number.txt")))))
+ (iterate (for window :in (n-grams 13 digits))
+ (maximize (apply #'* window)))))
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/009.lisp Tue Dec 24 13:50:19 2019 -0500
@@ -0,0 +1,16 @@
+(defpackage :euler/009 #.euler:*use*)
+(in-package :euler/009)
+
+;; A Pythagorean triplet is a set of three natural numbers, a < b < c, for
+;; which:
+;;
+;; a² + b² = c²
+;;
+;; For example, 3² + 4² = 9 + 16 = 25 = 5².
+;;
+;; There exists exactly one Pythagorean triplet for which a + b + c = 1000.
+;; Find the product abc.
+
+(define-problem (9 31875000)
+ (product (first (pythagorean-triplets-of-perimeter 1000))))
+
--- a/src/utils.lisp Sun Dec 16 18:02:32 2018 -0500
+++ b/src/utils.lisp Tue Dec 24 13:50:19 2019 -0500
@@ -830,7 +830,9 @@
(defun pythagorean-triplet-p (a b c)
- (math a ^ 2 + b ^ 2 = c ^ 2))
+ (= (+ (square a)
+ (square b))
+ (square c)))
(defun pythagorean-triplets-of-perimeter (p)
(iterate
@@ -840,8 +842,7 @@
(for a :from 1 :below (min c (- p c)))
(for b = (- p c a))
(when (pythagorean-triplet-p a b c)
- (adjoinf result (sort< (list a b c))
- :test #'equal)))
+ (adjoinf result (sort< (list a b c)) :test #'equal)))
(finally (return result))))