--- a/euler.asd Tue Jul 31 16:18:33 2018 +0000
+++ b/euler.asd Sat Dec 15 17:25:12 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 Tue Jul 31 16:18:33 2018 +0000
+++ b/package.lisp Sat Dec 15 17:25:12 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 Tue Jul 31 16:18:33 2018 +0000
+++ b/src/problems.lisp Sat Dec 15 17:25:12 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)
@@ -2300,12 +2211,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 Sat Dec 15 17:25:12 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 Sat Dec 15 17:25:12 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 Sat Dec 15 17:25:12 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 Sat Dec 15 17:25:12 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 Sat Dec 15 17:25:12 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 Sat Dec 15 17:25:12 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 Tue Jul 31 16:18:33 2018 +0000
+++ b/src/utils.lisp Sat Dec 15 17:25:12 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))))))))
@@ -781,8 +795,6 @@
(define-modify-macro adjoinf (item &rest keyword-args) adjoin%)
-
-
(defun pythagorean-triplet-p (a b c)
(math a ^ 2 + b ^ 2 = c ^ 2))
@@ -974,7 +986,6 @@
(* precision (round number precision)))
-
;;;; A* Search ----------------------------------------------------------------
(defstruct path
state
--- a/vendor/make-quickutils.lisp Tue Jul 31 16:18:33 2018 +0000
+++ b/vendor/make-quickutils.lisp Sat Dec 15 17:25:12 2018 -0500
@@ -23,6 +23,7 @@
:read-file-into-string
:removef
:switch
+ :symb
:with-gensyms
)
--- a/vendor/quickutils.lisp Tue Jul 31 16:18:33 2018 +0000
+++ b/vendor/quickutils.lisp Sat Dec 15 17:25:12 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 ;;;;