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-2019-18) - 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 :series)
(ql:quickload "series"))
(unless (find-package :graph)
(ql:quickload "graph"))
(unless (find-package :cl-permutation)
(ql:quickload "cl-permutation"))
(unless (find-package :bordeaux-threads)
(ql:quickload "bordeaux-threads"))<<packages>>
(defpackage :aoc-2019-18
(:use :common-lisp
:iterate
:parseq
:fiveam)
(:export :problem-a
:problem-b))
(in-package :aoc-2019-18)(defun read-input (file)
(iter (for line in-file file using #'read-line)
(collect line)))(defparameter *input*
(read-input "input/18.txt"))Today’s task is another maze one. Lower case letters are keys to their upper case letter door counterparts. Keys have to be retrieved before the door can be opened. What’s the shortest number of steps needed to take to retrieve all keys.
I’m attempting to produce a simplified graph. I’m operating under the assumption that (other than around the entrance) there are no cycles or alternate routes to the keys.
General concept:
- Convert input to hash-table grid, SOP for these problems for me.
- Convert hash-table grid to a graph, each node adjacent to its neighbors.
- Using those two data sources, produce simplified graph of maze.
The simplified graph is going to look like:
a - b 10 b - A 5 A - c 8
Reducing it to just this set of data should reduce the amount of effort involved in the DFS I intend to use for the actual solution.
(defun maze-to-hashtable (lines)
"Given a text-form maze, returns a hash table coord->character
without walls."
(let ((maze (make-hash-table)))
(iter (for y from 0)
(for line in lines)
(iter (for x from 0)
(for c in-string line)
(for coord = (complex x y))
(unless (char= #\# c) (setf (gethash coord maze) c))))
maze))
(defun maze-bounds (lines)
(list (length (first lines)) (length lines)))
(defun print-maze (maze)
(destructuring-bind (max-x max-y) (maze-bounds maze)
(let ((maze (maze-to-hashtable maze)))
(iter (for y from 0 below max-y)
(iter (for x from 0 below max-x)
(for coord = (complex x y))
(for c = (gethash coord maze))
(cond ((null c)
(format t " "))
(t
(format t "~C" c))))
(format t "~%")))))
(defun maze-to-graph (maze)
"Given a hash-form maze, returns a graph using coordinates."
(let ((graph (make-instance 'graph:graph)))
(iter (for (k v) in-hashtable maze)
(graph:add-node graph k))
(iter (for (k v) in-hashtable maze)
(iter (for d in '(#C(0 1) #C(0 -1) #C(-1 0) #C(1 0)))
(when (gethash (+ d k) maze)
(graph:add-node graph (+ d k))
(graph:add-edge graph (list k (+ d k))))))
graph))
(defun clear-path (objects path)
"If the PATH consists only of empty spaces, returns T. If the path
is a single edge, returns T. Otherwise, NIL."
(cond ((= 1 (length path)) t)
((and (gethash (caar path) objects)
(gethash (cadar path) objects))
nil)
((and (gethash (caar (last path)) objects)
(gethash (cadar (last path)) objects))
nil)
(t (iter (for (a b) in (butlast (rest path)))
(always (and (not (gethash a objects))
(not (gethash b objects))))))))
(defun doorp (s)
(upper-case-p (elt (symbol-name s) 0)))
(defun keyp (s)
(not (doorp s)))
(defun has-key (door keys)
(iter (for k in keys)
(thereis (string-equal (symbol-name k) door))))
(defun can-reach (a b maze keys)
(iter (for d in (remove-if #'keyp (apply #'append (graph:shortest-path maze a b))))
(always (has-key d keys))))
(defun simplified-maze (lines)
(let* ((hash (maze-to-hashtable lines))
(graph (maze-to-graph hash))
(maze (make-instance 'graph:graph))
(locations (make-hash-table)) ;; sym->complex
(objects (make-hash-table))) ;; complex->sym
(iter (for (k v) in-hashtable hash)
(for node-name = (intern (string v)))
(cond ((lower-case-p v)
(setf (gethash node-name locations) k)
(setf (gethash k objects) node-name)
(graph:add-node maze node-name))
((upper-case-p v)
(setf (gethash node-name locations) k)
(setf (gethash k objects) node-name)
(graph:add-node maze node-name))
((char= #\@ v)
(setf (gethash node-name locations) k)
(setf (gethash k objects) node-name)
(graph:add-node maze node-name))))
(iter (for (k1 v1) in-hashtable locations)
(iter (for (k2 v2) in-hashtable locations)
(multiple-value-bind (path length) (graph:shortest-path graph v1 v2)
(when (and (not (eql k1 k2))
(clear-path objects path))
(graph:add-edge maze (list k1 k2) length)))))
maze))
(defun solve-a (maze)
(let ((start (graph:neighbors maze '@)))
(remove '@ start :count nil)))I’ve way over complicated my solution. I think. Anyways, the above will produce a map of just the keys, entrance, and doors. It takes 14 seconds, oops. The last loop is what actually takes so long.
(defun problem-a () (format t "Problem 18 A: ~a~%" (identity *input*)))(defun problem-b () (format t "Problem 18 B: ~a~%" (identity *input*)))<<read-input>>
<<input>><<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)Problem 18 A: (#################################################################################
#.......#.A...........#.........#.......#.#.........#.............#...#..r......#
#.###.###.#####.#####.#.#######.#.#######.#.#.#####.#.#.#.#######.###.#.###.###.#
#...#.#...#.....#.#...#...#.....#.......#...#.#...#o#.#.#.#...#.#...#.#...#.#...#
#####.#.###.#####.#.###.#W###.#########.#####.#.#.###.#.#.#.#.#.###.#K###.#.#####
#.....#.#.#...#...#...#.#...#...........#...#...#.....#.#.#.#.#.#...#...#.#.....#
#M###.#.#.###.#.#####.#####.###########.#.#.###.#######.###.#.#.#.#####.#.#####.#
#.#...#...#...#.#...#.....#...#..z....#.#.#...#...#.....#...#.#.#.#...#.......#.#
#.###.###.#.###.#.#.#####.###.#.###.#.#.#.###.#####.#.###.###.#.#.#.#.#####.###.#
#...#...#.#.#....y#.....#.....#.#.#.#.#.#...#.#...#.#.#...#...#.#...#.#...#.#m..#
#.#.#####.#.###########.#######.#.#.#.#.###.#.#.#X#.#.#.###.###.#####.#.#.###.###
#.#.#...#.#s..#.......#.......#...#.#.#.#...#...#.#.#.#.#.#.#.......#...#...#...#
###.#.#.#.###.#.#####.###.###.#####.#.#.#.#######.#.###.#.#.#.#####.#######.###.#
#...#.#...#.#...#...#.#...#.......#.#.#.#.#.......#.....#.#.#.#.....#.....#.....#
#.###.#####.#####.#.#C#.###.#####.#.#.#.#.#####.###.#####.#.###.#####.#.#.#####.#
#.....#.....#.....#.#.#.#...#...#...#.#.#.#.F.#...#...#...#...#.#...#.#.#.....#.#
#.#######.#.###.###.#.#.#####.#.#######.#.#.#.###.###.###.###.#.#.#.#.#.#######.#
#.#.......#...#.#...#.#...#...#.#.......#...#.#.#...#.......#.#.#.#.#.#.........#
#.#.#########.#.#####.###N#.###.#.###########.#.###.#########.#.#.#.#.###########
#...#...#.......#.....#...#.#.#.#.......#...#.#...............#...#.#.#....q....#
#####.###.#######.#####.###.#.#.#######.#.#.#.#############.#####.#.#.#.#.#####.#
#g..#.....#.....#...#.#...#...#.......#.#.#.#..l..........#.#...#.#.#.#.#...#...#
###.#.#####.###.###.#T#.#.###.###.#####.###.#############.#####B#.#.#.#.###.#####
#...#.#...#...#.....#.#.#...#.#.#.#...#.#.......#.......#...#...#.#...#...#.....#
#.###.###.###.#####.#.###.###.#.#.#.#.#.#.#####.#.###.#####.#.###.#####.#######.#
#...#...#...#.#.#...#...#.I...#.#...#...#.....#.#...#.#...#...#.#...#.#.#.......#
###.###.#.###.#.#.#####.#####.#.#############.#####.#.#.#.#####.###.#.#.#.#######
#.....#.#...#.#.......#.#...#...........#.....#.....#...#.......#.#.#.#.#.......#
#.#####.###.#.#######.#.#.#.#####.#######.###.#.###########.###.#.#.#.#.#######.#
#...........#.#e....#.#...#...#...#.....#.#...#...#.........#.....#.#...#.......#
#.###########.#.###.#########.#####.###.#.#######.#.#####.#######.#.#####.#####.#
#.....#.#.....#.#.#.........#.......#...#.#.......#.#.....#.....#.#...#...#.#...#
#####.#.#.#####.#.#####.#.###########.###.#.#######.#####.#.###.#.###.#.###.#.###
#...#.#.#.......#.#.....#.#.........#.#.#...#.#.....#...#.#.#...#...#.#...#...#.#
#.###.#.#########.#.#####.#V#.#####.#.#.#.###.#.###.#.#.###.#.#######.###.#.###.#
#.#...#.....#.....#.#.....#.#...#...#.#.#.#...#.#.#.#.#.....#.........#...#.#...#
#.#.###.###.#.#####.#######.###.#.###.#.#.###.#.#.#.#.#################.###.#.#.#
#.#.....#.#.#.....#.......#.#.#.#...#.#.#.#...#.#...#.#.........#.......#.S.#.#.#
#.#######.#.#####.#######.#.#.#.#####.#.#.#.#.#.#####.#####.###.#.#######.###.#.#
#.......................#.....#.............#.#.............#.....#...........#.#
#######################################.@.#######################################
#...............#.....#.....#.............#.........................D.......#..u#
#.#############.#####.#.#.###.###.#####.#.#.#.#####.#######.###############.#.###
#.....#.....#...#...#...#.....#.#.#.....#...#....v#.#.....#.#.......#.....#.#.E.#
#####.#.#####.###.#.#.#########.#.#######.#######.###.###.###.#####.#.#####.#.#.#
#.....#.....#.....#.#.#...#.....#.......#.#.......#.....#.#...#...#.#....j#t#.#.#
#.#########.#######.#.#.#.#.###########.#.#.#######.#####.#.###.###.#####.#.#.#.#
#.......#...#...#...#...#...#.......#...#.#.#.....#.#.....#.#.....#.#...#.#.#.#.#
#######.#.#.###.#.#######.###.#####.#.#####.#.###.#.#.#####.#####.#.#.#.#.#.###.#
#.....#.#.#.....#...#.....#...#.....#...#...#.#.#...#.....#.......#...#.#.#.#...#
###.###.#.#####.###.#####.#.###.#####.#.#.#.#.#.#########.#######.#####.#.#.#.#.#
#...#...#...#...#.#.....#.#.#.#.#.....#.#.#d#.#.....#.......#.....#.....#.#...#.#
#.###.#####.#.###.#####.#.#.#.#.#######.#.###.###.#.#.#######.#####.#####.#####.#
#.....#...#.#.....#.....#.#.#.#...#.....#.....#...#.#.....#.....#...#...#.....#.#
#.#####.#.#.#.#####.#####.#.#.###.#.###.#######.#.#######.#.#####.#####.#.#.#.#.#
#.#.....#.#.#.#.....#.....#.#...#.#.#...#.......#.#.....#...#.#...#.....#.#.#.#.#
#.###.#.#.#.#.#.###########.###.#.#.#.###.#########.#.#######.#.#####.###.#.###.#
#.H.#.#.#.#.#.#.....#.....#.#...#...#...#.#.....#...#.........#.#.....#...#.....#
###.###.#.#.#.#####.#.###.#.#.#########.#.#.###.#.#######.#####.#.#.#.#.#########
#.#.#...#...#...#.#...#...#.#...#.......#...#.#...#.....#...#...#.#.#.#.........#
#.#.#.#.#######.#.#####.###.#.#.#.#######.###.#########.###.#.#####.#.#########.#
#...#.#.#...#.#.#...#...#...#.#.#...#...#...#...#.....#...#.#.#.....#.#.......#.#
#.###.###.#.#.#.###.#######.#.#.###.#.#.###.#.###.#.#.#.#.#.###.#####.###.###.#.#
#.#...#...#.#.#.#...........#.#...#.#.#.#.#.#.#...#.#...#.#.....#...#...#.#.#.#.#
#.###.#.###.#.#.#.###########.###.#.#.#.#.#.#.#.###.#####.#####.###.###.#.#.#.#.#
#...#...#.#.#.#...#...#.U...#.#.#...#.#.#...#.....#.#.....#...#...#...#...#...#.#
###.#.###.#.#.#####J#.#.#.###.#.#####.###.#######.#.#####.#.#####.#.#####.#####.#
#...#.Q.#.#.#.....#.#...#.....#.........#.......#.#f....#.L.#.....#h....#.#...#.#
#.#####.#.#.###.#.#.#################.#.#######.#.#####.###.#.#####.#.###.#.#.#.#
#.#...#...#...#.#.#.#...#.......#...#.#.#.#...G.#.....#.Z.#.#...#...#.....#.#...#
#.#.#####.###.###.#.#.#.#####.#.#.#.###.#.#.#############.#.###.#########.#.#####
#k#.#.....#.#...#.#..c#...#...#...#.#...#.#.#........n#...#...#.#.......#.#...#.#
#.#.#.#####.###.#.#######.#.#######.#.#.#.#.#.#######.#.###.###.#.#####.#####.#.#
#.#...#.....#...#.#.P...#.#.#.....#...#.#.#.#.#...#...#.#...#...#.....#.....#p..#
#.###.#.#.###.###.#.#.###.#.###.#.#####.#.#.#.#.###.###.###.#.#######.###.#####.#
#...#...#.#...#.#...#...#.#...#.#...#...#.O.#.#.....#.#...#b#.#.......#.#.#...#.#
###.#####.#.###.#.#####.#.###.#####.#.###.###.#.#####.#.#.###.#.#######.#.#.#.#.#
#.#.#.....#.#a..#.#...#.#.#...#.....#...#...#i#.#...#...#.Y.#.#.#....w..#.#.#...#
#.#R#######.#.#.#.###.#.#.#.###.#######.###.#.#.#.#.#######.#.#.#####.#.#.#.#####
#...........#.#.......#.....#...........#.....#x..#.........#.........#.#.......#
#################################################################################)
Problem 18 B: (#################################################################################
#.......#.A...........#.........#.......#.#.........#.............#...#..r......#
#.###.###.#####.#####.#.#######.#.#######.#.#.#####.#.#.#.#######.###.#.###.###.#
#...#.#...#.....#.#...#...#.....#.......#...#.#...#o#.#.#.#...#.#...#.#...#.#...#
#####.#.###.#####.#.###.#W###.#########.#####.#.#.###.#.#.#.#.#.###.#K###.#.#####
#.....#.#.#...#...#...#.#...#...........#...#...#.....#.#.#.#.#.#...#...#.#.....#
#M###.#.#.###.#.#####.#####.###########.#.#.###.#######.###.#.#.#.#####.#.#####.#
#.#...#...#...#.#...#.....#...#..z....#.#.#...#...#.....#...#.#.#.#...#.......#.#
#.###.###.#.###.#.#.#####.###.#.###.#.#.#.###.#####.#.###.###.#.#.#.#.#####.###.#
#...#...#.#.#....y#.....#.....#.#.#.#.#.#...#.#...#.#.#...#...#.#...#.#...#.#m..#
#.#.#####.#.###########.#######.#.#.#.#.###.#.#.#X#.#.#.###.###.#####.#.#.###.###
#.#.#...#.#s..#.......#.......#...#.#.#.#...#...#.#.#.#.#.#.#.......#...#...#...#
###.#.#.#.###.#.#####.###.###.#####.#.#.#.#######.#.###.#.#.#.#####.#######.###.#
#...#.#...#.#...#...#.#...#.......#.#.#.#.#.......#.....#.#.#.#.....#.....#.....#
#.###.#####.#####.#.#C#.###.#####.#.#.#.#.#####.###.#####.#.###.#####.#.#.#####.#
#.....#.....#.....#.#.#.#...#...#...#.#.#.#.F.#...#...#...#...#.#...#.#.#.....#.#
#.#######.#.###.###.#.#.#####.#.#######.#.#.#.###.###.###.###.#.#.#.#.#.#######.#
#.#.......#...#.#...#.#...#...#.#.......#...#.#.#...#.......#.#.#.#.#.#.........#
#.#.#########.#.#####.###N#.###.#.###########.#.###.#########.#.#.#.#.###########
#...#...#.......#.....#...#.#.#.#.......#...#.#...............#...#.#.#....q....#
#####.###.#######.#####.###.#.#.#######.#.#.#.#############.#####.#.#.#.#.#####.#
#g..#.....#.....#...#.#...#...#.......#.#.#.#..l..........#.#...#.#.#.#.#...#...#
###.#.#####.###.###.#T#.#.###.###.#####.###.#############.#####B#.#.#.#.###.#####
#...#.#...#...#.....#.#.#...#.#.#.#...#.#.......#.......#...#...#.#...#...#.....#
#.###.###.###.#####.#.###.###.#.#.#.#.#.#.#####.#.###.#####.#.###.#####.#######.#
#...#...#...#.#.#...#...#.I...#.#...#...#.....#.#...#.#...#...#.#...#.#.#.......#
###.###.#.###.#.#.#####.#####.#.#############.#####.#.#.#.#####.###.#.#.#.#######
#.....#.#...#.#.......#.#...#...........#.....#.....#...#.......#.#.#.#.#.......#
#.#####.###.#.#######.#.#.#.#####.#######.###.#.###########.###.#.#.#.#.#######.#
#...........#.#e....#.#...#...#...#.....#.#...#...#.........#.....#.#...#.......#
#.###########.#.###.#########.#####.###.#.#######.#.#####.#######.#.#####.#####.#
#.....#.#.....#.#.#.........#.......#...#.#.......#.#.....#.....#.#...#...#.#...#
#####.#.#.#####.#.#####.#.###########.###.#.#######.#####.#.###.#.###.#.###.#.###
#...#.#.#.......#.#.....#.#.........#.#.#...#.#.....#...#.#.#...#...#.#...#...#.#
#.###.#.#########.#.#####.#V#.#####.#.#.#.###.#.###.#.#.###.#.#######.###.#.###.#
#.#...#.....#.....#.#.....#.#...#...#.#.#.#...#.#.#.#.#.....#.........#...#.#...#
#.#.###.###.#.#####.#######.###.#.###.#.#.###.#.#.#.#.#################.###.#.#.#
#.#.....#.#.#.....#.......#.#.#.#...#.#.#.#...#.#...#.#.........#.......#.S.#.#.#
#.#######.#.#####.#######.#.#.#.#####.#.#.#.#.#.#####.#####.###.#.#######.###.#.#
#.......................#.....#.............#.#.............#.....#...........#.#
#######################################.@.#######################################
#...............#.....#.....#.............#.........................D.......#..u#
#.#############.#####.#.#.###.###.#####.#.#.#.#####.#######.###############.#.###
#.....#.....#...#...#...#.....#.#.#.....#...#....v#.#.....#.#.......#.....#.#.E.#
#####.#.#####.###.#.#.#########.#.#######.#######.###.###.###.#####.#.#####.#.#.#
#.....#.....#.....#.#.#...#.....#.......#.#.......#.....#.#...#...#.#....j#t#.#.#
#.#########.#######.#.#.#.#.###########.#.#.#######.#####.#.###.###.#####.#.#.#.#
#.......#...#...#...#...#...#.......#...#.#.#.....#.#.....#.#.....#.#...#.#.#.#.#
#######.#.#.###.#.#######.###.#####.#.#####.#.###.#.#.#####.#####.#.#.#.#.#.###.#
#.....#.#.#.....#...#.....#...#.....#...#...#.#.#...#.....#.......#...#.#.#.#...#
###.###.#.#####.###.#####.#.###.#####.#.#.#.#.#.#########.#######.#####.#.#.#.#.#
#...#...#...#...#.#.....#.#.#.#.#.....#.#.#d#.#.....#.......#.....#.....#.#...#.#
#.###.#####.#.###.#####.#.#.#.#.#######.#.###.###.#.#.#######.#####.#####.#####.#
#.....#...#.#.....#.....#.#.#.#...#.....#.....#...#.#.....#.....#...#...#.....#.#
#.#####.#.#.#.#####.#####.#.#.###.#.###.#######.#.#######.#.#####.#####.#.#.#.#.#
#.#.....#.#.#.#.....#.....#.#...#.#.#...#.......#.#.....#...#.#...#.....#.#.#.#.#
#.###.#.#.#.#.#.###########.###.#.#.#.###.#########.#.#######.#.#####.###.#.###.#
#.H.#.#.#.#.#.#.....#.....#.#...#...#...#.#.....#...#.........#.#.....#...#.....#
###.###.#.#.#.#####.#.###.#.#.#########.#.#.###.#.#######.#####.#.#.#.#.#########
#.#.#...#...#...#.#...#...#.#...#.......#...#.#...#.....#...#...#.#.#.#.........#
#.#.#.#.#######.#.#####.###.#.#.#.#######.###.#########.###.#.#####.#.#########.#
#...#.#.#...#.#.#...#...#...#.#.#...#...#...#...#.....#...#.#.#.....#.#.......#.#
#.###.###.#.#.#.###.#######.#.#.###.#.#.###.#.###.#.#.#.#.#.###.#####.###.###.#.#
#.#...#...#.#.#.#...........#.#...#.#.#.#.#.#.#...#.#...#.#.....#...#...#.#.#.#.#
#.###.#.###.#.#.#.###########.###.#.#.#.#.#.#.#.###.#####.#####.###.###.#.#.#.#.#
#...#...#.#.#.#...#...#.U...#.#.#...#.#.#...#.....#.#.....#...#...#...#...#...#.#
###.#.###.#.#.#####J#.#.#.###.#.#####.###.#######.#.#####.#.#####.#.#####.#####.#
#...#.Q.#.#.#.....#.#...#.....#.........#.......#.#f....#.L.#.....#h....#.#...#.#
#.#####.#.#.###.#.#.#################.#.#######.#.#####.###.#.#####.#.###.#.#.#.#
#.#...#...#...#.#.#.#...#.......#...#.#.#.#...G.#.....#.Z.#.#...#...#.....#.#...#
#.#.#####.###.###.#.#.#.#####.#.#.#.###.#.#.#############.#.###.#########.#.#####
#k#.#.....#.#...#.#..c#...#...#...#.#...#.#.#........n#...#...#.#.......#.#...#.#
#.#.#.#####.###.#.#######.#.#######.#.#.#.#.#.#######.#.###.###.#.#####.#####.#.#
#.#...#.....#...#.#.P...#.#.#.....#...#.#.#.#.#...#...#.#...#...#.....#.....#p..#
#.###.#.#.###.###.#.#.###.#.###.#.#####.#.#.#.#.###.###.###.#.#######.###.#####.#
#...#...#.#...#.#...#...#.#...#.#...#...#.O.#.#.....#.#...#b#.#.......#.#.#...#.#
###.#####.#.###.#.#####.#.###.#####.#.###.###.#.#####.#.#.###.#.#######.#.#.#.#.#
#.#.#.....#.#a..#.#...#.#.#...#.....#...#...#i#.#...#...#.Y.#.#.#....w..#.#.#...#
#.#R#######.#.#.#.###.#.#.#.###.#######.###.#.#.#.#.#######.#.#.#####.#.#.#.#####
#...........#.#.......#.....#...........#.....#x..#.........#.........#.#.......#
#################################################################################)
(def-suite aoc.2019.18)
(in-suite aoc.2019.18)
(run! 'aoc.2019.18)