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-17) - 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-17
(:use :common-lisp
:iterate
:parseq
:fiveam)
(:export :problem-a
:problem-b))
(in-package :aoc-2018-17)The input is a set of line segments, horizontal and vertical. The first value is whichever number is constant for the segment. So:
x=565, y=1098..1105 y=102, x=439..459 x=519, y=1522..1532
The first segment starts at (565,1098) and goes to (565,1105) with x constant, the second is (439,102) to (459,102) with y constant.
(defun parse-line (line)
(with-local-rules
(defrule coord () (+ digit) (:string) (:function #'parse-integer))
(defrule x () "x=" (:constant :x))
(defrule y () "y=" (:constant :y))
(defrule constant () (and (or x y) coord))
(defrule range () (and (or x y) coord ".." coord) (:choose 0 1 3))
(defrule line () (and constant ", " range) (:choose 0 2))
(parseq 'line line)))(defun read-input (file)
(iter (for line in-file file using #'read-line)
(collect (parse-line line))))(defparameter *input*
(read-input "input/17.txt"))Today’s challenge is basically a falling water game. The input describes “clay” that water cannot pass through. Each input line describes a run of clay in an infinite plane.
Water starts at coordinate (0,500). We need to know how many spaces are reachable by water within the range of the input file. That is, even though the y range goes to infinity, we only care about the horizontal slice between min-y and max-y.
I’m going to continue my trend of using hash tables as sparse arrays for this. There will be two hash tables:
- Clay spaces
- Water spaces
Clay spaces will be a simple t, there’s nothing special about any of them.
Water spaces will be one of ~ or | to represent filled water, or falling/surface water. Let’s go ahead and make the two hash tables, and then attempt to print them out.
(defstruct (water-tables (:conc-name wt-))
clay
water
min-y
max-y
min-x
max-x)
(defun parse-clay-coordinates (clay-coordinates)
(let ((clay (make-hash-table))
(water (make-hash-table))
(min-y sb-ext:double-float-positive-infinity)
(max-y sb-ext:double-float-negative-infinity)
(min-x sb-ext:double-float-positive-infinity)
(max-x sb-ext:double-float-negative-infinity))
(iter (for ((x-or-y coord) (y-or-x min max)) in clay-coordinates)
(when (eql x-or-y :x)
(setf min-x (min coord min-x))
(setf max-x (max coord max-x))
(iter (for y from min to max)
(with x = coord)
(setf (gethash (complex x y) clay) t)
(setf min-y (min y min-y))
(setf max-y (max y max-y))))
(when (eql x-or-y :y)
(setf min-y (min coord min-y))
(setf max-y (max coord max-y))
(iter (for x from min to max)
(with y = coord)
(setf (gethash (complex x y) clay) t)
(setf min-x (min x min-x))
(setf max-x (max x max-x)))))
(setf (gethash #C(500 0) water) #\+)
(make-water-tables :clay clay :water water :min-y min-y :max-y max-y :min-x min-x :max-x max-x)))(defun print-water-tables (wt)
(iter (for y from 0 to (wt-max-y wt))
(iter (for x from (1- (wt-min-x wt)) to (1+ (wt-max-x wt)))
(let ((coord (complex x y)))
(cond ((gethash coord (wt-clay wt))
(format t "#"))
((gethash coord (wt-water wt))
(format t "~a" (gethash coord (wt-water wt))))
(t (format t ".")))))
(format t "~%")))
The next step is to count the number of water spaces within our range. Since, technically, all x coordinates are valid to be counted regardless of the min/max, I’ll have a loop that goes from (min-x - 1) to (max-x + 1). I can get away with that because of the way the water falls, it can’t be more than one outside those bounds.
(defun count-water (wt)
(iter outer
(for x from (1- (wt-min-x wt)) to (1+ (wt-max-x wt)))
(iter (for y from (wt-min-y wt) to (wt-max-y wt))
(in outer
(count (gethash (complex x y) (wt-water wt)))))))OK, now the hard part. We have to fill the water table.
I’ll use 3 recursive functions: go-left, go-right, and go-down. The
functions will return t or nil. t will indicate that it has reached
the bottom of the map, nil will mean it reached a clay space. That
will indicate that we need to go back one level and again search left
and right. If both left and right lead to dead ends, we’ll go back and
fill the row with ~.
(defun fill-basins (wt)
(let ((water (wt-water wt))
(clay (wt-clay wt))
(down #C(0 1))
(left #C(-1 0))
(right #C(1 0))
(max-y (wt-max-y wt)))
(labels ((go-down (coord)
(unless (or (gethash coord clay)
(and (gethash coord water)
(char= (gethash coord water) #\~)))
(or (> (imagpart coord) max-y)
(and (gethash coord water)
(char= (gethash coord water) #\|))
(progn (setf (gethash coord water) #\|)
(or (go-down (+ coord down))
(let ((right? (go-right (+ coord right)))
(left? (go-left (+ coord left))))
(or left? right? (fill-row coord))))))))
(fill-row (coord)
(setf (gethash coord water) #\~)
(fill-left (+ coord left))
(fill-right (+ coord right)))
(fill-right (coord)
(unless (gethash coord clay)
(setf (gethash coord water) #\~)
(fill-right (+ coord right))))
(fill-left (coord)
(unless (gethash coord clay)
(setf (gethash coord water) #\~)
(fill-left (+ coord left))))
(go-right (coord)
(unless (gethash coord clay)
(setf (gethash coord water) #\|)
(or (go-down (+ coord down))
(go-right (+ coord right)))))
(go-left (coord)
(unless (gethash coord clay)
(setf (gethash coord water) #\|)
(or (go-down (+ coord down))
(go-left (+ coord left))))))
(go-down #C(500 1)))))(defun solve-a (wt)
(fill-basins wt)
(count-water wt))
(defun problem-a () (format t "Problem 17 A: ~a~%" (solve-a (parse-clay-coordinates *input*))))(defun count-water-reservoirs (wt)
(iter outer
(for x from (1- (wt-min-x wt)) to (1+ (wt-max-x wt)))
(iter (for y from (wt-min-y wt) to (wt-max-y wt))
(in outer
(count (and (gethash (complex x y) (wt-water wt))
(char= (gethash (complex x y) (wt-water wt)) #\~)))))))(defun solve-b (wt)
(fill-basins wt)
(count-water-reservoirs wt))
(defun problem-b () (format t "Problem 17 B: ~a~%" (solve-b (parse-clay-coordinates *input*))))<<parse-line>>
<<read-input>>
<<make-water-tables>>
<<print-water-tables>>
<<count-water>>
<<fill-basins>>
<<count-water-reservoirs>><<initialize>>
<<structs>>
<<functions>>
<<input>>
<<problem-a>>
<<problem-b>>
(problem-a)
(problem-b)Problem 17 A: 34244 Problem 17 B: 28202
(def-suite aoc.2018.17)
(in-suite aoc.2018.17)
(defparameter *test-input*
(mapcar #'parse-line
'("x=495, y=2..7"
"y=7, x=495..501"
"x=501, y=3..7"
"x=498, y=2..4"
"x=506, y=1..2"
"x=498, y=10..13"
"x=504, y=10..13"
"y=13, x=498..504")))
(test all-water
(is (= 57 (let ((wt (parse-clay-coordinates *test-input*)))
(fill-basins wt)
(count-water wt))))
(is (= 34244 (let ((wt (parse-clay-coordinates *input*)))
(fill-basins wt)
(count-water wt)))))
(test water-reservoir
(is (= 29 (let ((wt (parse-clay-coordinates *test-input*)))
(fill-basins wt)
(count-water-reservoirs wt))))
(is (= 28202 (let ((wt (parse-clay-coordinates *input*)))
(fill-basins wt)
(count-water-reservoirs wt)))))
(run! 'aoc.2018.17)Running test suite AOC.2018.17
Running test ALL-WATER ..
Running test WATER-RESERVOIR ..
Did 4 checks.
Pass: 4 (100%)
Skip: 0 ( 0%)
Fail: 0 ( 0%)