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-22) - 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"))
(unless (find-package :cl-heap)
(ql:quickload "cl-heap"))<<packages>>
(defpackage :aoc-2018-22
(:use :common-lisp
:iterate
:parseq
:fiveam)
(:export :problem-a
:problem-b))
(in-package :aoc-2018-22)The input is a depth and coordinate pair:
- Depth
- 3339
- X,Y
- 10,715
(defun read-input (file)
(iter (for line in-file file using #'read-line)
(collect line)))(defparameter *input*
(read-input "input/22.txt"))Need to determine the risk level of the cave Santa’s friend is trapped in.
Need to compute the geologic index of a region.
(defun erosion-level (geo-index depth)
(mod (+ geo-index depth) 20183))
(defun geologic-index-a (x y depth)
(let ((index (make-array (list (+ 2 x) (+ 2 y)) :initial-element 0)))
(iter (for i from 1 to (1+ x))
(setf (aref index i 0) (* i 16807)))
(iter (for j from 1 to (1+ y))
(setf (aref index 0 j) (* j 48271)))
(iter (for j from 1 to (1+ y))
(iter (for i from 1 to (1+ x))
(unless (and (= i x) (= j y)) ;; friend @ spot w/ 0 index
(setf (aref index i j)
(* (erosion-level (aref index (1- i) j) depth)
(erosion-level (aref index i (1- j)) depth))))))
index))OK, I think that works. Now we need the sum of each location from (0,0) to (10,715) mod 3.
(defun risk-level-a (geo-index x y depth)
(iter outer
(for j from 0 to y)
(iter (for i from 0 to x)
(in outer
(sum (mod (erosion-level (aref geo-index i j) depth) 3))))))(defun problem-a () (format t "Problem 22 A: ~a~%"
(let ((index (geologic-index-a 10 715 3339)))
(risk-level-a index 10 715 3339))))The second part is a path finding task.
As you leave, he hands you some tools: a torch and some climbing gear. You can’t equip both tools at once, but you can choose to use neither.
Tools can only be used in certain regions:
- In rocky regions, you can use the climbing gear or the torch. You cannot use neither (you’ll likely slip and fall).
- In wet regions, you can use the climbing gear or neither tool. You cannot use the torch (if it gets wet, you won’t have a light source).
- In narrow regions, you can use the torch or neither tool. You cannot use the climbing gear (it’s too bulky to fit).
Entering a region takes 1 minute, changing equipped tool (even to
neither) takes 7 minutes. You cannot enter a region with the wrong
tool equipped (so can’t enter wet with a torch).
Must equip the torch (if not already equipped) once at the target location to find them (potential extra 7 minutes).
The question is, what’s the fewest number of minutes it’d take to reach the target.
May traverse regions outside of those in the minimal rectangle.
Negative X or Y coordinates are impenetrable rock.
Start with the torch equipped.
I will attempt to relearn writing the A* algorithm. It uses a heuristic to determine which option is “best” at any given point.
(defun geologic-index (position grid depth target)
(cond ((= position target) 0)
((gethash position grid)
(gethash position grid))
((= 0 (imagpart position))
(setf (gethash position grid) (* position 16807)))
((= 0 (realpart position))
(setf (gethash position grid) (* (imagpart position) 48271)))
(t (setf (gethash position grid)
(* (erosion-level (geologic-index (- position #C(1 0)) grid depth target) depth)
(erosion-level (geologic-index (- position #C(0 1)) grid depth target) depth))))))(let ((grid (make-hash-table))
(target #C(10 715))
(depth 3339))
(iter outer
(for x from 0 to 10)
(iter (for y from 0 to 715)
(in outer
(sum (mod (erosion-level (geologic-index (complex x y) grid depth target) depth) 3))))))7915
That was an experiment, redid the first part using a hash table. This will make exploring a bit easier since it can grow more easily than the array.
I’ve added the cl-heap package to my building blocks. This will be
more efficient than using an alist with priorities.
The graph to search is not actually just the positions, but rather (positions x equipped). At any given point, the position can change (cost of 1) or the equipment can change (cost of 7).
The heuristic will be the Manhattan distance. If we overestimate the distance to the target then A* may not find the best path. Manhattan distance is the lower bound in our case.
(defun manhattan-distance (p1 p2)
(+ (abs (realpart (- p1 p2)))
(abs (imagpart (- p1 p2)))))Playing around with classes, because why not. defmethod specializes
on the class types of all parameters. If there’s no specialized
version, the default (returning nil) is called, otherwise the
specialized versions (returning t) will be called.
(defclass terrain () ())
(defclass rocky (terrain) ())
(defclass wet (terrain) ())
(defclass narrow (terrain) ())
(defclass equipment () ())
(defclass torch (equipment) ())
(defclass climbing-gear (equipment) ())
(defclass neither (equipment) ())
(defgeneric allowed (terrain))
(defmethod allowed (terrain) nil)
(defmethod allowed ((terrain rocky)) (list 'torch 'climbing-gear))
(defmethod allowed ((terrain wet)) (list 'climbing-gear 'neither))
(defmethod allowed ((terrain narrow)) (list 'torch 'neither))
(defun terrain-type (erosion-level)
(case (mod erosion-level 3)
(0 (make-instance 'rocky))
(1 (make-instance 'wet))
(2 (make-instance 'narrow))))
(defun terrain-char (erosion-level)
(case (mod erosion-level 3)
(0 #\.)
(1 #\=)
(2 #\|)))(defun calculate-cost (s1 s2)
(cond ((= (car s1) (car s2)) 7)
(t 1)))
(defun search-for-target (x y depth)
(let* ((target (complex x y))
(grid (make-hash-table))
(state (list #C(0 0) 'torch))
(frontier (make-instance 'cl-heap:priority-queue))
(came-from (make-hash-table :test #'equalp))
(cost-so-far (make-hash-table :test #'equalp))
(goal (list target 'torch)))
(labels ((neighborhood (current)
(let ((position (car current))
(equipment (cadr current))
(offsets '(-1 1 #C(0 1) #C(0 -1))))
(iter outer
(for offset in offsets)
(when (and (<= 0 (realpart (+ offset position)))
(<= 0 (imagpart (+ offset position))))
(let ((current-terrain
(terrain-type (erosion-level
(geologic-index position grid depth target)
depth)))
(next-terrain
(terrain-type (erosion-level
(geologic-index (+ position offset)
grid depth target)
depth))))
(when (member equipment (allowed next-terrain))
(collect (list (+ position offset) equipment)))
(unless (member equipment (allowed next-terrain))
(collect (list position (car (intersection (allowed next-terrain)
(allowed current-terrain))))))))))))
(setf (gethash state came-from) nil)
(setf (gethash state cost-so-far) 0)
(cl-heap:enqueue frontier state 0)
(iter (until (= 0 (cl-heap:queue-size frontier)))
(for current = (cl-heap:dequeue frontier))
(when (equalp current goal)
(return (values
(gethash current cost-so-far)
(path came-from goal)
grid)))
(iter (for next in (neighborhood current))
(let ((cost (+ (gethash current cost-so-far)
(calculate-cost current next))))
(when (or (not (gethash next cost-so-far))
(< cost (gethash next cost-so-far)))
(setf (gethash next cost-so-far) cost)
(cl-heap:enqueue frontier
next
(+ cost (manhattan-distance target (car next))
(if (eq (cadr next) 'torch) 0 7)))
(setf (gethash next came-from) current))))))))
(defun path (came-from goal)
(let ((state goal))
(iter (while (gethash state came-from))
(collect state)
(setf state (gethash state came-from)))))(defun problem-b () (format t "Problem 22 B: ~a~%" (search-for-target 10 715 3339)))<<geologic-index-a>>
<<risk-level-a>>
<<read-input>>
<<manhattan-distance>>
<<geologic-index>>
<<classes>>
<<search>><<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)Problem 22 A: 7915 Problem 22 B: 980
(def-suite aoc.2018.22)
(in-suite aoc.2018.22)
(run! 'aoc.2018.22)