aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2022/08/solver.el
blob: 27ee8a007710894a0b8c50bd60d01f0357c4bc9e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
;;; solver.el --- Day 08 -*- lexical-binding: t; -*-
;;
;; Copyright (C) 2022 Óscar Nájera
;;
;; Author: Óscar Nájera <hi@oscarnajera.com>
;; Maintainer: Óscar Nájera <hi@oscarnajera.com>
;; Created: December 09, 2022
;; Modified: December 09, 2022
;;
;; This file is not part of GNU Emacs.
;;
;;; Commentary:
;;
;;  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))

(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-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)))))
      (dotimes (i (forest-depth forest))
        ;; left visible
        (setq last-max -1)
        (dotimes (j (forest-width forest))
          (update-visibility (forest-index forest i j)))
        ;; rigth visible
        (setq last-max -1)
        (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)
        (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-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))

(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))))