aboutsummaryrefslogtreecommitdiffstats
path: root/AoC2022/15/eg-in
blob: a61242407e0d5ef6618cca5e67224d0493edbe8e (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Sensor at x=2, y=18: closest beacon is at x=-2, y=15
Sensor at x=9, y=16: closest beacon is at x=10, y=16
Sensor at x=13, y=2: closest beacon is at x=15, y=3
Sensor at x=12, y=14: closest beacon is at x=10, y=16
Sensor at x=10, y=20: closest beacon is at x=10, y=16
Sensor at x=14, y=17: closest beacon is at x=10, y=16
Sensor at x=8, y=7: closest beacon is at x=2, y=10
Sensor at x=2, y=0: closest beacon is at x=2, y=10
Sensor at x=0, y=11: closest beacon is at x=2, y=10
Sensor at x=20, y=14: closest beacon is at x=25, y=17
Sensor at x=17, y=20: closest beacon is at x=21, y=22
Sensor at x=16, y=7: closest beacon is at x=15, y=3
Sensor at x=14, y=3: closest beacon is at x=15, y=3
Sensor at x=20, y=1: closest beacon is at x=15, y=3
*/ .highlight .nn { color: #FFCB6B } /* Name.Namespace */ .highlight .nx { color: #EEFFFF } /* Name.Other */ .highlight .py { color: #FFCB6B } /* Name.Property */ .highlight .nt { color: #FF5370 } /* Name.Tag */ .highlight .nv { color: #89DDFF } /* Name.Variable */ .highlight .ow { color: #89DDFF; font-style: italic } /* Operator.Word */ .highlight .pm { color: #89DDFF } /* Punctuation.Marker */ .highlight .w { color: #EEFFFF } /* Text.Whitespace */ .highlight .mb { color: #F78C6C } /* Literal.Number.Bin */ .highlight .mf { color: #F78C6C } /* Literal.Number.Float */ .highlight .mh { color: #F78C6C } /* Literal.Number.Hex */ .highlight .mi { color: #F78C6C } /* Literal.Number.Integer */ .highlight .mo { color: #F78C6C } /* Literal.Number.Oct */ .highlight .sa { color: #BB80B3 } /* Literal.String.Affix */ .highlight .sb { color: #C3E88D } /* Literal.String.Backtick */ .highlight .sc { color: #C3E88D } /* Literal.String.Char */ .highlight .dl { color: #EEFFFF } /* Literal.String.Delimiter */ .highlight .sd { color: #546E7A; font-style: italic } /* Literal.String.Doc */ .highlight .s2 { color: #C3E88D } /* Literal.String.Double */ .highlight .se { color: #EEFFFF } /* Literal.String.Escape */ .highlight .sh { color: #C3E88D } /* Literal.String.Heredoc */ .highlight .si { color: #89DDFF } /* Literal.String.Interpol */ .highlight .sx { color: #C3E88D } /* Literal.String.Other */ .highlight .sr { color: #89DDFF } /* Literal.String.Regex */ .highlight .s1 { color: #C3E88D } /* Literal.String.Single */ .highlight .ss { color: #89DDFF } /* Literal.String.Symbol */ .highlight .bp { color: #89DDFF } /* Name.Builtin.Pseudo */ .highlight .fm { color: #82AAFF } /* Name.Function.Magic */ .highlight .vc { color: #89DDFF } /* Name.Variable.Class */ .highlight .vg { color: #89DDFF } /* Name.Variable.Global */ .highlight .vi { color: #89DDFF } /* Name.Variable.Instance */ .highlight .vm { color: #82AAFF } /* Name.Variable.Magic */ .highlight .il { color: #F78C6C } /* Literal.Number.Integer.Long */
;;; 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:

(require 'subr-x)

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