Skip to content

Latest commit

 

History

History
166 lines (162 loc) · 5.39 KB

2019.06.org

File metadata and controls

166 lines (162 loc) · 5.39 KB

Day 06

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-06)
  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-06
  (:use :common-lisp
        :iterate
        :parseq
        :fiveam)
  (:export :problem-a
           :problem-b))
(in-package :aoc-2019-06)

Input

The input is a collection of orbits (directional pairs). I’m going to split the lines on ).

(defun read-input (file)
  (iter (for line in-file file using #'read-line)
        (collect (cl-ppcre:split "\\)" line))))
(defparameter *input*
  (make-graph (read-input "input/06.txt")))

Part 1

Tally the number of direct orbits and indirect orbits. A direct orbit is, well, exactly the information in the input. The indirect is the distance from COM less one.

(defun make-graph (orbits)
  (let ((graph (make-hash-table :test 'equal)))
    (iter (for (l r) in orbits)
          (setf (gethash r graph) l))
    graph))
(defun count-direct (graph)
  (iter (for (k v) in-hashtable graph)
        (sum 1)))

(defun count-indirect (graph)
  (labels ((depth (object acc)
             (if (string= object "COM") acc
                 (depth (gethash object graph) (1+ acc)))))
    (iter (for (l r) in-hashtable graph)
          (sum (depth r 0)))))
(defun problem-a () (format t "Problem 06 A: ~a~%" (+ (count-direct *input*)
                                                      (count-indirect *input*))))

Part 2

Part 2 requires finding the minimum number of transfers to get from where YOU is orbit to where SAN is in orbit.

(defun transfers (orbits)
  (let ((from (gethash "YOU" orbits))
        (to (gethash "SAN" orbits)))
    (labels ((depth (object acc)
               (if (string= object "COM") acc
                   (depth (gethash object orbits) (1+ acc))))
             (common-root (a b)
               (let ((da (depth a 0))
                     (db (depth b 0)))
                 (cond ((equal a b) a)
                       ((< da db) (common-root a (gethash b orbits)))
                       ((> da db) (common-root b (gethash a orbits)))
                       ((= da db) (common-root (gethash a orbits) (gethash b orbits)))))))
      (- (+ (depth from 0) (depth to 0))
         (* 2 (depth (common-root from to) 0))))))

This morning I realized I’d made a mistake above. Not with the answer, but the algorithm. I’m calculating the depth repeatedly at each step, that’s not needed and adds to the time complexity.

(defun transfers (orbits)
  (let* ((from (gethash "YOU" orbits))
         (to (gethash "SAN" orbits)))
    (labels ((depth (object &optional (acc 0))
               (if (string= object "COM") acc
                   (depth (gethash object orbits) (1+ acc))))
             (common-root (a b da db)
               (cond ((equal a b) a)
                     ((< da db) (common-root a (gethash b orbits) da (1- db)))
                     ((> da db) (common-root (gethash a orbits) b (1- da) db))
                     ((= da db) (common-root (gethash a orbits) (gethash b orbits) (1- da) (1- db))))))
      (let ((depth-from (depth from 0))
            (depth-to (depth to 0)))
        (- (+ depth-from depth-to)
           (* 2 (depth (common-root from to depth-from depth-to) 0)))))))

Now it’s a $O(N)$ algorithm where $N$ is the depth of the tree.

(defun problem-b () (format t "Problem 06 B: ~a~%" (transfers *input*)))

Putting it all together



<<read-input>>
<<make-graph>>
<<input>>
<<count-orbits>>
;; <<transfers>>


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


Answer


Problem 06 A: 278744
Problem 06 B: 475



Test Cases


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

(run! 'aoc.2019.06)


Test Results


Thoughts