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