Skip to content

Latest commit

 

History

History
190 lines (180 loc) · 6.23 KB

2019.04.org

File metadata and controls

190 lines (180 loc) · 6.23 KB

Day 04

Executing this code

If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:

  1. Starting slime (M-x slime)
  2. Typing C-c C-c in the block initialize.
  3. In the repl type (in-package :aoc-2019-04)
  4. Typing C-c C-c in the block answers

Initial stuffs

Packages to load

(unless (find-package :cl-ppcre)
  (ql:quickload "cl-ppcre"))
(unless (find-package :iterate)
  (ql:quickload "iterate"))
(unless (find-package :parseq)
  (ql:quickload "parseq"))
(unless (find-package :fiveam)
  (ql:quickload "fiveam"))

Create package for this day

<<packages>>
(defpackage :aoc-2019-04
  (:use :common-lisp
        :iterate
        :parseq
        :fiveam)
  (:export :problem-a
           :problem-b))
(in-package :aoc-2019-04)

Input

Today’s input is simple, it’s two numbers. I won’t bother with the parser, I’ll just return my input.

(defun read-input (file)
  (declare (ignore file))
  (list 231832 767346))
(defparameter *input*
  (read-input "input/04.txt"))

Part 1

I did this initially in emacs lisp because I didn’t have a common lisp install available. The following is a translation of that code, no need to preserve the elisp itself. This first version is slow.

(defun monotonic (password)
  "Returns T if PASSWORD is a monotonically increasing sequence. NIL
otherwise."
  (apply #'<= password))
(defun run-length (password)
  (let ((prev (first password))
        (run-length 1)
        (encoding nil))
    (iter (for current in (rest password))
          (finally (push run-length encoding))
          (cond ((= prev current)
                 (incf run-length))
                (t
                 (push run-length encoding)
                 (setf run-length 1)
                 (setf prev current))))
    encoding))
(defun p2-pairwise (password)
  (member 2 (run-length password)))
(defun p1-pairwise (password)
  (member-if #'(lambda (n) (>= n 2)) (run-length password)))
(defun split-password (password)
  (map 'list #'(lambda (c) (- (char-code c) (char-code #\0))) (format nil "~a" password)))
(defun test-password (password &optional (p2 nil))
  (let ((password (split-password password)))
    (and (monotonic password)
         (if p2 (p2-pairwise password)
             (p1-pairwise password)))))

(defun solve-a (&optional (min 100000) (max 999999))
  (iter (for password from min to max)
        (counting (test-password password))))

(defun solve-b (&optional (min 100000) (max 999999))
  (iter (for password from min to max)
        (counting (test-password password t))))

It turns out that the above is quite fast with a compiled language versus my elisp version, which took 50 seconds or so on my work PC to finish. It takes about 0.350 seconds for the worst case scenario (range of 100000 to 999999) on my computer.

Here is the improved version, it constructs only the monotonic sequences which minimizes the number of sequences to consider (reducing from 900k worst case to 3003).

(defun run-length (password)
  (iter (for current in (rest password))
        (for prev previous current initially (first password))
        (with run-length = 1)
        (with encoding = nil)
        (finally (push run-length encoding) (return encoding))
        (when (= prev current)
          (incf run-length))
        (unless (= prev current)
          (push run-length encoding)
          (setf run-length 1))))
(defun p2-pairwise (password)
  (member 2 (run-length password)))
(defun p1-pairwise (password)
  (member-if #'(lambda (n) (>= n 2)) (run-length password)))

(defun test-password (password &key (min 100000) (max 999999) (p2 nil))
  (let ((n (parse-integer (format nil "~{~a~}"  password))))
    (and (<= min n) (>= max n)
         (if p2 (p2-pairwise password)
             (p1-pairwise password)))))

(defun solve (&key (min 100000) (max 999999) (p2 nil))
  (iter outer
        (for a from (floor min 100000) to (floor max 100000))
        (iter (for b from a to 9)
              (iter (for c from b to 9)
                    (iter (for d from c to 9)
                          (iter (for e from d to 9)
                                (iter (for f from e to 9)
                                      (in outer
                                          (counting (test-password (list a b c d e f)
                                                                   :min min :max max :p2 p2))))))))))
(defun solve-a (min max)
  (solve :min min :max max))
(defun solve-b (min max)
  (solve :min min :max max :p2 t))

This improved one solves the worst case (100000 - 999999) problem in an average of 0.004 seconds on my computer. Much better.

(defun problem-a () (format t "Problem 04 A: ~a~%" (solve-a (first *input*) (second *input*))))

Part 2

(defun problem-b () (format t "Problem 04 B: ~a~%" (solve-b (first *input*) (second *input*))))

Putting it all together



<<read-input>>
<<better-solution>>


<<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)


Answer


Problem 04 A: 1330
Problem 04 B: 876



Test Cases


(def-suite aoc.2019.04)
(in-suite aoc.2019.04)

(run! 'aoc.2019.04)


Test Results


Thoughts