Each line of the input file had the format:
#ID @ LEFT,TOP : WIDTHxHEIGHT
I didn’t want to parse that, so I had emacs transform that into a list of the form:
((id (left top) (width height) ...)
A single read of the input file is all that’s needed to parse it thanks to CL’s reader.
(defvar *input-3*
(with-open-file (s "input/3.txt")
(read s)))We need to find out how many spaces have been claimed multiple times. The maximum size is 1000x1000 based on evaluating the claims.
(defun overlapping-spaces (cuts)
(let ((fabric (make-array '(1000 1000) :initial-element 0))
(overlap 0))
(loop for (id (left top) (width height)) in cuts
do (loop for i from left below (+ left width)
do (loop for j from top below (+ top height)
do (incf (aref fabric i j)))))
(loop for i from 0 below 1000
do (loop for j from 0 below 1000
if (> (aref fabric i j) 1)
do (incf overlap)))
overlap))
(defun problem-3a () (format t "Problem 3a: ~a~%" (overlapping-spaces *input-3*)))So the logic above mostly works for what we need now. However, instead of counting the claims we will mark each space with the various claims, this will just be a list. nil will represent unclaimed spaces. At the end, we just need to find one claim which is fully its own. To do that, we iterate over the space of each claim. If it has any spaces which are shared, we skip it and go to the next one. If we get to the very end of the cut and there’s no overlap, we return that.
(defun unique-claim (cuts)
(let ((fabric (make-array '(1000 1000) :initial-element nil))
(unique nil))
(loop for (id (left top) (width height)) in cuts
do (loop for i from left below (+ left width)
do (loop for j from top below (+ top height)
do (setf (aref fabric i j) (cons id (aref fabric i j))))))
(loop named outer
for (id (left top) (width height)) in cuts
do (loop named per-id
for i from left below (+ left width)
do (loop for j from top below (+ top height)
if (> (length (aref fabric i j)) 1)
do (return-from per-id nil)
if (and (= i (1- (+ left width)))
(= j (1- (+ top height))))
do (return-from outer (aref fabric i j)))))))
(defun problem-3b () (format t "Problem 3b: ~a~%" (unique-claim *input-3*)))<<day3-input>>
<<problem-3a>>
<<problem-3b>>
(problem-3a)
(problem-3b)Problem 3a: 110546 Problem 3b: (819)
I’m not going to clean up this code, it’s OK as is. But I did make an
error in my thoughts on #2. The first loop didn’t need to be changed
from the original, because ultimately I’m counting (via length) the
same thing that was produced in the first loop in #1 (each cell in the
array has an indicator of how many cuts try to claim it).
This would, very slightly, clean up the second loop as the test would go from:
if (> length (aref fabric i j) 1)to:
if (> (aref fabric i j) 1)And the variable I created, unique, in #2 was meant to be used with
the second loop. If a cut had no overlaps unique would be set to
that id. But I ended up not using it.
Below is how I’d have written unique-claim with those
considerations.
(defun unique-claim (cuts)
(let ((fabric (make-array '(1000 1000) :initial-element 0))
(unique nil))
(loop for (id (left top) (width height)) in cuts
do (loop for i from left below (+ left width)
do (loop for j from top below (+ top height)
do (incf (aref fabric i j)))))
(loop for (id (left top) (width height)) in cuts
until unique
do (loop named per-id
for i from left below (+ left width)
do (loop for j from top below (+ top height)
if (> (aref fabric i j) 1)
do (return-from per-id nil)
if (and (= i (1- (+ left width)))
(= j (1- (+ top height))))
do (setf unique id))))
unique))Of course, since that first loop is now identical in each we could
factor that into its own function. And since both problems now create
the same fabric array, we could generate it once and pass it to each
to use in their solutions. But I don’t feel like making those changes.