2a837c783fe7

Merge.
[view raw] [browse files]
author Steve Losh <steve@stevelosh.com>
date Sun, 16 Dec 2018 18:02:32 -0500
parents 5e5dd3fd5ae0 (current diff) c19da8761e57 (diff)
children 4b54adfbaf3d
branches/tags (none)
files src/problems.lisp src/utils.lisp

Changes

--- a/euler.asd	Thu Nov 01 19:44:26 2018 -0400
+++ b/euler.asd	Sun Dec 16 18:02:32 2018 -0500
@@ -1,3 +1,14 @@
+(defclass auto-module (module) ())
+
+(defmethod component-children ((self auto-module))
+  (mapcar (lambda (p) (make-instance 'cl-source-file :type "lisp"
+                        :pathname p
+                        :name (pathname-name p)
+                        :parent (component-parent self)))
+          (directory-files (component-pathname self)
+                           (make-pathname :directory nil :name *wild* :type "lisp"))))
+
+
 (asdf:defsystem :euler
   :name "euler"
   :description "Project Euler solutions."
@@ -13,11 +24,11 @@
                :1am
                :anaphora
                :cl-pcg
-               :cl-strings
                :iterate
                :local-time
                :losh
                :pileup
+               :str
 
                )
 
@@ -32,5 +43,6 @@
                              (:file "utils")
                              (:file "hungarian")
                              (:file "problems")
-                             (:file "poker")))))
+                             (:file "poker")
+                             (:auto-module "problems")))))
 
--- a/package.lisp	Thu Nov 01 19:44:26 2018 -0400
+++ b/package.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -1,12 +1,15 @@
 (defpackage :euler
-  (:use
-    :cl
-    :iterate
-    :losh
-    :euler.quickutils)
-  (:import-from :1am :is)
-  (:shadowing-import-from :1am :test)
-  (:export :run-tests))
+  (:use :cl :iterate :losh :euler.quickutils)
+  (:export
+    :*use*
+    :run-tests
+
+    :define-problem
+
+    :prime-factorization
+    :irange
+
+    ))
 
 (defpackage :euler.poker
   (:use
@@ -18,11 +21,13 @@
     :euler.quickutils))
 
 (defpackage :euler.hungarian
-  (:use
-    :cl
-    :iterate
-    :losh
-    :euler
-    :euler.quickutils)
+  (:use :cl :euler :iterate :losh :euler.quickutils)
   (:export
     :find-minimal-assignment))
+
+(defparameter euler:*use* '(:use
+                             :cl
+                             :euler
+                             :iterate
+                             :losh
+                             :euler.quickutils))
--- a/src/problems.lisp	Thu Nov 01 19:44:26 2018 -0400
+++ b/src/problems.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -1,94 +1,5 @@
 (in-package :euler)
 
-(defun problem-1 ()
-  ;; If we list all the natural numbers below 10 that are multiples of 3 or 5,
-  ;; we get 3, 5, 6 and 9. The sum of these multiples is 23.
-  ;;
-  ;; Find the sum of all the multiples of 3 or 5 below 1000.
-  (iterate (for i :from 1 :below 1000)
-           (when (or (dividesp i 3)
-                     (dividesp i 5))
-             (summing i))))
-
-(defun problem-2 ()
-  ;; Each new term in the Fibonacci sequence is generated by adding the previous
-  ;; two terms. By starting with 1 and 2, the first 10 terms will be:
-  ;;
-  ;;     1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
-  ;;
-  ;; By considering the terms in the Fibonacci sequence whose values do not
-  ;; exceed four million, find the sum of the even-valued terms.
-  (iterate (for n :in-fibonacci t)
-           (while (<= n 4000000))
-           (when (evenp n)
-             (summing n))))
-
-(defun problem-3 ()
-  ;; The prime factors of 13195 are 5, 7, 13 and 29.
-  ;;
-  ;; What is the largest prime factor of the number 600851475143?
-  (apply #'max (prime-factorization 600851475143)))
-
-(defun problem-4 ()
-  ;; A palindromic number reads the same both ways. The largest palindrome made
-  ;; from the product of two 2-digit numbers is 9009 = 91 × 99.
-  ;;
-  ;; Find the largest palindrome made from the product of two 3-digit numbers.
-  (iterate
-    ;; We COULD brute force this, but it's more fun to do it smartly.
-    (with result = 0)
-    (for i :from 999 :downto 100)
-    (iterate (for j :from i :downto 100)
-             (for product = (* i j))
-             ;; Because we're counting down, we can break in this inner loop as
-             ;; soon as our products drop below the current maximum.
-             (while (>= product (or result 0)))
-             (when (palindromep product)
-               (setf result product)))
-    (finally (return result))))
-
-(defun problem-5 ()
-  ;; 2520 is the smallest number that can be divided by each of the numbers from
-  ;; 1 to 10 without any remainder.
-  ;;
-  ;; What is the smallest positive number that is evenly divisible by all of the
-  ;; numbers from 1 to 20?
-  (iterate
-    ;; all numbers are divisible by 1 and we can skip checking everything <= 10
-    ;; because:
-    ;;
-    ;; anything divisible by 12 is automatically divisible by 2
-    ;; anything divisible by 12 is automatically divisible by 3
-    ;; anything divisible by 12 is automatically divisible by 4
-    ;; anything divisible by 15 is automatically divisible by 5
-    ;; anything divisible by 12 is automatically divisible by 6
-    ;; anything divisible by 14 is automatically divisible by 7
-    ;; anything divisible by 16 is automatically divisible by 8
-    ;; anything divisible by 18 is automatically divisible by 9
-    ;; anything divisible by 20 is automatically divisible by 10
-    (with divisors = (range 11 20))
-    (for i :from 20 :by 20) ; it must be divisible by 20
-    (finding i :such-that (every (curry #'dividesp i) divisors))))
-
-(defun problem-6 ()
-  ;; The sum of the squares of the first ten natural numbers is,
-  ;;   1² + 2² + ... + 10² = 385
-  ;;
-  ;; The square of the sum of the first ten natural numbers is,
-  ;;   (1 + 2 + ... + 10)² = 55² = 3025
-  ;;
-  ;; Hence the difference between the sum of the squares of the first ten
-  ;; natural numbers and the square of the sum is 3025 − 385 = 2640.
-  ;;
-  ;; Find the difference between the sum of the squares of the first one hundred
-  ;; natural numbers and the square of the sum.
-  (flet ((sum-of-squares (to)
-           (summation (irange 1 to :key #'square)))
-         (square-of-sum (to)
-           (square (summation (irange 1 to)))))
-    (abs (- (sum-of-squares 100) ; apparently it wants the absolute value
-            (square-of-sum 100)))))
-
 (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.
@@ -1157,7 +1068,7 @@
   ;; How many hands does Player 1 win?
   (iterate (for line :in-file "data/054-poker.txt" :using #'read-line)
            (for cards = (mapcar #'euler.poker::parse-card
-                                (cl-strings:split line #\space)))
+                                (str:split #\space line)))
            (for p1 = (take 5 cards))
            (for p2 = (drop 5 cards))
            (counting (euler.poker::poker-hand-beats-p p1 p2))))
@@ -1300,7 +1211,7 @@
                  read-all-from-string))
          (raw-words (-<> "/usr/share/dict/words"
                       read-file-into-string
-                      (cl-strings:split <> #\newline)
+                      (str:split #\newline <>)
                       (mapcar #'string-downcase <>)))
          (words (make-hash-set :test 'equal :initial-contents raw-words)))
     (labels
@@ -1314,7 +1225,7 @@
            (-<> (apply-cipher keyword)
              (stringify <>)
              (string-downcase <>)
-             (cl-strings:split <>)
+             (str:words <>)
              (remove-if-not (curry #'hset-contains-p words) <>)
              length))
          (answer (keyword)
@@ -2354,12 +2265,6 @@
 
 
 ;;;; Tests --------------------------------------------------------------------
-(test p1 (is (= 233168 (problem-1))))
-(test p2 (is (= 4613732 (problem-2))))
-(test p3 (is (= 6857 (problem-3))))
-(test p4 (is (= 906609 (problem-4))))
-(test p5 (is (= 232792560 (problem-5))))
-(test p6 (is (= 25164150 (problem-6))))
 (test p7 (is (= 104743 (problem-7))))
 (test p8 (is (= 23514624000 (problem-8))))
 (test p9 (is (= 31875000 (problem-9))))
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/001.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -0,0 +1,14 @@
+(defpackage :euler/001 #.euler:*use*)
+(in-package :euler/001)
+
+;; If we list all the natural numbers below 10 that are multiples of 3 or 5, we
+;; get 3, 5, 6 and 9. The sum of these multiples is 23.
+;;
+;; Find the sum of all the multiples of 3 or 5 below 1000.
+
+(define-problem (1 233168)
+  (iterate (for i :from 1 :below 1000)
+           (when (or (dividesp i 3)
+                     (dividesp i 5))
+             (summing i))))
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/002.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -0,0 +1,17 @@
+(defpackage :euler/002 #.euler:*use*)
+(in-package :euler/002)
+
+;; Each new term in the Fibonacci sequence is generated by adding the previous
+;; two terms. By starting with 1 and 2, the first 10 terms will be:
+;;
+;;     1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
+;;
+;; By considering the terms in the Fibonacci sequence whose values do not exceed
+;; four million, find the sum of the even-valued terms.
+
+(define-problem (2 4613732)
+  (iterate (for n :in-fibonacci t)
+           (while (<= n 4000000))
+           (when (evenp n)
+             (summing n))))
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/003.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -0,0 +1,10 @@
+(defpackage :euler/003 #.euler:*use*)
+(in-package :euler/003)
+
+;; The prime factors of 13195 are 5, 7, 13 and 29.
+;;
+;; What is the largest prime factor of the number 600851475143?
+
+(define-problem (3 6857)
+  (apply #'max (prime-factorization 600851475143)))
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/004.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -0,0 +1,23 @@
+(defpackage :euler/004 #.euler:*use*)
+(in-package :euler/004)
+
+;; A palindromic number reads the same both ways. The largest palindrome made
+;; from the product of two 2-digit numbers is 9009 = 91 × 99.
+;;
+;; Find the largest palindrome made from the product of two 3-digit numbers.
+
+(define-problem (4 906609)
+  (iterate
+    ;; We COULD brute force this, but it's more fun to do it smartly.
+    (with result = 0)
+    (for i :from 999 :downto 100)
+    (iterate (for j :from i :downto 100)
+             (for product = (* i j))
+             ;; Because we're counting down, we can break in this inner loop as
+             ;; soon as our products drop below the current maximum.
+             (while (>= product (or result 0)))
+             (when (palindromep product)
+               (setf result product)))
+    (finally (return result))))
+
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/005.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -0,0 +1,27 @@
+(defpackage :euler/005 #.euler:*use*)
+(in-package :euler/005)
+
+
+;; 2520 is the smallest number that can be divided by each of the numbers from
+;; 1 to 10 without any remainder.
+;;
+;; What is the smallest positive number that is evenly divisible by all of the
+;; numbers from 1 to 20?
+
+(define-problem (5 232792560)
+  (iterate
+    ;; all numbers are divisible by 1 and we can skip checking everything <= 10
+    ;; because:
+    ;;
+    ;; anything divisible by 12 is automatically divisible by 2
+    ;; anything divisible by 12 is automatically divisible by 3
+    ;; anything divisible by 12 is automatically divisible by 4
+    ;; anything divisible by 15 is automatically divisible by 5
+    ;; anything divisible by 12 is automatically divisible by 6
+    ;; anything divisible by 14 is automatically divisible by 7
+    ;; anything divisible by 16 is automatically divisible by 8
+    ;; anything divisible by 18 is automatically divisible by 9
+    ;; anything divisible by 20 is automatically divisible by 10
+    (with divisors = (range 11 20))
+    (for i :from 20 :by 20) ; it must be divisible by 20
+    (finding i :such-that (every (curry #'dividesp i) divisors))))
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/problems/006.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -0,0 +1,25 @@
+(defpackage :euler/006 #.euler:*use*)
+(in-package :euler/006)
+
+;; The sum of the squares of the first ten natural numbers is,
+;;   1² + 2² + ... + 10² = 385
+;;
+;; The square of the sum of the first ten natural numbers is,
+;;   (1 + 2 + ... + 10)² = 55² = 3025
+;;
+;; Hence the difference between the sum of the squares of the first ten natural
+;; numbers and the square of the sum is 3025 − 385 = 2640.
+;;
+;; Find the difference between the sum of the squares of the first one hundred
+;; natural numbers and the square of the sum.
+
+(define-problem (6 25164150)
+  (flet ((sum-of-squares (to)
+           (summation (irange 1 to) :key #'square))
+         (square-of-sum (to)
+           (square (summation (irange 1 to)))))
+    (abs (- (sum-of-squares 100) ; apparently it wants the absolute value
+            (square-of-sum 100)))))
+
+
+
--- a/src/utils.lisp	Thu Nov 01 19:44:26 2018 -0400
+++ b/src/utils.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -1,5 +1,19 @@
 (in-package :euler)
 
+;;;; Problems -----------------------------------------------------------------
+(defun run-tests ()
+  (1am:run))
+
+(defmacro define-problem ((number &optional solution) &body body)
+  (let ((name (symb 'problem- number)))
+    `(progn
+       (defun ,name () ,@body)
+       ,@(when solution
+           `((1am:test ,(symb 'test- name)
+               (1am:is (= ,solution (,name))))))
+       ',name)))
+
+
 ;;;; Iterate ------------------------------------------------------------------
 (defmacro-driver (FOR var ITERATING function SEED value &optional
                   INCLUDE-SEED include-seed?)
@@ -164,7 +178,7 @@
                     ,line%)
                   (parse-line (l)
                     (map ,result-type% ,key%
-                         (cl-strings:split l ,delimiter%))))
+                         (str:split ,delimiter% l))))
            (,kwd ,var :next (parse-line (next-line))))))))
 
 (defmacro-driver (FOR var IN-FAREY-SEQUENCE n)
--- a/vendor/make-quickutils.lisp	Thu Nov 01 19:44:26 2018 -0400
+++ b/vendor/make-quickutils.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -23,6 +23,7 @@
                :read-file-into-string
                :removef
                :switch
+               :symb
                :with-gensyms
 
                )
--- a/vendor/quickutils.lisp	Thu Nov 01 19:44:26 2018 -0400
+++ b/vendor/quickutils.lisp	Sun Dec 16 18:02:32 2018 -0500
@@ -2,7 +2,7 @@
 ;;;; See http://quickutil.org for details.
 
 ;;;; To regenerate:
-;;;; (qtlc:save-utils-as "quickutils.lisp" :utilities '(:COMPOSE :COPY-ARRAY :CURRY :DEFINE-CONSTANT :EMPTYP :ENSURE-BOOLEAN :ENSURE-FUNCTION :ENSURE-GETHASH :EQUIVALENCE-CLASSES :MAP-COMBINATIONS :MAP-PERMUTATIONS :MAXF :MINF :N-GRAMS :RANGE :RCURRY :READ-FILE-INTO-STRING :REMOVEF :SWITCH :WITH-GENSYMS) :ensure-package T :package "EULER.QUICKUTILS")
+;;;; (qtlc:save-utils-as "quickutils.lisp" :utilities '(:COMPOSE :COPY-ARRAY :CURRY :DEFINE-CONSTANT :EMPTYP :ENSURE-BOOLEAN :ENSURE-FUNCTION :ENSURE-GETHASH :EQUIVALENCE-CLASSES :MAP-COMBINATIONS :MAP-PERMUTATIONS :MAXF :MINF :N-GRAMS :RANGE :RCURRY :READ-FILE-INTO-STRING :REMOVEF :SWITCH :SYMB :WITH-GENSYMS) :ensure-package T :package "EULER.QUICKUTILS")
 
 (eval-when (:compile-toplevel :load-toplevel :execute)
   (unless (find-package "EULER.QUICKUTILS")
@@ -23,7 +23,8 @@
                                          :WITH-OPEN-FILE* :WITH-INPUT-FROM-FILE
                                          :READ-FILE-INTO-STRING :REMOVEF
                                          :STRING-DESIGNATOR :WITH-GENSYMS
-                                         :EXTRACT-FUNCTION-NAME :SWITCH))))
+                                         :EXTRACT-FUNCTION-NAME :SWITCH :MKSTR
+                                         :SYMB))))
 (eval-when (:compile-toplevel :load-toplevel :execute)
   (defun make-gensym-list (length &optional (x "G"))
     "Returns a list of `length` gensyms, each generated as if with a call to `make-gensym`,
@@ -543,11 +544,28 @@
     "Like `switch`, but signals a continuable error if no key matches."
     (generate-switch-body whole object clauses test key '(cerror "Return NIL from CSWITCH.")))
   
+
+  (defun mkstr (&rest args)
+    "Receives any number of objects (string, symbol, keyword, char, number), extracts all printed representations, and concatenates them all into one string.
+
+Extracted from _On Lisp_, chapter 4."
+    (with-output-to-string (s)
+      (dolist (a args) (princ a s))))
+  
+
+  (defun symb (&rest args)
+    "Receives any number of objects, concatenates all into one string with `#'mkstr` and converts them to symbol.
+
+Extracted from _On Lisp_, chapter 4.
+
+See also: `symbolicate`"
+    (values (intern (apply #'mkstr args))))
+  
 (eval-when (:compile-toplevel :load-toplevel :execute)
   (export '(compose copy-array curry define-constant emptyp ensure-boolean
             ensure-function ensure-gethash equivalence-classes map-combinations
             map-permutations maxf minf n-grams range rcurry
-            read-file-into-string removef switch eswitch cswitch with-gensyms
-            with-unique-names)))
+            read-file-into-string removef switch eswitch cswitch symb
+            with-gensyms with-unique-names)))
 
 ;;;; END OF quickutils.lisp ;;;;