#+STARTUP: indent contents
#+OPTIONS: num:nil toc:nil
* Day 14
** 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][initialize]].
3. In the repl type =(in-package :aoc-2018-14)=
4. Typing =C-c C-c= in the block [[answers][answers]]
** Initial stuffs
*** Packages to load
#+NAME: packages
#+BEGIN_SRC lisp :results silent
(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"))
#+END_SRC
*** Create package for this day
#+NAME: initialize
#+BEGIN_SRC lisp :noweb yes :results silent
<<packages>>
(defpackage :aoc-2018-14
(:use :common-lisp
:iterate
:parseq
:fiveam)
(:export :problem-a
:problem-b))
(in-package :aoc-2018-14)
#+END_SRC
** Input
The input is a string of digits to be interpreted in one of two ways:
An integer count, or a list of numbers.
#+NAME: read-input
#+NAME: input
#+BEGIN_SRC lisp :noweb yes :results silent
(defparameter *input* (list 286051 (list 2 8 6 0 5 1)))
#+END_SRC
** Part 1
I wrote this in emacs lisp while at the office today. Took about 5
minutes to write the first version (with lists) and then abandon
it. About 10 more minutes throughout the day to learn enough about
using vectors in emacs lisp to get this working right.
#+NAME: next-state
#+BEGIN_SRC elisp
(require 'cl)
(defun next-recipes-vector (recipes positions)
(let* ((p1 (car positions))
(p2 (cadr positions))
(next (+ (aref recipes p1) (aref recipes p2)))
(next-1 (floor (/ next 10)))
(next-2 (mod next 10)))
(when (not (= 0 next-1))
(setf (aref recipes n) next-1)
(incf n))
(incf n)
(setf (aref recipes (1- n)) next-2)
recipes))
(defun next-positions-vector (recipes positions)
(let* ((p1 (car positions))
(p2 (cadr positions)))
(list (mod (+ p1 1 (aref recipes p1)) n)
(mod (+ p2 1 (aref recipes p2)) n))))
#+END_SRC
#+BEGIN_SRC elisp :results output :exports both :noweb yes
<<next-state>>
(defun solve-a (target)
(let ((recipes (make-vector (+ target 12) 0))
(positions '(0 1))
(n 2))
(setf (aref recipes 0) 3)
(setf (aref recipes 1) 7)
(print (current-time-string))
(loop while (< n (+ target 11))
for i from 0
do (progn
(setq recipes (next-recipes-vector recipes positions))
(setq positions (next-positions-vector recipes positions))))
(print (current-time-string))
(subseq recipes target (+ target 10))))
(print (solve-a 286051))
#+END_SRC
#+RESULTS:
:
: "Fri Dec 14 17:12:07 2018"
:
: "Fri Dec 14 17:12:11 2018"
:
: [2 1 1 1 1 1 3 6 7 8]
#+NAME: problem-a
#+BEGIN_SRC lisp :noweb yes :results silent
(defun problem-a () (format t "Problem 14 A: ~a~%" (identity *input*)))
#+END_SRC
** Part 2
Now we have to find at what index the sequence interpretation of the input occurs.
#+BEGIN_SRC elisp :results output :exports both :noweb yes
<<next-state>>
(defun solve-b (target iterations)
(let ((recipes (make-vector (+ iterations 10) 0))
(positions '(0 1))
(n 2))
(setf (aref recipes 0) 3)
(setf (aref recipes 1) 7)
(loop while (< n iterations)
do (progn
(setq recipes (next-recipes-vector recipes positions))
(setq positions (next-positions-vector recipes positions)))
do (when (> n (length target))
(if (search target recipes :start2 (- n (length target) 1) :end2 n)
(return (search target recipes :start2 (- n (length target) 1) :end2 n)))))))
(print (solve-b [5 1 5 8 9] 10000)) ;; 9
(print (solve-b [0 1 2 4 5] 10000)) ;; 5
(print (solve-b [9 2 5 1 0] 10000)) ;; 18
(print (solve-b [5 9 4 1 4] 10000)) ;; 2018
(print (current-time-string))
(print (solve-b [2 8 6 0 5 1] 21000000))
(print (current-time-string))
#+END_SRC
#+RESULTS:
#+begin_example
9
5
18
2018
"Fri Dec 14 23:24:49 2018"
20195114
"Fri Dec 14 23:29:50 2018"
#+end_example
That took a while and totally locked up Emacs for over 5
minutes. Below are timings from when I used =subseq= instead of just
starting the search at a specific point. Turns out it's a modest
improvement for Emacs Lisp and Common Lisp.
#+RESULTS:
#+begin_example
9
5
18
2018
"Fri Dec 14 18:01:58 2018"
20195114
"Fri Dec 14 18:07:07 2018"
#+end_example
Alright, so I'm going to re-implement everything in Common Lisp now.
#+NAME: solve-b
#+BEGIN_SRC lisp :results silent
(defun next-recipes (recipes positions)
(let* ((p1 (car positions))
(p2 (cadr positions))
(next (+ (aref recipes p1) (aref recipes p2)))
(next-1 (floor (/ next 10)))
(next-2 (mod next 10)))
(unless (= 0 next-1)
(vector-push-extend next-1 recipes))
(vector-push-extend next-2 recipes)
recipes))
(defun next-positions (recipes positions)
(let* ((p1 (car positions))
(p2 (cadr positions)))
(list (mod (+ p1 1 (aref recipes p1)) (length recipes))
(mod (+ p2 1 (aref recipes p2)) (length recipes)))))
(defun solve-b (target &optional (iterations 1000))
(let ((recipes (make-array iterations :adjustable t :fill-pointer 0 :element-type '(integer 0 9)))
(positions '(0 1)))
(vector-push-extend 3 recipes)
(vector-push-extend 7 recipes)
(iter (repeat iterations)
(setf recipes (next-recipes recipes positions))
(setf positions (next-positions recipes positions))
(when (> (length recipes) (length target))
(if (search target recipes :start2 (- (length recipes) (length target) 1))
(return (search target recipes :start2 (- (length recipes) (length target) 1))))))))
#+END_SRC
Timing on my machine for the above code:
#+BEGIN_EXAMPLE
Evaluation took:
4.787 seconds of real time
4.783282 seconds of total run time (4.724493 user, 0.058789 system)
[ Run times consist of 0.103 seconds GC time, and 4.681 seconds non-GC time. ]
99.92% CPU
14,818,029,875 processor cycles
1,403,098,944 bytes consed
#+END_EXAMPLE
Before I was using =:start2= I was taking a subsequence and searching
against it. This was from the emacs lisp code. In Common Lisp and
emacs lisp we have the option of starting the search from an arbitrary point.
#+BEGIN_EXAMPLE
Evaluation took:
5.244 seconds of real time
5.249132 seconds of total run time (5.193022 user, 0.056110 system)
[ Run times consist of 0.139 seconds GC time, and 5.111 seconds non-GC time. ]
100.10% CPU
16,233,424,920 processor cycles
1,924,772,672 bytes consed
#+END_EXAMPLE
It's incredibly important to use that =:element-type= specifier
here. If I don't, unless the garbage collector helps me out, I'm
likely to have run out of heap space.
#+NAME: problem-b
#+BEGIN_SRC lisp :noweb yes :results silent
(defun problem-b () (format t "Problem 14 B: ~a~%" (solve-b (cadr *input*) 100000000)))
#+END_SRC
** Putting it all together
#+NAME: structs
#+BEGIN_SRC lisp :noweb yes :results silent
#+END_SRC
#+NAME: functions
#+BEGIN_SRC lisp :noweb yes :results silent
<<solve-b>>
#+END_SRC
#+NAME: answers
#+BEGIN_SRC lisp :results output :exports both :noweb yes :tangle 2018.14.lisp
<<structs>>
<<initialize>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)
#+END_SRC
** Answer
#+RESULTS: answers
: Problem 14 A: (286051 (2 8 6 0 5 1))
: Problem 14 B: 20195114
** Test Cases
#+NAME: test-cases
#+BEGIN_SRC lisp :results output :exports both :noweb yes
<<solve-b>>
(def-suite aoc.2018.14)
(in-suite aoc.2018.14)
(test part-2
(is (= 9 (solve-b (list 5 1 5 8 9))))
(is (= 5 (solve-b (list 0 1 2 4 5) 1000)))
(is (= 18 (solve-b (list 9 2 5 1 0) 1000)))
(is (= 2018 (solve-b (list 5 9 4 1 4) 3000)))
(is (null (solve-b (list 5 9 4 1 4) 1000))))
(run! 'aoc.2018.14)
#+END_SRC
** Test Results
#+RESULTS: test-cases
:
: Running test suite AOC.2018.14
: Running test PART-2 .....
: Did 5 checks.
: Pass: 5 (100%)
: Skip: 0 ( 0%)
: Fail: 0 ( 0%)
** Thoughts