(in-package :ca.mhcat.advent2022)

;; --- Day 8: Treetop Tree House ---

;; The expedition comes across a peculiar patch of tall
;; trees all planted carefully in a grid. The Elves explain
;; that a previous expedition planted these trees as a
;; reforestation effort. Now, they're curious if this would
;; be a good location for a tree house.

;; First, determine whether there is enough tree cover here
;; to keep a tree house hidden. To do this, you need to
;; count the number of trees that are visible from outside
;; the grid when looking directly along a row or column.

;; The Elves have already launched a quadcopter to generate
;; a map with the height of each tree (your puzzle input).
;; For example:

;; 30373
;; 25512
;; 65332
;; 33549
;; 35390

;; Each tree is represented as a single digit whose value is
;; its height, where 0 is the shortest and 9 is the tallest.

;; A tree is visible if all of the other trees between it
;; and an edge of the grid are shorter than it. Only
;; consider trees in the same row or column; that is, only
;; look up, down, left, or right from any given tree.

;; All of the trees around the edge of the grid are visible
;; - since they are already on the edge, there are no trees
;; to block the view. In this example, that only leaves the
;; interior nine trees to consider:

;;     The top-left 5 is visible from the left and top. (It
;;     isn't visible from the right or bottom since other
;;     trees of height 5 are in the way.)

;;     The top-middle 5 is visible from the top and right.

;;     The top-right 1 is not visible from any direction;
;;     for it to be visible, there would need to only be
;;     trees of height 0 between it and an edge.

;;     The left-middle 5 is visible, but only from the right.

;;     The center 3 is not visible from any direction; for
;;     it to be visible, there would need to be only trees
;;     of at most height 2 between it and an edge.

;;     The right-middle 3 is visible from the right.

;;     In the bottom row, the middle 5 is visible, but the 3
;;     and 4 are not.

;; With 16 trees visible on the edge and another 5 visible
;; in the interior, a total of 21 trees are visible in this
;; arrangement.

;; Consider your map; how many trees are visible from
;; outside the grid?

(defparameter day8/test-data
  '("30373"
    "25512"
    "65332"
    "33549"
    "35390"))

(defun day8/visible-from-end (lst)
  (not (find-if (lambda (tree) (>= tree (car lst)))
                (cdr lst))))

(defun day8/parse-data (lst)
  (loop for line in lst
        collect (mapcar (lambda (ch)
                          (- (char-int ch)
                             (char-int #\0)))
                        (coerce line 'list))))

(defun day8/process-row (row mkcoordf)
  (loop for subl on row
        for idx from 0 below (length row)
        when (day8/visible-from-end subl)
          collect (funcall mkcoordf idx)))

(defun day8/process-grid (data mkcoordf1 mkcoordf2)
  (loop for row in data
        for idx from 0 below (length data)
        collect (append (day8/process-row
                         row
                         (funcall mkcoordf1 idx))
                        (day8/process-row
                         (reverse row)
                         (funcall mkcoordf2 idx)))
          into results
        finally (return (apply #'append results))))

;; Table rotation bits

(defun day8/rotate (data)
  "Rotates the table 90 degrees clockwise"
  (let ((row-size (length (car data))))
    (loop for idx from 0 below row-size
          collect (reverse (apply #'list
                                  (mapcar (lambda (row)
                                            (nth idx row))
                                          data))))))

;; These are function constructors for addressing the
;; coordinate space from within code that does not know the
;; orientation of the table.

(defun tblr (width height)
  "y = top to bottom, x = left to right"
  (lambda (y)
    (lambda (x)
      (list x y))))
(defun tbrl (width height)
  "y = top to bottom, x = right to left"
  (lambda (y)
    (lambda (x)
      (list (- width x 1) y))))
(defun lrbt (width height)
  "y = left to right, x = bottom to top"
  (lambda (y)
    (lambda (x)
      (list y (- height x 1)))))
(defun lrtb (width height)
  "y = left to right, x = top to bottom"
  (lambda (y)
    (lambda (x)
      (list y x))))

;; Part 1

(defun day8/compute-part1 (lst)
  (let* ((data (day8/parse-data lst))
         (height (length data))
         (width (length (car data))))
    (remove-duplicates
     (append
      (day8/process-grid data (tblr width height) (tbrl width height))
      (day8/process-grid (day8/rotate data) (lrbt width height) (lrtb width height)))
     :test #'equal)))

(defun day8/part1 ()
  (length
   (day8/compute-part1
    (load-lines "day8.txt"))))

;; --- Part Two ---

;; Content with the amount of tree cover available, the
;; Elves just need to know the best spot to build their tree
;; house: they would like to be able to see a lot of trees.

;; To measure the viewing distance from a given tree, look
;; up, down, left, and right from that tree; stop if you
;; reach an edge or at the first tree that is the same
;; height or taller than the tree under consideration. (If a
;; tree is right on the edge, at least one of its viewing
;; distances will be zero.)

;; The Elves don't care about distant trees taller than
;; those found by the rules above; the proposed tree house
;; has large eaves to keep it dry, so they wouldn't be able
;; to see higher than the tree house anyway.

;; In the example above, consider the middle 5 in the second
;; row:

;; 30373
;; 25512
;; 65332
;; 33549
;; 35390

;;     Looking up, its view is not blocked; it can see 1
;;     tree (of height 3).

;;     Looking left, its view is blocked immediately; it can
;;     see only 1 tree (of height 5, right next to it).

;;     Looking right, its view is not blocked; it can see 2
;;     trees.

;;     Looking down, its view is blocked eventually; it can
;;     see 2 trees (one of height 3, then the tree of height
;;     5 that blocks its view).

;; A tree's scenic score is found by multiplying together
;; its viewing distance in each of the four directions. For
;; this tree, this is 4 (found by multiplying 1 * 1 * 2 *
;; 2).

;; However, you can do even better: consider the tree of
;; height 5 in the middle of the fourth row:

;; 30373
;; 25512
;; 65332
;; 33549
;; 35390

;;     Looking up, its view is blocked at 2 trees (by
;;     another tree with a height of 5).

;;     Looking left, its view is not blocked; it can see 2
;;     trees.

;;     Looking down, its view is also not blocked; it can
;;     see 1 tree.

;;     Looking right, its view is blocked at 2 trees (by a
;;     massive tree of height 9).

;; This tree's scenic score is 8 (2 * 2 * 1 * 2); this is
;; the ideal spot for the tree house.

;; Consider each tree on your map. What is the highest
;; scenic score possible for any tree?

(defun day8/trees-visible-from-here (lst)
  (let ((pos (position-if (lambda (tree)
                            (>= tree (car lst)))
                          (cdr lst))))
    (or (and pos (1+ pos))
        (length (cdr lst)))))

(defun day8/row-wise-view (lst)
  (loop for row in lst
        collect
        (mapcar #'*
                (maplist #'day8/trees-visible-from-here row)
                (reverse (maplist #'day8/trees-visible-from-here (reverse row))))))

(defun day8/compute-part2 (lst)
  (apply
   #'max
   (apply
    #'append
    (mapcar (lambda (v1 v2) (mapcar #'* v1 v2))
            (day8/row-wise-view lst)
            (day8/rotate
             (day8/rotate
              (day8/rotate
               (day8/row-wise-view (day8/rotate lst)))))))))

(defun day8/part2 ()
  (day8/compute-part2
   (day8/parse-data
    (load-lines "day8.txt"))))