# HG changeset patch # User Steve Losh # Date 1577213419 18000 # Node ID 4b54adfbaf3dfa294b9a4b16b6c975a43443eedc # Parent 2a837c783fe744d3bd3cd2e563cfc11761398310 More refactoring diff -r 2a837c783fe7 -r 4b54adfbaf3d euler.asd --- 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"))))) diff -r 2a837c783fe7 -r 4b54adfbaf3d package.lisp --- 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 )) diff -r 2a837c783fe7 -r 4b54adfbaf3d src/4d/polydivisible-numbers.lisp --- /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))))) + + diff -r 2a837c783fe7 -r 4b54adfbaf3d src/problems.lisp --- 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)))) diff -r 2a837c783fe7 -r 4b54adfbaf3d src/problems/007.lisp --- /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)) + + + diff -r 2a837c783fe7 -r 4b54adfbaf3d src/problems/008.lisp --- /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))))) diff -r 2a837c783fe7 -r 4b54adfbaf3d src/problems/009.lisp --- /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)))) + diff -r 2a837c783fe7 -r 4b54adfbaf3d src/utils.lisp --- 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))))