4b54adfbaf3d default tip

More refactoring
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Tue, 24 Dec 2019 13:50:19 -0500
parents 2a837c783fe7
children (none)
branches/tags default tip
files euler.asd package.lisp src/4d/polydivisible-numbers.lisp src/problems.lisp src/problems/007.lisp src/problems/008.lisp src/problems/009.lisp src/utils.lisp

Changes

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