aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2022
diff options
context:
space:
mode:
Diffstat (limited to 'AoC2022')
-rw-r--r--AoC2022/08/solver.el123
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))))