diff options
Diffstat (limited to 'AoC2022/08/solver.el')
| -rw-r--r-- | AoC2022/08/solver.el | 123 |
1 files changed, 84 insertions, 39 deletions
diff --git a/AoC2022/08/solver.el b/AoC2022/08/solver.el index 9c19651..27ee8a0 100644 --- a/AoC2022/08/solver.el +++ b/AoC2022/08/solver.el @@ -14,50 +14,95 @@ ;; Day 08 ;; ;;; Code: +(cl-defstruct (forest (:constructor forest--create) + (:copier nil)) + "Contaner for the forest layout" + grid (width nil :read-only t) (depth nil :read-only t)) -(with-temp-buffer - (insert-file-contents "input") - (let* ((rows (split-string (buffer-string))) - (forest-depth (length rows)) - (forest-width (length (car rows))) - (forest - (seq-mapcat - (lambda (row) - (cl-map 'vector (lambda (col) (logxor col 48)) row)) ;; 48 is the ascii 0 - rows 'vector)) - (visibility - (make-bool-vector (* forest-width forest-depth) nil)) - (last-max -1)) +(defsubst forest-index (forest i j) + (+ j (* (forest-width forest) i))) + +(defun solver-tree-visibility (forest) + (let ((visibility + (forest--create + :grid (make-bool-vector (* (forest-width forest) (forest-depth forest)) nil) + :depth (forest-depth forest) + :width (forest-width forest))) + last-max) (cl-flet ((update-visibility (index) - (let ((tree-height (aref forest index)) - (mask-val (aref visibility index))) - (setf (aref visibility index) (or mask-val (< last-max tree-height))) + (let ((tree-height (aref (forest-grid forest) index)) + (mask-val (aref (forest-grid visibility) index))) + (setf (aref (forest-grid visibility) index) (or mask-val (< last-max tree-height))) (setq last-max (max last-max tree-height))))) - - - ;; left visible - (dotimes (i forest-width) + (dotimes (i (forest-depth forest)) + ;; left visible (setq last-max -1) - (dotimes (j forest-depth) - (update-visibility (+ j (* forest-width i))))) - ;; top visible - (dotimes (j forest-depth) + (dotimes (j (forest-width forest)) + (update-visibility (forest-index forest i j))) + ;; rigth visible (setq last-max -1) - (dotimes (i forest-width) - (update-visibility (+ j (* forest-width i))))) - ;; rigth visible - (dotimes (i forest-width) + (cl-loop for j downfrom (1- (forest-width forest)) to 0 do + (update-visibility (forest-index forest i j)))) + (dotimes (j (forest-width forest)) + ;; top visible (setq last-max -1) - (cl-loop for j downfrom (1- forest-depth) to 0 do - (update-visibility (+ j (* forest-width i))))) - ;; bottom visible - (dotimes (j forest-depth) + (dotimes (i (forest-depth forest)) + (update-visibility (forest-index forest i j))) + ;; bottom visible (setq last-max -1) - (cl-loop for i downfrom (1- forest-width) to 0 do - (update-visibility (+ j (* forest-width i)))))) + (cl-loop for i downfrom (1- (forest-depth forest)) to 0 do + (update-visibility (forest-index forest i j))))) + visibility)) + +(defun solver-parse-input () + (with-temp-buffer + (insert-file-contents "input") + (let ((rows (split-string (buffer-string)))) + (forest--create + :grid (seq-mapcat + (lambda (row) + (cl-map 'vector (lambda (col) (logxor col 48)) row)) ;; 48 is the ascii 0 + rows 'vector) + :depth (length rows) + :width (length (car rows)))))) + +(defun solver-max-view-score (forest) + (let ((score (forest--create + :grid (make-vector (* (forest-width forest) (forest-depth forest)) 0) + :depth (forest-depth forest) + :width (forest-width forest)))) + (dotimes (i (forest-depth forest)) + (dotimes (j (forest-width forest)) + (let ((tree-height (aref (forest-grid forest) (forest-index forest i j)))) + (aset (forest-grid score) (forest-index score i j) + (* + ;; left + (cl-loop for l from (1+ j) below (forest-width forest) + for v-tree = (aref (forest-grid forest) (forest-index forest i l)) + count l + until (>= v-tree tree-height)) + ;; right + (cl-loop for l downfrom (1- j) to 0 + for v-tree = (aref (forest-grid forest) (forest-index forest i l)) + count l + until (>= v-tree tree-height)) + ;; top + (cl-loop for l downfrom (1- i) to 0 + for v-tree = (aref (forest-grid forest) (forest-index forest l j)) + count l + until (>= v-tree tree-height)) + ;; bottom + (cl-loop for l from (1+ i) below (forest-depth forest) + for v-tree = (aref (forest-grid forest) (forest-index forest l j)) + count l + until (>= v-tree tree-height))))))) + score)) - (seq-partition - (cl-map 'vector #'identity - visibility) 5) - (cl-loop for v across visibility when v count it) - )) +(ert-deftest test-solver () + (let* ((forest (solver-parse-input)) + (visibility (solver-tree-visibility forest))) + ;; part 1 + (should (= 1672 (cl-loop for v across (forest-grid visibility) when v count it))) + ;; part 2 + (thread-first (solver-max-view-score forest) (forest-grid) (seq-max) + (= 327180) (should)))) |