From 070f6560bc16d6d27d304b0f37471cdf6c8c5ff8 Mon Sep 17 00:00:00 2001 From: Yann Herklotz Date: Tue, 14 Dec 2021 00:49:33 +0000 Subject: Add final solution to 03 --- src/03.lisp | 70 ++++++++++++++++++++++++++++++++++++------------------------- 1 file changed, 42 insertions(+), 28 deletions(-) (limited to 'src/03.lisp') diff --git a/src/03.lisp b/src/03.lisp index ae2f0bd..b1727fc 100644 --- a/src/03.lisp +++ b/src/03.lisp @@ -1,45 +1,59 @@ -(load "~/quicklisp/setup.lisp") -(ql:quickload "uiop") +(defun 03/parse-bin-char (x) (case x (#\1 1) (#\0 0))) -(defun get-file-lines (name) - (uiop:read-file-lines name)) - -(defun parse-bin-char (x) (case x (#\1 1) (#\0 0))) +(defun 03/parse-bin-char-inv (x) (case x (1 #\1) (0 #\0))) ;; Turn the input file into whatever form you will use for both parts ;; (get-file-lines) and (get-file-string) will be useful -(defun parse-input (input-file) - (mapcar (lambda (x) (mapcar #'parse-bin-char (coerce x 'list))) (get-file-lines input-file))) +(defun 03/parse-input-direct (input) + (mapcar (lambda (x) (mapcar #'03/parse-bin-char (coerce x 'list))) input)) + +(defun 03/parse-input (input-file) + (03/parse-input-direct (get-file-lines input-file))) ;; Loops through two item windows on input and counts each time the first is less than the second -(defun partial (func &rest args1) +(defun 03/partial (func &rest args1) (lambda (&rest args2) (apply func (append args1 args2)))) -(defun is-less (h l) +(defun 03/is-more (h l) (mapcar (lambda (x) (if (< x h) 0 1)) l)) -(defun not-list (l) +(defun 03/is-less (h l) + (mapcar (lambda (x) (if (>= x h) 0 1)) l)) + +(defun 03/not-list (l) (mapcar (lambda (x) (if (= x 0) 1 0)) l)) -(defun range (max &key (min 0) (step 1)) - (loop :for n :from (- max 1) :above (- min 1) :by step - :collect n)) +(defun 03/to-dec (l) + (parse-integer (coerce (mapcar #'03/parse-bin-char-inv l) 'string) :radix 2)) -(defun to-dec (l) - (apply #'+ (mapcar (lambda (a b) (* a (expt 2 b))) l (range (list-length l))))) +(defun 03/find-most-common (parsed-input) + (let ((half-length (/ (list-length parsed-input) 2))) + (03/is-more half-length (apply (03/partial #'mapcar #'+) parsed-input)))) -(defun part-a (parsed-input) - (let* ((half-length (/ (list-length parsed-input) 2)) - (l (is-less half-length (apply (partial #'mapcar #'+) parsed-input))) - (gamma (to-dec l)) - (epsilon (to-dec (not-list l)))) - (* epsilon gamma))) +(defun 03/find-least-common (parsed-input) + (let ((half-length (/ (list-length parsed-input) 2))) + (03/is-less half-length (apply (03/partial #'mapcar #'+) parsed-input)))) -;; Similar to part a, but with four item windows, comparing the sum of the first 3 with the next 3 -(defun part-b (parsed-input) - (loop for (w x y z) on parsed-input until (null z) if (< (+ w x y) (+ x y z)) count w)) +(defun 03/part-a (parsed-input) + (let* ((l (03/find-most-common parsed-input)) + (gamma (03/to-dec l)) + (epsilon (03/to-dec (03/not-list l)))) + (* epsilon gamma))) -(time (format t "part 1: ~a~%" (part-a (parse-input "../inputs/03.txt")))) -;;(time (format t "part 1: ~a~%" (part-a (parse-input "test.txt")))) -;;(time (format t "part 1: ~a~%" (part-b (parse-input "../inputs/01.txt")))) +(defun 03/recursive-b (f input out) + (if (member nil input) out + (let* ((common (car (funcall f input))) + (rest-tmp (mapcar #'cdr (remove-if-not (lambda (x) (equalp (car x) common)) input))) + (rest (if rest-tmp rest-tmp + (progn + (setf common (car (car input))) + (mapcar #'cdr input))))) + (03/recursive-b f rest (append out (list common)))))) + +(defun 03/part-b (parsed-input) + (* (03/to-dec (03/recursive-b #'03/find-most-common parsed-input nil)) + (03/to-dec (03/recursive-b #'03/find-least-common parsed-input nil)))) + +;;(time (format t "part 1: ~a~%" (03/part-a (03/parse-input "../inputs/03.txt")))) +;;(time (format t "part 2: ~a~%" (03/part-b (03/parse-input "../inputs/03.txt")))) -- cgit