If you have a lisp installation, emacs, org-mode, and org-babel support for lisp installed you can run this by:
- Starting slime (
M-x slime) - Typing
C-c C-cin the block initialize. - In the repl type
(in-package :aoc-2018-14) - Typing
C-c C-cin the block answers
(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"))<<packages>>
(defpackage :aoc-2018-14
(:use :common-lisp
:iterate
:parseq
:fiveam)
(:export :problem-a
:problem-b))
(in-package :aoc-2018-14)The input is a string of digits to be interpreted in one of two ways: An integer count, or a list of numbers.
(defparameter *input* (list 286051 (list 2 8 6 0 5 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.
(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))))<<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))"Fri Dec 14 17:12:07 2018" "Fri Dec 14 17:12:11 2018" [2 1 1 1 1 1 3 6 7 8]
(defun problem-a () (format t "Problem 14 A: ~a~%" (identity *input*)))Now we have to find at what index the sequence interpretation of the input occurs.
<<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))9 5 18 2018 "Fri Dec 14 23:24:49 2018" 20195114 "Fri Dec 14 23:29:50 2018"
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.
Alright, so I’m going to re-implement everything in Common Lisp now.
(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))))))))Timing on my machine for the above code:
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
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.
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
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.
(defun problem-b () (format t "Problem 14 B: ~a~%" (solve-b (cadr *input*) 100000000)))<<solve-b>><<structs>>
<<initialize>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)Problem 14 A: (286051 (2 8 6 0 5 1)) Problem 14 B: 20195114
<<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)Running test suite AOC.2018.14
Running test PART-2 .....
Did 5 checks.
Pass: 5 (100%)
Skip: 0 ( 0%)
Fail: 0 ( 0%)