# HG changeset patch # User Steve Losh # Date 1545001352 18000 # Node ID 2a837c783fe744d3bd3cd2e563cfc11761398310 # Parent 5e5dd3fd5ae005c36c39e5d0cb96cf0579e886e2# Parent c19da8761e5752072bfbf856d95e855c6e938f51 Merge. diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 euler.asd --- 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"))))) diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 package.lisp --- 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)) diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 src/problems.lisp --- 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)))) diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 src/problems/001.lisp --- /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)))) + diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 src/problems/002.lisp --- /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)))) + diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 src/problems/003.lisp --- /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))) + diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 src/problems/004.lisp --- /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)))) + + diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 src/problems/005.lisp --- /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)))) diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 src/problems/006.lisp --- /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))))) + + + diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 src/utils.lisp --- 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) diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 vendor/make-quickutils.lisp --- 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 ) diff -r 5e5dd3fd5ae0 -r 2a837c783fe7 vendor/quickutils.lisp --- 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 ;;;;