# HG changeset patch # User Steve Losh # Date 1575058505 18000 # Node ID 7e8b6d68c8990be994f56ebb1b57a787c6a03f89 # Parent d5468dc3769d32405aa72e17ecc7cfa61e587c4c Update some old problems diff -r d5468dc3769d -r 7e8b6d68c899 .lispwords --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/.lispwords Fri Nov 29 15:15:05 2019 -0500 @@ -0,0 +1,1 @@ +(1 let-complex) diff -r d5468dc3769d -r 7e8b6d68c899 advent.asd --- a/advent.asd Sat Feb 02 14:41:20 2019 -0500 +++ b/advent.asd Fri Nov 29 15:15:05 2019 -0500 @@ -41,7 +41,5 @@ (:file "package") (:module "src" :serial t :components ((:file "utils") - #+later (:module "2017" :serial t - :components ((:file "number-spiral") - (:file "main"))) + (:file "number-spiral") (:auto-module "2018"))))) diff -r d5468dc3769d -r 7e8b6d68c899 package.lisp --- a/package.lisp Sat Feb 02 14:41:20 2019 -0500 +++ b/package.lisp Fri Nov 29 15:15:05 2019 -0500 @@ -5,6 +5,7 @@ :read-all :read-lines + :read-lines-of-words :read-lines-of-numbers-and-garbage :ensure-string diff -r d5468dc3769d -r 7e8b6d68c899 src/2017/day-01.lisp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/2017/day-01.lisp Fri Nov 29 15:15:05 2019 -0500 @@ -0,0 +1,19 @@ +(defpackage :advent/2017/01 #.cl-user::*advent-use*) +(in-package :advent/2017/01) + + +(define-problem (2017 1) (data read-line) + (iterate + (with digits = (map 'vector #'digit-char-p data)) + (for digit :in-vector digits) + (for prev :previous digit :initially (aref digits (1- (length digits)))) + (for j :modulo (length digits) :from (truncate (length digits) 2)) + (for next = (aref digits j)) + (when (= digit prev) (sum digit :into part1)) + (when (= digit next) (sum digit :into part2)) + (finally (return (values part1 part2))))) + +(1am:test test-2017/01 + (multiple-value-bind (part1 part2) (run) + (1am:is (= 1049 part1)) + (1am:is (= 1508 part2)))) diff -r d5468dc3769d -r 7e8b6d68c899 src/2017/day-02.lisp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/2017/day-02.lisp Fri Nov 29 15:15:05 2019 -0500 @@ -0,0 +1,27 @@ +(defpackage :advent/2017/02 #.cl-user::*advent-use*) +(in-package :advent/2017/02) + +(defun find-quotient (row) + (alexandria:map-permutations + (lambda (pair) + (multiple-value-bind (quotient remainder) + (truncate (first pair) (second pair)) + (when (zerop remainder) + (return-from find-quotient quotient)))) + row :length 2 :copy nil)) + +(defun checksum (row) + (multiple-value-bind (lo hi) (extrema #'< row) + (- hi lo))) + +(define-problem (2017 2) (data read-lines-of-numbers-and-garbage) + (iterate + (for row :in data) + (summing (checksum row) :into part1) + (summing (find-quotient row) :into part2) + (finally (return (values part1 part2))))) + +(1am:test test-2017/02 + (multiple-value-bind (part1 part2) (run) + (1am:is (= 53460 part1)) + (1am:is (= 282 part2)))) diff -r d5468dc3769d -r 7e8b6d68c899 src/2017/day-03.lisp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/2017/day-03.lisp Fri Nov 29 15:15:05 2019 -0500 @@ -0,0 +1,37 @@ +(defpackage :advent/2017/03 #.cl-user::*advent-use*) +(in-package :advent/2017/03) + +(defmacro let-complex (bindings &body body) + `(let* (,@(iterate (for (x y val) :in bindings) + (for v = (gensym)) + (collect `(,v ,val)) + (collect `(,x (realpart ,v))) + (collect `(,y (imagpart ,v))))) + ,@body)) + +(defun manhattan-distance (a b) + (let-complex ((ax ay a) + (bx by b)) + (+ (abs (- ax bx)) + (abs (- ay by))))) + +(defun neighbors (coord) + (iterate (for (dx dy) :within-radius 1 :skip-origin t) + (collect (+ coord (complex dx dy))))) + +(define-problem (2017 3) (data read) + (values + (manhattan-distance #c(0 0) (advent/spiral:number-coordinates data)) + (iterate + (with memory = (make-hash-table)) + (initially (setf (gethash #c(0 0) memory) 1)) + (for n :from 2) + (for coord = (advent/spiral:number-coordinates n)) + (for value = (summation (neighbors coord) :key (rcurry #'gethash memory 0))) + (finding value :such-that (> value data)) + (setf (gethash coord memory) value)))) + +(1am:test test-2017/03 + (multiple-value-bind (part1 part2) (run) + (1am:is (= 552 part1)) + (1am:is (= 330785 part2)))) diff -r d5468dc3769d -r 7e8b6d68c899 src/2017/day-04.lisp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/2017/day-04.lisp Fri Nov 29 15:15:05 2019 -0500 @@ -0,0 +1,45 @@ +(defpackage :advent/2017/04 #.cl-user::*advent-use*) +(in-package :advent/2017/04) + +(defun valid-hash-table-test-p (test) + (member test `(eq eql equal equalp ,#'eq ,#'eql ,#'equal ,#'equalp))) + +(defun ensure-boolean (value) + (if value t nil)) + +(defun contains-duplicates-p (sequence &key (test #'eql)) + (ensure-boolean (if (valid-hash-table-test-p test) + (iterate + (with seen = (make-hash-set :test test)) + (for value :in-whatever sequence) + (thereis (hset-contains-p seen value)) + (hset-insert! seen value)) + (etypecase sequence + (list (iterate + (for (value . remaining) :on sequence) + (thereis (position value remaining :test test)))) + (sequence + (iterate + (for i :from 0 :below (length sequence)) + (for value = (elt sequence i)) + (thereis (position value sequence :start (1+ i) :test test)))))))) + + +(defun anagramp (string1 string2) + (string= (sort (copy-seq string1) #'char<) + (sort (copy-seq string2) #'char<))) + +(define-problem (2017 4) (data read-lines-of-words) + (values (count-if (lambda (phrase) + (not (contains-duplicates-p phrase :test #'equal))) + data) + (count-if (lambda (phrase) + (not (contains-duplicates-p phrase :test #'anagramp))) + data))) + + +(1am:test test-2017/04 + (multiple-value-bind (part1 part2) (run) + (1am:is (= 337 part1)) + (1am:is (= 231 part2)))) + diff -r d5468dc3769d -r 7e8b6d68c899 src/number-spiral.lisp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/number-spiral.lisp Fri Nov 29 15:15:05 2019 -0500 @@ -0,0 +1,90 @@ +(defpackage :advent/spiral + (:use :cl :losh :iterate :advent.quickutils) + (:export :number-coordinates)) + +(in-package :advent/spiral) + +(defun layer-side-length (layer) + "Return the length of one side of `layer`." + (1+ (* 2 layer))) + +(defun layer-size (layer) + "Return the total size of a number spiral with a final layer of `layer`." + (square (layer-side-length layer))) + +(defun layer-for-number (number) + "Return the index of the layer containing `number`." + (ceiling (/ (1- (sqrt number)) 2))) + +(defun layer-start (layer) + "Return the smallest number in `layer`." + (if (zerop layer) + 1 + (1+ (layer-size (1- layer))))) + +(defun layer-leg-length (layer) + "Return the length of one \"leg\" of `layer`." + (1- (layer-side-length layer))) + + +(defun leg (layer number) + "Return the leg index and offset of `number` in `layer`." + (if (= 1 number) + (values 0 0) + (let ((idx (- number (layer-start layer))) + (legsize (layer-leg-length layer))) + (values (floor idx legsize) + (1+ (mod idx legsize)))))) + +(defun corner-coordinates (layer leg) + "Return the coordinates of the corner starting `leg` in `layer`. + + Leg | Corner + 0 | Bottom Right + 1 | Top Right + 2 | Top Left + 3 | Bottom Left + + " + + ;; 2 1 + ;; + ;; 3 0 + (ccase leg + (0 (complex layer (- layer))) + (1 (complex layer layer)) + (2 (complex (- layer) layer)) + (3 (complex (- layer) (- layer))))) + +(defun leg-direction (leg) + "Return the direction vector for the given `leg`. + " + ;; <-- + ;; 11110 + ;; | 2 0 ^ + ;; | 2 0 | + ;; v 2 0 | + ;; 23333 + ;; --> + (ccase leg + (0 (complex 0 1)) + (1 (complex -1 0)) + (2 (complex 0 -1)) + (3 (complex 1 0)))) + + +(defun number-coordinates (number) + (nest + ;; Find the layer the number falls in. + (let ((layer (layer-for-number number)))) + + ;; Find which leg of that layer it's in, and how far along the leg it is. + (multiple-value-bind (leg offset) (leg layer number)) + + ;; Find the coordinates of the leg's corner, and its direction vector. + (let ((corner (corner-coordinates layer leg)) + (direction (leg-direction leg)))) + + ;; Start at the corner and add the offset in the leg's direction to find the + ;; number's coordinates. + (+ corner (* direction offset)))) diff -r d5468dc3769d -r 7e8b6d68c899 src/old/2017/main.lisp --- a/src/old/2017/main.lisp Sat Feb 02 14:41:20 2019 -0500 +++ b/src/old/2017/main.lisp Fri Nov 29 15:15:05 2019 -0500 @@ -1,6 +1,7 @@ (in-package :advent) (named-readtables:in-readtable :interpol-syntax) +(asdf:test-system ) (define-problem (2017 1 1) (data read-file-of-digits) (iterate diff -r d5468dc3769d -r 7e8b6d68c899 src/old/2017/number-spiral.lisp --- a/src/old/2017/number-spiral.lisp Sat Feb 02 14:41:20 2019 -0500 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,90 +0,0 @@ -(defpackage :advent.spiral - (:use :cl :losh :iterate :advent.quickutils) - (:export :number-coordinates)) - -(in-package :advent.spiral) - -(defun layer-side-length (layer) - "Return the length of one side of `layer`." - (1+ (* 2 layer))) - -(defun layer-size (layer) - "Return the total size of a number spiral with a final layer of `layer`." - (square (layer-side-length layer))) - -(defun layer-for-number (number) - "Return the index of the layer containing `number`." - (ceiling (/ (1- (sqrt number)) 2))) - -(defun layer-start (layer) - "Return the smallest number in `layer`." - (if (zerop layer) - 1 - (1+ (layer-size (1- layer))))) - -(defun layer-leg-length (layer) - "Return the length of one \"leg\" of `layer`." - (1- (layer-side-length layer))) - - -(defun leg (layer number) - "Return the leg index and offset of `number` in `layer`." - (if (= 1 number) - (values 0 0) - (let ((idx (- number (layer-start layer))) - (legsize (layer-leg-length layer))) - (values (floor idx legsize) - (1+ (mod idx legsize)))))) - -(defun corner-coordinates (layer leg) - "Return the coordinates of the corner starting `leg` in `layer`. - - Leg | Corner - 0 | Bottom Right - 1 | Top Right - 2 | Top Left - 3 | Bottom Left - - " - - ;; 2 1 - ;; - ;; 3 0 - (ccase leg - (0 (complex layer (- layer))) - (1 (complex layer layer)) - (2 (complex (- layer) layer)) - (3 (complex (- layer) (- layer))))) - -(defun leg-direction (leg) - "Return the direction vector for the given `leg`. - " - ;; <-- - ;; 11110 - ;; | 2 0 ^ - ;; | 2 0 | - ;; v 2 0 | - ;; 23333 - ;; --> - (ccase leg - (0 (complex 0 1)) - (1 (complex -1 0)) - (2 (complex 0 -1)) - (3 (complex 1 0)))) - - -(defun number-coordinates (number) - (nest - ;; Find the layer the number falls in. - (let ((layer (layer-for-number number)))) - - ;; Find which leg of that layer it's in, and how far along the leg it is. - (multiple-value-bind (leg offset) (leg layer number)) - - ;; Find the coordinates of the leg's corner, and its direction vector. - (let ((corner (corner-coordinates layer leg)) - (direction (leg-direction leg)))) - - ;; Start at the corner and add the offset in the leg's direction to find the - ;; number's coordinates. - (+ corner (* direction offset)))) diff -r d5468dc3769d -r 7e8b6d68c899 src/utils.lisp --- a/src/utils.lisp Sat Feb 02 14:41:20 2019 -0500 +++ b/src/utils.lisp Fri Nov 29 15:15:05 2019 -0500 @@ -54,7 +54,6 @@ (defun read-numbers-from-line (line) (mapcar #'parse-integer (ppcre:all-matches-as-strings "-?\\d+" line))) - (defun read-and-collect (stream reader) (iterate (for value :in-stream stream :using reader) (collect value))) @@ -80,6 +79,10 @@ (when numbers (collect numbers)))) +(defun read-lines-of-words (stream) + (mapcar (lambda (line) (split-sequence:split-sequence #\space line)) + (read-lines stream))) + ;;;; Rings -------------------------------------------------------------------- (declaim (inline ring-prev ring-next ring-data))